Confundido en Miller-Rabin

Question

Como ejercicio para mí mismo, estoy implementando la prueba Miller-Rabin. (Trabajando a través del SICP). Comprendo el pequeño teorema de Fermat y pude implementarlo con éxito. La parte en la que estoy tropezando en la prueba de Miller-Rabin es este "1 mod n". ¿No es 1 mod n (n es un entero aleatorio) siempre 1? Así que estoy confundido con 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 de modo 3 es una raíz cuadrada no trivial de 1 mod 8.

lo que está trabajando no es números individuales, sino conjuntos de equivalencia. [m]n es el conjunto de todos los números x tal que x es congruente con m mod n. Cualquier cosa que sqaure a cualquier elemento de este conjunto es una raíz cuadrada de m modulo 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 se encuentra en uno y solo uno de esos conjuntos. podemos definir la suma y la multiplicación en este conjunto por [a]n + [b]n = [a + b]n y lo mismo para la multiplicación. Por lo tanto, una raíz cuadrada de [1]n es un (elemento n) de [b]n tal que [b*b]n = [1]n.

En la práctica, sin embargo, podemos combinar con m[m]n y normalmente elegir el elemento único, m' de [m]n tal que 0 <= m' < n como nuestro elemento 'representativa': esto es lo que normalmente consideramos 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 algunos (no-idiomática) código Python como no tengo un cajero automático de esquema intérprete:

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

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

Answer 2

Esa es la razón por la redacción es de 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 únicas dos de esas raíces. 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}.

Answer 3

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

una “raíz cuadrada no trivial de 1 módulo n”, es decir, un número 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 módulo n