algorithm - Confundido en Miller-Rabin

primes sicp

Question

Como ejercicio para mí, estoy implementando la prueba de Miller-Rabin. (Trabajando a través del SICP). Entiendo el pequeño teorema de Fermat y pude implementarlo con éxito. La parte a la que me estoy engañando en la prueba de Miller-Rabin es este asunto de "1 mod n". ¿No es 1 mod n (n es algún entero aleatorio) siempre 1? Así que estoy confundido sobre lo que podría ser una "raíz cuadrada no trivial de 1 módulo n" ya que en mi opinión "1 mod n" siempre es 1 cuando se trata de valores enteros. ¿Qué me estoy perdiendo?

Answer 1

1 es congruente con 9 mod 8, por lo que 3 es una raíz cuadrada no trivial de 1 mod 8.

Con lo que estás trabajando no son números individuales, sino conjuntos de equivalencia. [m]n es el conjunto de todos los números x modo que x es congruente con m mod n . Cualquier cosa que se adapte a cualquier elemento de este conjunto es una raíz cuadrada de m módulo n .

dado cualquier n , tenemos el conjunto de enteros módulo n que podemos escribir como Zn . este es el conjunto (de conjuntos) [1]n , [2]n , ..., [n]n . Cada entero está en uno y solo uno de esos conjuntos. podemos definir la suma y la multiplicación en este conjunto mediante [a]n + [b]n = [a + b]n y de la misma manera para la multiplicación. Entonces, una raíz cuadrada de [1]n es un (n elemento de) [b]n tal que [b*b]n = [1]n .

Sin embargo, en la práctica, podemos combinar m con [m]n y normalmente elegir el elemento único, m'' de [m]n , de manera que 0 <= m'' < n sea ​​nuestro elemento ''representativo'': esto es lo que generalmente pensamos como el m mod n . pero es importante tener en cuenta que estamos ''abusando de la notación'' como dicen los matemáticos.

Aquí hay un código de Python (no idiomático) ya que no tengo un cajero automático de intérprete de esquema:

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

Entonces, en particular (mirando el último ejemplo), 17 es una raíz de unidad módulo 9. de hecho, 17 ^ 2 = 289 y 289% 9 = 1. volviendo a nuestra notación anterior [8]9 = [17]9 y ([17]9)^2 = [1]9

Answer 2

Creo que el malentendido proviene de la definición que da el libro sobre la raíz no trivial:

una "raíz cuadrada no trivial de 1 módulo n", es decir, un número que no es igual a 1 o n - 1 cuyo cuadrado es igual a 1 módulo n

Donde creo que debería decir:

cuyo cuadrado es congruente a 1 modulo n

Answer 3

Es por eso que la redacción fue para una raíz cuadrada NO TRIVIAL de 1. 1 es una raíz cuadrada trivial de 1, para cualquier módulo n.

17 es una raíz cuadrada no trivial de 1, mod 144. Así, 17 ^ 2 = 289, que es congruente con 1 mod 144. Si n es primo, entonces 1 y n-1 son las dos raíces cuadradas de 1, y Son las dos únicas raíces de este tipo. Sin embargo, para el compuesto n generalmente hay múltiples raíces cuadradas. Con n = 144, las raíces cuadradas son {1,17,55,71,73,89,127,143}.