Exercise1-27 <---> Exercise1-29
Exercise 1.28
One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976; Rabin 1980). This starts from an alternate form of Fermat's Little Theorem, which states that if n is a prime number and a is any positive integer less than n, then a raised to the (n - 1)st power is congruent to 1 modulo n. To test the primality of a number n by the Miller-Rabin test, we pick a random number a<n and raise a to the (n - 1)st power modulo n using the expmod procedure. However, whenever we perform the squaring step in expmod, we check to see if we have discovered a "nontrivial square root of 1 modulo n," that is, a number not equal to 1 or n - 1 whose square is equal to 1 modulo n. It is possible to prove that if such a nontrivial square root of 1 exists, then n is not prime. It is also possible to prove that if n is an odd number that is not prime, then, for at least half the numbers a<n, computing an-1 in this way will reveal a nontrivial square root of 1 modulo n. (This is why the Miller-Rabin test cannot be fooled.) Modify the expmod procedure to signal if it discovers a nontrivial square root of 1, and use this to implement the Miller-Rabin test with a procedure analogous to fermat-test. Check your procedure by testing various known primes and non-primes. Hint: One convenient way to make expmod signal is to have it return 0.
Ru: Один из вариантов теста Ферма, который невозможно обмануть, называется тест Миллера–Рабина (Miller-Rabin test) (Miller 1976; Rabin 1980). Он основан наальтернативной формулировке Малой теоремы Ферма, которая состоит в том, что если n — простое число, а a — произвольное положительное целое число, меньшее n, то a в n − 1-ой степени равняется 1 по модулю n. Про- веряя простоту числа n методом Миллера–Рабина, мы берем случайное число a < n и возводим его в (n − 1)-ю степень по модулю n с помощью процедуры expmod. Однако когда в процеду- ре expmod мы проводим возведение в квадрат, мы проверяем, не нашли ли мы «нетривиальный квадратный корень из 1 по модулю n», то есть число, не равное 1 или n − 1, квадрат которого по модулю n равен 1. Можно доказать, что если такой нетривиальный квадратный корень из 1 существует, то n не простое число. Можно, кроме того, доказать, что если n — нечетное число, не являющееся простым, то по крайней мере для половины чисел a < n вычисление an−1 с помощью такой процедуры обнаружит нетривиальный квадратный корень из 1 по модулю n (вот почему тест Миллера–Рабина невозможно обмануть). Модифицируйте процедуру expmod так, чтобы она сигнализировала обнаружение нетривиального квадратного корня из 1, и используйте ее для ре- ализации теста Миллера–Рабина с помощью процедуры, аналогичной fermat-test. Проверьте свою процедуру на нескольких известных Вам простых и составных числах. Подсказка: удобный способ заставить expmod подавать особый сигнал — заставить ее возвращать 0.
Scheme solution:
Modified expmod:
(define (square x)
(* x x))
(define (apply-trivial-check k m r)
(if (and (not (= k 1))
(not (= k (- m 1)))
(= r 1))
0
r))
(define (remainder-or-trivial k m)
(apply-trivial-check k m (remainder (square k) m)))
(define (modified-expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder-or-trivial (modified-expmod base (/ exp 2) m) m))
(else
(remainder (* base (modified-expmod base (- exp 1) m))
m))))
Miller-Rabin test:
(define (miller-rabin-test n)
(define (miller-rabin-iteration a t n)
(define (try-it a)
(= (modified-expmod a (- n 1) n) 1))
(if (= a n)
(> t (/ n 2))
(if (try-it a)
(miller-rabin-iteration (+ a 1) (+ t 1) n)
(miller-rabin-iteration (+ a 1) t n))))
(miller-rabin-iteration 1 0 n))
Now let's check how miller-rabin-test procedure works for several prime and compound numbers:
> (miller-rabin-test 5)
#t
> (miller-rabin-test 15)
#f
> (miller-rabin-test 97)
#t
> (miller-rabin-test 121)
#f
> (miller-rabin-test 1003)
#f
> (miller-rabin-test 1009)
#t
> (miller-rabin-test 100003)
#t
> (miller-rabin-test 100005)
#f
And what about first six Carmichael numbers?
> (miller-rabin-test 561)
#f
> (miller-rabin-test 1105)
#f
> (miller-rabin-test 1729)
#f
> (miller-rabin-test 2465)
#f
> (miller-rabin-test 2821)
#f
> (miller-rabin-test 6601)
#f
As we can see the procedure identifies prime numbers correctly.
Exercise1-27 <---> Exercise1-29
Comments
| I'm a little puzzled about what returning (> t (/ n 2)) is all about. Additionally, the exercise explicitly says "pick a random number", but I don't see where you're doing that. In fact, I'm not certain that this is a true implementation of the Miller-Rabin test despite the fact that it works well enough in the test cases shown. | ||||
| Posted by c-76-118-20-206 at 2008-01-02 20:58:18 X | ||||
Thanks for comment! Author of this solution (Sergey) will reply you soon, I think (when he's online). | ||||
| Posted by IvanVeselov at 2008-01-02 21:17:23 | ||||
| The exercise says "It is also possible to prove that if n is an odd number that is not prime, then, for at least half the numbers a<n, computing an-1 in this way will reveal a nontrivial square root of 1 modulo n." So we are running through the sequence of numbers a<n and accumulate number of nontrivial square roots of 1 modulo n. If their number is less than n/2 it means that number n is prime. However I think I should get back to the implementation and maybe to change it a bit. | ||||
| Posted by SergeyKhenkin at 2008-01-06 22:20:41 | ||||
Hey! Urrrrgghhh! This solution is absolutely WRONG! | ||||
| Posted by PCS-TTC-gw at 2008-02-09 21:24:49 X | ||||
I think my approach to the solution was a little bit wrong. The solution is correct in the sense that it produces correct results. But the essence of Miller-Rabin test is indeed as some people pointed out in that it is probabilistic and it guarantees correctness of the result with any given probability. I'll provide another solution to this exercise which was shared with me by a very smart reader of my SICP in Russian website. The code goes below: (define (square x)
(* x x))
(define (sqrmod x m)
(let ((y (remainder (square x) m)))
(if (and (= y 1) (not (= x 1)) (not (= x (- m 1))))
0
y)))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp) (sqrmod (expmod base (/ exp 2) m) m))
(else (remainder (* base (expmod base (- exp 1) m)) m))))
(define (witness? a n)
(not (= (expmod a (- n 1) n) 1)))
(define (miller-rabin-test n)
(not (witness? (+ 1 (random (- n 1))) n)))
(define (fast-prime? n times)
(cond ((= times 0) true)
((miller-rabin-test n) (fast-prime? n (- times 1)))
(else false)))
Hope it is helpful. | ||||
| Posted by SergeyKhenkin at 2008-03-04 12:13:22 | ||||
(define (non-trivial-or-remainder number m)
(if (and (or (not (= number 1)) (not (= number (- m 1)))) (= (square number) (remainder 1 n)))
0
(remainder number m)))
(define (expmod-miller-rabin base exp m)
(cond ((= exp 0) 1)
((even? exp)
(non-trivial-or-remainder (square (expmod-miller-rabin base (/ exp 2) m))
m))
(else
(remainder (* base (expmod-miller-rabin base (- exp 1) m))
m))))
(define (miller-rabin-test a n)
(define (try-it a)
(= (expmod a (- n 1) n) (remainder 1 n)))
(try-it a))
(define (miller-rabin-test-odd x max n)
(cond ((> x max) #t)
((eq? (miller-rabin-test x n) #f) #f)
(else
(miller-rabin-test-odd (+ x 1) max n))))
(define (fast-prime? n)
(if (= (remainder n 2) 0)
#f
(miller-rabin-test-odd 1 (/ (+ 1 n) 2) n)))
| ||||
| Posted by SriramDevadas at 2009-04-08 01:32:43 | ||||
As i can see, you didn't read CLRS...