Confundido en Miller-Rabin
-
03-10-2019 - |
Pregunta
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?
Solución
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
Otros consejos
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}.
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