Запутался на Миллер-Рабин

Question

Как упражнение для себя, я реализую тест Miller-Rabin. (Работает через SICP). Я понимаю маленькую теорему Ферма и смог успешно реализовать это. Часть, которую я побуждаю в тесте Miller-Rabin, это бизнес «1 мод n». Не 1 мод 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, У нас есть набор целых чисел модуля, который мы можем написать как Zn. Отказ Это набор (множеств) [1]n, [2]n, ... ,[n]n. Отказ Каждое целое число лежит в одном и только один из этих наборов. Мы можем определить дополнение и умножение на этот набор [a]n + [b]n = [a + b]n и также для умножения. Так что квадратный корень из [1]n это (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 является корнем Unity Modulo 9. Действительно, 17 ^ 2 = 289 и 289% 9 = 1. Возвращаясь к нашему предыдущему обозначению [8]9 = [17]9 а также ([17]9)^2 = [1]9

Answer 2

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

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

Answer 3

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

«Нетривиальный квадратный корень из 1 модуля N», то есть число не равно 1 или N - 1 Чья квадрат равна 1 модулю N

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

Чей квадрат есть конгруэнт до 1 модуля n