1 ;; (define (expmod base exp m)
2 ;;   (cond ((= exp 0) 1)
3 ;; 	((even? exp)
4 ;; 	 (remainder (square (expmod base (/ exp 2) m)) m))
5 ;; 	(else (remainder (* base (expmod base (- exp 1) m)) m))))
6 
7 ;; (define (fermat-test n)
8 ;;   (define (try-it a)
9 ;;     (= (expmod a n n) a))
10 ;;   (try-it (+ 1 (random (- n 1)))))
11 
12 ;; (define (fast-prime? n times)
13 ;;   (cond ((= times 0) true)
14 ;; 	((fermat-test n) (fast-prime? n (- times 1)))
15 ;; 	(else false)))
16 
17 ;; ;; (define (test-case actual expected)
18 ;; ;;   (load-option 'format)
19 ;; ;;   (newline)
20 ;; ;;   (format #t "Actual: ~A Expected: ~A" actual expected))
21 
22 ;; (define (prime? n)
23 ;;   (let ((times-to-test 10))
24 ;;     (fast-prime? n times-to-test)))
25 
26 ;; (define (timed-prime-test n)
27 ;;   (newline)
28 ;;   (display n)
29 ;;   (start-prime-test n (runtime)))
30 ;; (define (start-prime-test n start-time)
31 ;;   (if (prime? n)
32 ;;       (report-prime (- (runtime) start-time))))
33 ;; (define (report-prime elapsed-time)
34 ;;   (display " *** ")
35 ;;   (display elapsed-time))
36 
37 ;; (define (search-for-primes lower upper)
38 ;;   (cond ((even? lower) (search-for-primes (+ lower 1) upper))
39 ;; 	((< lower upper) (begin (timed-prime-test lower)
40 ;; 				(search-for-primes (+ lower 2) upper)))
41 ;; 	(else (newline)
42 ;; 	      (display " *** Finished *** "))))
43 
44 ;; (search-for-primes 100000000000001 100000000000099)
45 ;; (search-for-primes 1000000000000001 1000000000000099)
46 ;; (search-for-primes 10000000000000001 10000000000000099)
47 ;; (search-for-primes 100000000000000001 100000000000000099)
48 ;; (search-for-primes 1000000000000000001 1000000000000000099)
49 ;; (search-for-primes 10000000000000000001 10000000000000000099)
50 
51 
52 ;; (define (fermat-test n)
53 ;;   (define (try-it a)
54 ;;     (= (expmod a n n) a))
55 ;;   (try-it (+ 1 (random (- n 1)))))
56 
57 ;; (define (fast-prime? n times)
58 ;;   (cond ((= times 0) true)
59 ;; 	((fermat-test n) (fast-prime? n (- times 1)))
60 ;; 	(else false)))
61 
62 ;; (define (test-case actual expected)
63 ;;   (load-option 'format)
64 ;;   (newline)
65 ;;   (format #t "Actual: ~A Expected: ~A" actual expected))
66 
67 ;; (define (prime? n)
68 ;;   (let ((times-to-test 10))
69 ;;     (fast-prime? n times-to-test)))
70 
71 ;; (define (timed-prime-test n)
72 ;;   (newline)
73 ;;   (display n)
74 ;;   (start-prime-test n (runtime)))
75 ;; (define (start-prime-test n start-time)
76 ;;   (if (prime? n)
77 ;;       (report-prime (- (runtime) start-time))))
78 ;; (define (report-prime elapsed-time)
79 ;;   (display " *** ")
80 ;;   (display elapsed-time))
81 
82 ;; (define (search-for-primes lower upper)
83 ;;   (cond ((even? lower) (search-for-primes (+ lower 1) upper))
84 ;; 	((< lower upper) (begin (timed-prime-test lower)
85 ;; 				(search-for-primes (+ lower 2) upper)))
86 ;; 	(else (newline)
87 ;; 	      (display " *** Finished *** "))))
88 
89 
90 
91 
92 
93 ;; Exercise 1.27.  Demonstrate that the Carmichael numbers listed in footnote 47 really do fool the Fermat test. That is, write a procedure that takes an integer n and tests whether an is congruent to a modulo n for every a<n, and try your procedure on the given Carmichael numbers. 
94 
95 ;; Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a ``correct'' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering. 
96 
97 ;; calculate base^exp modulo m
98 (define (expmod base exp m)
99   (cond ((= exp 0) 1)
100 	((even? exp)
101 	 (remainder (square (expmod base (/ exp 2) m)) m))
102 	(else (remainder (* base (expmod base (- exp 1) m)) m))))
103 
104 ;; tests if integer n passes fermat's little theorem
105 (define (fermat-prime? n)
106   (define (fermat-test a)
107     (cond ((= a n) #t)
108 	  ((not (= (expmod a n n) a)) #f)
109 	  (else (fermat-test (+ a 1)))))
110   (fermat-test 1))
111 
112 (define (list-primes upper)
113   (define (test i)
114     (cond ((= i upper) (display "Finished"))
115 	  ((fermat-prime? i) (begin (display i)
116 				    (newline))))
117     (test (+ i 1)))
118   (test 2))
119 
120 (define (test-case actual expected)
121   (load-option 'format)
122   (newline)
123   (format #t "Actual: ~A Expected: ~A" actual expected))
124 
125 ;; (test-case (fermat-prime? 2) #t)
126 ;; (test-case (fermat-prime? 3) #t)
127 ;; (test-case (fermat-prime? 4) #f)
128 ;; (test-case (fermat-prime? 5) #t)
129 ;; (test-case (fermat-prime? 6) #f)
130 ;; (test-case (fermat-prime? 7) #t)
131 ;; (test-case (fermat-prime? 8) #f)
132 ;; (test-case (fermat-prime? 9) #f)
133 
134 
135 ;; (list-primes 10000)
136 
137 ;; Carmichael Numbers
138 (test-case (fermat-prime? 561) #f)
139 (test-case (fermat-prime? 1105) #f)
140 (test-case (fermat-prime? 1729) #f)
141 (test-case (fermat-prime? 2465) #f)
142 (test-case (fermat-prime? 2821) #f)
143 (test-case (fermat-prime? 6601) #f)