Confundido en Miller-Rabin

Question

A modo de ejercicio para mí, estoy poniendo en práctica la prueba de Miller-Rabin. (Trabajo a través de SICP). Entiendo pequeño teorema de Fermat y fue capaz de implementar con éxito eso. La parte que me voy a tropezar en la prueba de Miller-Rabin es este negocio "1 mod n". No es 1 mod n (siendo n un entero aleatorio) siempre es 1? Así que estoy confundido por lo que es una "raíz cuadrada no trivial de 1 módulo n" podría ser puesto en mi mente "1 mod n" es siempre 1 cuando se trata de valores enteros. ¿Qué me falta?

Answer 1

1 es congruente a 9 mod 8 de modo 3 es una raíz cuadrada trivial no de 1 mod 8.

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

dado ninguna n, tenemos el conjunto de los enteros módulo n, que podemos escribir como Zn. este es el conjunto (de juegos) [1]n, [2]n, ..., [n]n. Cada entero se encuentra en uno y sólo uno de esos conjuntos. podemos definir la suma y la multiplicación de este conjunto por [a]n + [b]n = [a + b]n y lo mismo para la multiplicación. Por lo que una raíz cuadrada de [1]n es un (elemento 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 notación' como dicen los matemáticos.

He aquí algunos (no-idiomática) código Python, ya que no disponen de un sistema ATM 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í que, en particular, (mirando el último ejemplo), 17 es una raíz de la unidad de 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

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. Por lo tanto 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 los dos únicos raíces. Sin embargo, para n compuesto 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:

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

Cuando yo creo que debería decir:

cuyo cuadrado es congruente a 1 módulo n