Exercise1-26 <---> Exercise1-28
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.
Ru: Покажите, что числа Кармайкла, перечисленные в сноске 47, действительно «обманывают» тест Ферма: напишите процедуру, которая берет целое число n и проверяет, правда ли an равняется a по модулю n для всех a < n, и проверьте эту процедуру на этих числах Кармайкла.
Scheme solution:
(define (square n) (* n n))
(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))))
(define (carmichael? n)
(define (carm? n a)
(cond ((= a 0) #t)
((= (expmod a n n) a) (carm? n (- a 1)))
(else #f)))
(carm? n (- n 1)))
> (carmichael? 561) #t > ...
Note: According to the task, the procedure returns true not only for Carmichael numbers, which are not prime, but for all prime numbers as well.
Haskell solution:
expmod base 0 m = 1
expmod base exp m | even exp = square (expmod base (exp `div` 2) m) `mod` m
| otherwise = (base * expmod base (exp - 1) m) `mod` m
where square n = n * n
is'carmichael n = is'carm n (n-1)
where is'carm n 0 = True
is'carm n a | expmod a n n == a = is'carm n (a-1)
| otherwise = False
Prelude> is'carmichael 561 True
OCaml solution:
let square n = n * n
let rec expmod base exp m =
if exp = 0 then
1
else if exp mod 2 = 0 then
square (expmod base (exp / 2) m) mod m
else
(base * expmod base (exp - 1) m) mod m
let is_carmichael n =
let rec is_carm n a =
if a = 0 then
true
else if expmod a n n = a then
is_carm n (a-1)
else
false
in
is_carm n (n-1)
# is_carmichael 561;; - : bool = true
Standard ML solution:
fun square n = n * n
fun expmod (base, exp, m) =
if exp = 0 then
1
else if exp mod 2 = 0 then
square (expmod (base, exp div 2, m)) mod m
else
(base * expmod (base, exp - 1, m)) mod m
fun is_carmichael n = let
fun is_carm (n, a) =
if a = 0 then
true
else if expmod (a, n, n) = a then
is_carm (n, a-1)
else
false
in
is_carm (n, n-1)
end
- is_carmichael 561; val it = true : bool
Exercise1-26 <---> Exercise1-28
Comments
(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))))
(define (carmichel? n)
(define (mod-test a n)
(if (= (expmod a n n) (remainder a n))
#t
#f))
(define (carmichel a n)
(cond ((= a n) (display "prime or carmichel"))
((mod-test a n) (carmichel (+ a 1) n))
(else (display "not prime, not carmichel"))))
(carmichel 1 n))(carmichel? 561) | ||||
| Posted by SriramDevadas at 2009-04-03 02:18:50 | ||||