Как упражнение для себя, я реализую тест Миллера-Рабина. (Работа через SICP). Я понимаю небольшую теорему Ферма и смог успешно ее реализовать. Часть, с которой я сталкиваюсь в тесте Миллера-Рабина, - это бизнес "1 мод". Разве 1 mod n (n не является случайным целым) всегда 1? Поэтому я смущен тем, что может быть "нетривиальным квадратным корнем из 1 по модулю n", поскольку в моем уме "1 mod n" всегда имеет значение 1 при работе с целыми значениями. Что мне не хватает?
Смущенный Миллер-Рабином
Ответ 1
1 соответствует конгруэнту 9 mod 8, поэтому 3 - нетривиальный квадратный корень из 1 mod 8.
то, с чем вы работаете, - это не отдельные числа, а множества эквивалентности. [m]n - это set всех чисел x, для которых x соответствует m mod n. Любая вещь, которая sqaures для любого элемента этого набора, является квадратным корнем из m по модулю n.
при любом n, мы имеем множество целых чисел по модулю n, которое мы можем написать как Zn. это множество (множеств) [1]n, [2]n,..., [n]n. Каждое целое число лежит в одном и только одном из этих множеств. мы можем определить сложение и умножение на этом множестве на [a]n + [b]n = [a + b]n и аналогично для умножения. Таким образом, квадратный корень из [1]n является (n элементом) [b]n таким, что [b*b]n = [1]n.
На практике, однако, мы можем conflate m с [m]n и обычно выбираем уникальный элемент m' of [m]n такой, что 0 <= m' < n как наш "представительский" элемент: это то, о чем мы обычно думаем как m mod n. но важно помнить, что мы "злоупотребляем обозначениями", как говорят математики.
здесь некоторый (неидиоматический) код python, поскольку у меня нет схемы-интерпретатора ATM:
>>> def roots_of_unity(n):
... roots = []
... for i in range(n):
... if i**2 % n == 1:
... roots.append(i)
... return roots
...
>>> roots_of_unity(4)
[1, 3]
>>> roots_of_unity(8)
[1, 3, 5, 7]
>>> roots_of_unity(9)
[1, 8]
Итак, в частности (смотря на последний пример), 17 является корнем из единицы по модулю 9. Действительно, 17 ^ 2 = 289 и 289% 9 = 1. Возвращаясь к нашим предыдущим обозначениям [8]9 = [17]9 и ([17]9)^2 = [1]9
Ответ 2
Вот почему формулировка была для NONTRIVIAL квадратного корня из 1. 1 является тривиальным квадратным корнем из 1 для любого модуля n.
17 является нетривиальным квадратным корнем из 1, mod 144. Таким образом, 17 ^ 2 = 289, что соответствует 1 mod 144. Если n является простым, то 1 и n-1 являются двумя квадратными корнями из 1, и они являются единственными двумя такими корнями. Однако для составного n обычно имеется несколько квадратных корней. При n = 144 квадратные корни составляют {1,17,55,71,73,89,127,143}.
Ответ 3
Я считаю, что недоразумение исходит из определения, которое книга дает о нетривиальном корне:
a "нетривиальный квадратный корень из 1 по модулю n", то есть число, не равное 1 или n - 1 , квадрат которого равен 1 по модулю n
Где я считаю, он должен сказать:
квадрат которого конгруэнтный до 1 по модулю n