## SICP – cap. 1 – Esempio: test di primalità – esercizi – 34 Continuo da qui a copiare qui.

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.

Panico. Davvero. No, dai basta procedere passo-passo e si può fare (`btl.rkt):`

``````(require (lib "27.ss" "srfi"))

(define (square-check x m)
(if (and (not (or (= x 1) (= x (- m 1))))
(= (remainder (* x x) m) 1))
0
(remainder (* x x) m)))

(define (even? n)
(= (remainder n 2) 0))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(square-check (expmod base (/ exp 2) m) m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))

(define (miller-rabin-test n)
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (+ 2 (random-integer (- n 2)))))`````` ho copiato Bill the Lizard 😀

Altrettanto bella la versione di Ken Dick (`kd.rkt`):

``````#lang racket

(define (square x)
(* x x))

(define (expmod-with-trivial-sqrt-check base exp m)
(cond ((= exp 0) 1)
((even? exp)
(let* ((intermediate
(expmod-with-trivial-sqrt-check base (/ exp 2) m))
(squared-mod (remainder (square intermediate) m)))
(if (and (not
(or (= intermediate 1) (= intermediate (- m 1))))
(= squared-mod 1))
0
squared-mod)))
(else
(remainder
(* base (expmod-with-trivial-sqrt-check base (- exp 1) m))
m))))

(define (miller-rabin-test n)
(define (try-it a )
(= (expmod-with-trivial-sqrt-check a (- n 1) n) 1))
(try-it (+ 1 (random (- n 1)))))``````

Non metto lo screenshot perché identico al precedente.

Su s-sol due soluzioni, con considerazioni interessanti (per esempio sul let che SICP finora non ha introdotto).

SICP richiederebbe più tempo, lo so 😳 Posta un commento o usa questo indirizzo per il trackback.