Тест Миллера-Рабина (SICP 1.28) - PullRequest
Новая
       74

Тест Миллера-Рабина (SICP 1.28)

2 голосов
/ 17 мая 2019

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

Чтобы проверить простоту числа n с помощью теста Миллера-Рабина, мы выбираем случайное число a меньше n и повышаем a до (n - 1) st power по модулю n с использованием процедуры expmod.Однако всякий раз, когда мы выполняем шаг возведения в квадрат в expmod, мы проверяем, обнаружили ли мы «нетривиальный квадратный корень из 1 по модулю n », то есть число неравно 1 или n - 1 , квадрат которого равен 1 по модулю n .

Можно доказать, что если такой нетривиальный квадратный корень из 1 существует, то n не является простым.Также можно доказать, что если n нечетное число, которое не является простым, то, по крайней мере, для половины чисел a , вычисляя a n-1 , таким образом, обнаружит нетривиальный квадратный корень из 1 по модулю n .(Вот почему тест Миллера-Рабина не может быть одурачен.)

Измените процедуру expmod, чтобы сигнализировать, если она обнаруживает нетривиальный квадратный корень из 1 , и используйте его для реализацииТест Миллера-Рабина с процедурой, аналогичной fermat-test.Проверьте вашу процедуру, протестировав различные известные простые и не простые числа.Подсказка: один из удобных способов сделать сигнал expmod состоит в том, чтобы он возвращал 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.Вы проверяете число перед квадратом или после квадрата?Я не знаю, прочитав вопрос.

1 Ответ

1 голос
/ 17 мая 2019

Я решил это, используя оригинальное определение expmod внутри expmod-signal.Где-то в моих тестах expmod-signal естественно возвращал ноль и возился с тестами.Я неправильно понял функцию проверки, «квадрат которой равен 1 по модулю n» означает проверку, если a^2 % m = 1.Эта функция проверки работает так, чтобы возвращать 0, если аргумент является нетривиальным квадратным корнем из 1 mod n, и возвращать аргумент в противном случае.Если он возвращает ноль, ноль распространяется через остаток от expmod-signal и возвращается. 

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