SICP – cap. 1 – Esempio: test di primalità – esercizi – 34

1326

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)))))

s62

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 😳
:mrgreen:

Posta un commento o usa questo indirizzo per il trackback.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: