米勒-拉宾测试 (SICP 1.28)
Miller-Rabin test (SICP 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 less than 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.
这是我目前所拥有的。
(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))
(define (expmod-signal b n m)
(define (check a)
(and (not (= a 1))
(not (= a (- n 1)))
(= (square a) (remainder 1 n))))
(cond ((= n 0) 1)
((check b) 0)
((even? n) (remainder (square (expmod-signal b (/ n 2) m)) m))
(else (remainder (* b (expmod-signal b (- n 1) m)) m))))
(define (miller-rabin n)
(define (fail? n a)
(or (= n 0) (not (= n a))))
(define (try a)
(cond ((= a 1) #t)
((fail? (expmod-signal a (- n 1) n) a) #f)
(else (try (- a 1)))))
(try (- n 1)))
我认为我正确地实施了 miller-rabin
,但我不明白修改后的 expmod
应该如何工作。你检查方块前的数字还是方块后的数字?我看问题不知道。
我通过使用 expmod-signal
中 expmod
的原始定义解决了这个问题。在我的测试中的某个地方,expmod-signal
自然地 return 归零并扰乱了测试。我误解了check函数,"whose square is equal to 1 modulo n"的意思是check if a^2 % m = 1
。如果参数是 1 mod n 的 non-trivial 平方根,则此检查函数的工作方式是 return 0,否则 return 参数。如果它 return 为零,则零会传播到 expmod-signal
的其余部分并被 return 编辑。
(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))
(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 (expmod-signal b n m)
(define (check a)
(if (and (not (= a 1))
(not (= a (- n 1)))
(= (remainder (square a) n) 1))
0
a))
(cond ((= n 0) 1)
((even? n) (remainder (square (check (expmod b (/ n 2) m))) m))
(else (remainder (* b (expmod b (- n 1) m)) m))))
(define (miller-rabin n)
(define (fail? a)
(or (= a 0) (not (= a 1))))
(define (try a)
(cond ((= a 1) #t)
((fail? (expmod-signal a (- n 1) n)) #f)
(else (try (- a 1)))))
(try (- n 1)))
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 less than n and raise a to the (n - 1)st power modulo n using the
expmod
procedure. However, whenever we perform the squaring step inexpmod
, 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 tofermat-test
. Check your procedure by testing various known primes and non-primes. Hint: One convenient way to makeexpmod
signal is to have it return 0.
这是我目前所拥有的。
(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))
(define (expmod-signal b n m)
(define (check a)
(and (not (= a 1))
(not (= a (- n 1)))
(= (square a) (remainder 1 n))))
(cond ((= n 0) 1)
((check b) 0)
((even? n) (remainder (square (expmod-signal b (/ n 2) m)) m))
(else (remainder (* b (expmod-signal b (- n 1) m)) m))))
(define (miller-rabin n)
(define (fail? n a)
(or (= n 0) (not (= n a))))
(define (try a)
(cond ((= a 1) #t)
((fail? (expmod-signal a (- n 1) n) a) #f)
(else (try (- a 1)))))
(try (- n 1)))
我认为我正确地实施了 miller-rabin
,但我不明白修改后的 expmod
应该如何工作。你检查方块前的数字还是方块后的数字?我看问题不知道。
我通过使用 expmod-signal
中 expmod
的原始定义解决了这个问题。在我的测试中的某个地方,expmod-signal
自然地 return 归零并扰乱了测试。我误解了check函数,"whose square is equal to 1 modulo n"的意思是check if a^2 % m = 1
。如果参数是 1 mod n 的 non-trivial 平方根,则此检查函数的工作方式是 return 0,否则 return 参数。如果它 return 为零,则零会传播到 expmod-signal
的其余部分并被 return 编辑。
(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))
(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 (expmod-signal b n m)
(define (check a)
(if (and (not (= a 1))
(not (= a (- n 1)))
(= (remainder (square a) n) 1))
0
a))
(cond ((= n 0) 1)
((even? n) (remainder (square (check (expmod b (/ n 2) m))) m))
(else (remainder (* b (expmod b (- n 1) m)) m))))
(define (miller-rabin n)
(define (fail? a)
(or (= a 0) (not (= a 1))))
(define (try a)
(cond ((= a 1) #t)
((fail? (expmod-signal a (- n 1) n)) #f)
(else (try (- a 1)))))
(try (- n 1)))