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

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


algorithm primes prime-factoring sicp primality-test
person hraesvelgr    schedule 17.09.2010    source источник
comment
Этот вопрос не по теме, потому что это не вопрос программирования   -  person JK.    schedule 05.06.2014

Ответы (3)


arrow_upward
27
arrow_downward

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 представляет собой (n элемент) [b]n такой, что [b*b]n = [1]n.

Однако на практике мы можем объединить m с [m]n и обычно выбираем уникальный элемент, m' из [m]n, так что 0 <= m' < n является нашим «репрезентативным» элементом: это то, что мы обычно думаем как m mod n. но важно помнить, что мы «злоупотребляем обозначениями», как говорят математики.

вот некоторый (неидиоматический) код Python, поскольку у меня нет банкомата интерпретатора схемы:

>>> 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

person aaronasterling    schedule 17.09.2010

arrow_upward
12
arrow_downward

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

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

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

квадрат которого конгруэнтен 1 по модулю n

person sfotiadis    schedule 26.07.2014
comment
Я разделял ту же путаницу, что и ОП, и это разъяснение имело все значение. Принятый ответ великолепен, но этот ответ устраняет источник путаницы. - person Nadim Hussami; 21.06.2017
comment
Вот и сентябрь 2020 года, и меня тоже просто смутила формулировка. Для кого-то вроде меня, у которого мало математики, можно ли также сформулировать, чей квадрат по модулю n равен 1? - person Tony; 12.09.2020

arrow_upward
10
arrow_downward

Вот почему формулировка была для НЕТРИВИАЛЬНОГО квадратного корня из 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}.

person Community    schedule 17.09.2010