Путать на Миллер-Рабин

Question

В качестве упражнения для себя я применяю тест Миллера-Рабина. (Работает через SICP). Я понимаю маленькую теорему Ферма и смог успешно ее реализовать. В испытании Миллера-Рабина меня запутали, это бизнес "1 mod n". Разве 1 ​​mod n (n - случайное целое число) не всегда 1? Поэтому я не понимаю, что такое "нетривиальный квадратный корень из 1 по модулю n", поскольку, на мой взгляд, "1 mod n" всегда равно 1 при работе с целочисленными значениями. Что мне не хватает?

Answer 1

1 соответствует 9 мод 8, так что 3 является нетривиальным квадратным корнем из 1 мод 8.

вы работаете не с отдельными числами, а с множествами эквивалентности. [m]n это набор всех чисел x такой, что x соответствует m модификация n, Любая вещь, которая связана с любым элементом этого набора, является квадратным корнем m по модулю n,

учитывая любой n, у нас есть набор целых чисел по модулю n, который мы можем записать как Zn, это множество (множеств) [1]n, [2]n,...,[n]n, Каждое целое число лежит в одном и только одном из этих множеств. мы можем определить сложение и умножение на этом множестве [a]n + [b]n = [a + b]n и аналогично для умножения. Таким образом, квадратный корень [1]n является (п элемент) [b]n такой, что [b*b]n = [1]n,

На практике, однако, мы можем сопоставить m с [m]n и обычно выбирают уникальный элемент, m' из [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

Answer 2

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

"нетривиальный квадратный корень из 1 по модулю n", то есть число, не равное 1 или n - 1, чей квадрат равен 1 по модулю n

Где я считаю, это должно сказать:

чья площадь совпадает с 1 по модулю n

Answer 3

Вот почему формулировка была для нетривиального квадратного корня из 1. 1 является тривиальным квадратным корнем из 1 для любого модуля n.

17 является нетривиальным квадратным корнем из 1, mod 144. Таким образом, 17^2 = 289, что соответствует 1 модулю 144. Если n простое, то 1 и n-1 являются двумя квадратными корнями из 1, и они единственные два таких корня. Однако для составного n обычно есть несколько квадратных корней. При n = 144 квадратные корни составляют {1,17,55,71,73,89,127,143}.