;; Fermat's Little Theorem:
;; If N is a prime number and A is any positive integer less than N,
;; then A raised to the N-th power is congruent to A modulo N
;; Two numbers are said to be congruent modulo N if they both
;; have the same remainder when divided by N
;; The Fermat test:
;; Given a number N, pick a random number A < N
;; and compute the remainder of A^N modulo N.
;; If the result is not equal to A, then N is certainly not prime
;; If it is A, then chances are good that N is prime.
;; Now pick anthor random number A and test it with the same method.
;; If it also satisfies the equation,
;; then we can be even more confident that N is prime.
;; By trying more and more values of A,
;; We can increase our confidence in the result.
;; This algorithm is known as the Fermat test.
( define ( bad-exp base exp )
( cond ( ( = exp 0 ) 1 )
( ( even?
exp )
( square ( bad-exp base ( / exp 2 ) ) ) )
( else ( * base ( bad-exp base ( - exp 1 ) ) ) ) ) )
( define ( bad-expmod base exp m )
( remainder ( bad-exp base exp ) m ) )
( define ( expmod base exp m )
( cond ( ( = exp 0 ) 1 )
( ( even?
exp )
( remainder
( square ( expmod base ( / exp 2 ) m ) ) m ) )
( else
( remainder
( * base ( expmod base ( - exp 1 ) m ) ) m ) ) ) )
;; 第一个过程比第二个过程慢,且超过一定长度的数值就不能计算,
;; 由于第一个是先将阶乘算出来。再取模，而第二个是在阶乘的过程中就取模
;; 26 mod 4 和 ( 2 mod 4 ) * ( 13 mod 4 ) 结果一样
;; ( expmod 32 10911110033 10911110033 )
;; ( my-expmod 32 1091111003 1091111003 )
( define ( fermat-test n )
( define ( try-it a )
( = ( expmod a n n ) a ) )
( try-it ( + 1 ( random ( - n 1 ) ) ) ) )
( define ( fast-prime? n times )
( cond ( ( = times 0 ) true )
( ( fermat-test n )
( fast-prime? n ( - times 1 ) ) )
( else false ) ) )
;; The Fermat test differs in character from most familiar algorithms,
;; in which one computes an answer that is guaranteed to be correct.
;; Here, the answer obtained is only probably correct.
;; More precisely, if N ever fails the Fermat test,
;; we can be certain that N is not prime.
;; But the fact that N passes the test,
;; while an extremely strong indication,
;; is still not a guarantee that N is prime.
;; What we would like to say is that for any number N,
;; if we perform the test enough times and find that N always passes the test,
;; then the probability of error in our primality test can be made as small as we like.
;; Unfortunately, this assertion is not quite correct.
;; There do exist numbers that fool the Fermat test:
;; numbers N that are not prime and yet have the property that
;; an is congruent to a modulo n for all integers A < N.
;; Such numbers are extremely rare,
;; so the Fermat test is quite reliable in practice
;; There are variations of the Fermat test that cannot be fooled.
;; In these tests, as with the Fermat method,
;; one tests the primality of an integer N
;; by choosing a random integer A < N and
;; checking some condition that depends upon N and A.
;; On the other hand, in contrast to the Fermat test,
;; one can prove that, for any N,
;; the condition does not hold for most of the integers A < N
;; unless N is prime.
;; Thus, if N passes the test for some random choice of A,
;; the chances are better than even that N is prime.
;; If N passes the test for two random choices of A,
;; the chances are better than 3 out of 4 that N is prime.
;; By running the test with more and more randomly chosen
;; values of A we can make the probability of error as small as we like.
;; The existence of tests for which one can prove that
;; the chance of error becomes arbitrarily small has sparked interest in
;; algorithms of this type,
;; which have come to be known as probabilistic algorithms.
;; There is a great deal of research activity in this area,
;; and probabilistic algorithms have been fruitfully applied to many fields