学步园

;Fermat's little theorem

;If N is a prime number and A is any positive number less than N, then (A^N % N) == (A % N). (A^N stands for A raised to the Nth power.)

;This theorem can be used to test the primality of a number. If the above relation is not satisfied for a N, then N is certainly not a prime. If the above relation is satisfied for a N, then the chance is good that N is a prime. The equation is necessary for N to be a prime, but it is not sufficient.

;The programs followed are a implementation for testing the primality of a N.

;This function call fermat-test several times.<br /> ;If failed in a test, then return false.<br /> ;Otherwise, return true.<br /> (define (prime? n times)<br /> (if (= 0 times) true<br /> (if (fermat-test n (+ 1 (random (- n 1) ) ) )<br /> (prime? n (- times 1) )<br /> false) ) )</p> <p>;Fermat test<br /> ;n is the number to be tested<br /> ;a is the number less than n and greater than 0<br /> (define (fermat-test n a)<br /> (= (exponent-modulo a n n) a) )</p> <p>;exponent-modulo<br /> (define (exponent-modulo base exp mod)<br /> (remainder (exponent base exp) mod) )</p> <p>;calculate base^exp<br /> (define (exponent base exp)<br /> (exponent-helper base exp 1) )</p> <p>;tail recursive base^exp helper<br /> (define (exponent-helper base exp product)<br /> (cond ( (= exp 0) product )<br /> ( (even? exp) (exponent-helper (* base base) (/ exp 2) product) )<br /> ( else (exponent-helper base (- exp 1) (* product base) ) ) ) )</p> <p>;determine whether a number is even or odd<br /> (define (even? n)<br /> (= (remainder n 2) 0) )</p> <p>