Упражнение SICP 1.28 - Миллер-Рабин - «хотя бы половина чисел покажет нетривиальный квадратный корень из 1 по модулю n»

Question

SICP Упражнение 1.28

https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_thm_1.28

Один вариант теста Ферма, который нельзя обмануть называется тестом Миллера-Рабина (Miller 1976; Rabin 1980). Это начинается из альтернативной формы маленькой теоремы Ферма, которая утверждает, что если n простое число и a любое положительное целое число меньше n, то возведенное в (n - 1) -й степени соответствует 1 по модулю n. Тестировать простоту числа n по критерию Миллера-Рабина, мы выбираем случайное число a если n нечетное число, которое не является простым, то, хотя бы для половины чисел a (Вот почему Тест Миллера-Рабина не может быть одурачен.) Измените процедуру expmod на сигнал, если он обнаруживает нетривиальный квадратный корень из 1, и использовать это для выполнить тест Миллера-Рабина с помощью процедуры, аналогичной Fermat-тест. Проверьте вашу процедуру, протестировав различные известные простые числа и не являющиеся простые числа. Подсказка: один из удобных способов сделать сигнал expmod - это иметь это возвращает 0.

Я написал свое собственное решение, и его результаты соответствуют решениям, представленным здесь:

http://community.schemewiki.org/?sicp-ex-1.28

15 - нечетное число, которое не является простым, поэтому, по крайней мере, для половины чисел a от 1 до 14, я ожидаю, что вычисление expmod(a, 14, 15) покажет нетривиальный квадратный корень из 1 по модулю n , что обозначается expmod возвращением 0.

Однако вот результаты, которые я получаю:

(expmod 1 14 15)
> 1
(expmod 2 14 15)
> 4
(expmod 3 14 15)
> 9
(expmod 4 14 15)
> 0
(expmod 5 14 15)
> 10
(expmod 6 14 15)
> 6
(expmod 7 14 15)
> 4
(expmod 8 14 15)
> 4
(expmod 9 14 15)
> 6
(expmod 10 14 15)
> 10
(expmod 11 14 15)
> 0
(expmod 12 14 15)
> 9
(expmod 13 14 15)
> 4
(expmod 14 14 15)
> 1

Как видно, только 2 из этих результатов 0, что намного меньше, чем минимум, как и ожидалось.

Я неправильно понимаю утверждение? Я полный идиот? Код неправильный? SICP не так? Большое спасибо.

Редактировать 1: меня попросили указать точный код, который я использую. Вот оно, хотя я, по сути, просто копирую решение, с которым я связался, и псевдоним remainder как mod, потому что так его называет мой интерпретатор.

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

 (define remainder mod)

 (define (miller-rabin-expmod base exp m) 
   (define (squaremod-with-check x) 
     (define (check-nontrivial-sqrt1 x square) 
       (if (and (= square 1) 
                (not (= x 1)) 
                (not (= x (- m 1)))) 
           0 
           square)) 
     (check-nontrivial-sqrt1 x (remainder (square x) m))) 
   (cond ((= exp 0) 1) 
         ((even? exp) (squaremod-with-check 
                       (miller-rabin-expmod base (/ exp 2) m))) 
         (else 
          (remainder (* base (miller-rabin-expmod base (- exp 1) m)) 
                     m))))

(define expmod miller-rabin-expmod)

(print (expmod 1 14 15))
(print (expmod 2 14 15))
(print (expmod 3 14 15))
(print (expmod 4 14 15))
(print (expmod 5 14 15))
(print (expmod 6 14 15))
(print (expmod 7 14 15))
(print (expmod 8 14 15))
(print (expmod 9 14 15))
(print (expmod 10 14 15))
(print (expmod 11 14 15))
(print (expmod 12 14 15))
(print (expmod 13 14 15))
(print (expmod 14 14 15))

Редактировать 2: Теперь я также вручную вычислил шаги expmod(a, 14, 15) (которые всегда повторяются с помощью exp = 14, exp = 7, exp = 6, exp = 3, exp = 2, exp = 1, exp = 0 ), для всех значений a от 1 до 14, и я уверен, что только a = 4 и a = 11 встречают нетривиальный квадратный корень из 1. Поэтому я склонен думать, что SICP либо ошибается в этом или не выражает себя четко.

Answer 1

Я нашел статью, которая охватывает этот тест и доказательство конкретного результата, что более половины значений от 2 до n-2 приведут к нетривиальному квадратному корню из 1. (Теорема 4.1)

• https://kconrad.math.uconn.edu/blurbs/ugradnumthy/millerrabin.pdf

Я сделал этот код для двойной проверки

(define (print x) (display x) (newline))

(define (assert p) (unless p (error 'assert-failed)))

(define (power-of-two-split m)
  ;; write m = 2^e k
  (let loop ((e 0) (k m))
    (if (even? k)
        (loop (+ e 1) (quotient k 2))
        (cons e k))))

(define (exp/mod a k n)
  ;; a^k (mod n)
  (cond ((= k 0) 1)
        ((= k 1) (modulo a n))
        (else (modulo (* a (exp/mod a (- k 1) n)) n))))

(define (miller-rabin a n)
  (assert (odd? n))
  (assert (= 3 (modulo n 4))) ;; only handles e=1 case, need to use power-of-two-split for full test
  (let ((k (quotient (- n 1) 2)))
    (exp/mod a k n)))

(define (test n)
  (for ((i (in-range 2 (- n 2))))
    (let ((m (miller-rabin i n)))
      (print `(,i -> ,m squared ,(exp/mod m 2 n))))))

(test 15)

выводит следующий результат

(2 -> 8 squared 4)
(3 -> 12 squared 9)
(4 -> 4 squared 1)
(5 -> 5 squared 10)
(6 -> 6 squared 6)
(7 -> 13 squared 4)
(8 -> 2 squared 4)
(9 -> 9 squared 6)
(10 -> 10 squared 10)
(11 -> 11 squared 1)
(12 -> 3 squared 9)

Итак, проверяя формальное определение свидетеля-мельника, они на самом деле все зим:

Определение 2.3. Для нечетного n> 1 запишите n - 1 = 2 ^ ek с k нечетным и выберите a ∈ {1,. , , , n - 1}. Мы говорим, что a является свидетельством Миллера-Рабина для n, если все сравнения в нем ложны: * a ^ k = 1 mod n и a ^ {(2 ^ i) k} = −1 mod n для всех i ∈ {0,. , , , е - 1}.

и вы можете видеть, что ни одно из значений в столбце 'm' не равно 1, и ни одно из значений в столбце в квадрате не равно 14. Таким образом, все они являются свидетелями, поэтому> 50%.

Код, который выполняет "check-nontrivial-sqrt1", не подходит в данном конкретном случае n = 3 (mod 4), потому что в этом случае e = 1.

---

Обновление:

Я только что понял причину, почему у нас много свидетелей, но мы не всегда находим квадратный корень из них всех:

Идея свидетелей Миллера-Рабина состоит в том, чтобы найти неожиданный квадратный корень из 1 mod n. Это не всегда то, что мы на самом деле находим, поскольку предпосылка a n − 1 mod 1 mod n для простого n может на самом деле не быть верной для составного n.

вот таблица ^ (n-1) (мод n) для n = 15

(2 -> 4)
(3 -> 9)
(4 -> 1)
(5 -> 10)
(6 -> 6)
(7 -> 4)
(8 -> 4)
(9 -> 6)
(10 -> 10)
(11 -> 1)
(12 -> 9)

как вы можете видеть, только два раза конгруэнция a ^ (n-1) = 1 (mod n) действительно выполняется.

Answer 2

Один вариант теста Ферма, который нельзя обмануть, называется тестом Миллера-Рабина (Miller 1976; Rabin 1980).Это начинается с альтернативной формы Маленькой теоремы Ферма, которая гласит, что если n - простое число, а a - любое положительное целое число, меньшее n, то возведение в (n - 1) -ю степень является конгруэнтным 1 по модулю n.

• n простое число, a a ^ (n-1) = 1 (mod n)

Для проверки простотычисла n с помощью теста Миллера-Рабина мы выбираем случайное число a

Итак, выберитеслучайным образом и проверьте, если a ^ (n-1) = 1 (mod n).если это , а не , тогда вы знаете, что n не простое число.

Однако всякий раз, когда мы выполняем шаг возведения в квадрат в expmod, мы проверяем, обнаружили ли мы `` нетривиальный квадраткорень из 1 по модулю n, '', то есть число, не равное 1 или n - 1, квадрат которого равен 1 по модулю n.

Это говорит о том, что дополнительная проверка добавляется внутрифункция expmod.Это может быть то, что вы упустили из виду.

Можно доказать, что если такой нетривиальный квадратный корень из 1 существует, то n не простое число.

Пойдемпо этому подробно.Нетривиальный квадратный корень из 1 будет таким числом x, что x ^ 2 = 1 (mod n).и x не равен 1 или -1.

Почему один из них указывает на то, что n не является простым?

Мы знаем, что x ^ 2 - 1 = (x - 1) (x + 1) и (работая по модулю n) оба x-1 и x + 1 не равны нулю, но их произведение равно нулю.Это подразумевает, что у нас есть составной модуль, и вы можете вычислить его, взяв GCD из этих двух значений.

Можно также доказать, что если n - нечетное число, которое не является простым, топо крайней мере, для половины чисел a

Это опять говорит о добавлении внутреннего теста к квадрату ветви функции expmod.

Измените процедуру expmod, чтобы сигнализировать, обнаруживает ли он нетривиальный квадратный корень из 1, и используйте его для реализации теста Миллера-Рабина с процедурой, аналогичной fermat-test.Проверьте вашу процедуру, протестировав различные известные простые и не простые числа.Подсказка: один из удобных способов сделать сигнал expmod вернувшимся 0. 0. 1040 *

Надеюсь, это поможет!Спросите, если вам нужно больше указаний.