El símbolo de Jacobi es una generalización del símbolo de Legendre . Introducido por Jacobi en 1837, [1] es de interés teórico en la aritmética modular y otras ramas de la teoría de números , pero su uso principal es en la teoría de números computacional , especialmente las pruebas de primalidad y la factorización de enteros ; éstos, a su vez, son importantes en criptografía .
k norte | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | ||||||||||||||||
3 | 0 | 1 | −1 | ||||||||||||||
5 | 0 | 1 | −1 | −1 | 1 | ||||||||||||
7 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | ||||||||||
9 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | ||||||||
11 | 0 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | ||||||
13 | 0 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | ||||
15 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | −1 | 1 | 0 | 0 | −1 | 0 | −1 | −1 | ||
17 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 |
Definición
Para cualquier número entero una y cualquier número entero impar positivo n , el símbolo Jacobi (a/norte) se define como el producto de los símbolos de Legendre correspondientes a los factores primos de n :
dónde
es la factorización prima de n .
El símbolo de Legendre (a/pag) Se define para todos los números enteros a y todos los primos impares p por
Siguiendo la convención normal para el producto vacío, (a/1) = 1.
Cuando el argumento inferior es un primo impar, el símbolo de Jacobi es igual al símbolo de Legendre.
Tabla de valores
La siguiente es una tabla de valores del símbolo de Jacobi (k/norte) con n ≤ 59, k ≤ 30, n impar.
k norte | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
3 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 |
5 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 |
7 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 |
9 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
11 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 0 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 0 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 |
13 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | 0 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | 0 | 1 | −1 | 1 | 1 |
15 | 1 | 1 | 0 | 1 | 0 | 0 | −1 | 1 | 0 | 0 | −1 | 0 | −1 | −1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | −1 | 1 | 0 | 0 | −1 | 0 | −1 | −1 | 0 |
17 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 |
19 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 0 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 |
21 | 1 | −1 | 0 | 1 | 1 | 0 | 0 | −1 | 0 | −1 | −1 | 0 | −1 | 0 | 0 | 1 | 1 | 0 | −1 | 1 | 0 | 1 | −1 | 0 | 1 | 1 | 0 | 0 | −1 | 0 |
23 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | 0 | 1 | 1 | 1 | 1 | −1 | 1 | −1 |
25 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
27 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 |
29 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | 0 | 1 |
31 | 1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 |
33 | 1 | 1 | 0 | 1 | −1 | 0 | −1 | 1 | 0 | −1 | 0 | 0 | −1 | −1 | 0 | 1 | 1 | 0 | −1 | −1 | 0 | 0 | −1 | 0 | 1 | −1 | 0 | −1 | 1 | 0 |
35 | 1 | −1 | 1 | 1 | 0 | −1 | 0 | −1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | −1 | −1 | 0 | 0 | −1 | −1 | −1 | 0 | −1 | 1 | 0 | 1 | 0 |
37 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 |
39 | 1 | 1 | 0 | 1 | 1 | 0 | −1 | 1 | 0 | 1 | 1 | 0 | 0 | −1 | 0 | 1 | −1 | 0 | −1 | 1 | 0 | 1 | −1 | 0 | 1 | 0 | 0 | −1 | −1 | 0 |
41 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | −1 |
43 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 |
45 | 1 | −1 | 0 | 1 | 0 | 0 | −1 | −1 | 0 | 0 | 1 | 0 | −1 | 1 | 0 | 1 | −1 | 0 | 1 | 0 | 0 | −1 | −1 | 0 | 0 | 1 | 0 | −1 | 1 | 0 |
47 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 |
49 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
51 | 1 | −1 | 0 | 1 | 1 | 0 | −1 | −1 | 0 | −1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | −1 | 1 | 0 | 1 | −1 | 0 | −1 | 1 | 0 |
53 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 |
55 | 1 | 1 | −1 | 1 | 0 | −1 | 1 | 1 | 1 | 0 | 0 | −1 | 1 | 1 | 0 | 1 | 1 | 1 | −1 | 0 | −1 | 0 | −1 | −1 | 0 | 1 | −1 | 1 | −1 | 0 |
57 | 1 | 1 | 0 | 1 | −1 | 0 | 1 | 1 | 0 | −1 | −1 | 0 | −1 | 1 | 0 | 1 | −1 | 0 | 0 | −1 | 0 | −1 | −1 | 0 | 1 | −1 | 0 | 1 | 1 | 0 |
59 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 |
Propiedades
Los siguientes hechos, incluso las leyes de reciprocidad, son deducciones sencillas de la definición del símbolo de Jacobi y las propiedades correspondientes del símbolo de Legendre. [2]
El símbolo de Jacobi se define solo cuando el argumento superior ("numerador") es un número entero y el argumento inferior ("denominador") es un número entero positivo impar.
- 1. Si n es primo (impar), entonces el símbolo de Jacobi (a/norte) es igual a (y se escribe igual que) el símbolo de Legendre correspondiente.
- 2. Si a ≡ b (mod n ) , entonces
- 3.
Si el argumento superior o inferior es fijo, el símbolo de Jacobi es una función completamente multiplicativa en el argumento restante: [ se necesita más explicación ]
- 4.
- 5.
La ley de reciprocidad cuadrática : si m y n son números primos entre sí impares positivos, entonces
- 6.
y sus suplementos
- 7. ,
y
- 8.
La combinación de las propiedades 4 y 8 da:
- 9.
Como el símbolo de Legendre:
- Si (a/norte) = −1 entonces a es un módulo n no residual cuadrático .
- Si una es un residuo cuadrático módulo n y gcd ( a , n ) = 1, entonces (a/norte) = 1.
Pero, a diferencia del símbolo de Legendre:
- Si (a/norte) = 1 entonces a puede o no ser un residuo cuadrático módulo n .
Esto es porque para un para ser un modulo residuo cuadrático n , que tiene que ser un residuo cuadrático modulo cada factor primo de n . Sin embargo, el símbolo de Jacobi es igual a uno si, por ejemplo, a es un módulo sin residuos exactamente dos de los factores primos de n .
Aunque el símbolo de Jacobi no se puede interpretar uniformemente en términos de cuadrados y no cuadrados, se puede interpretar uniformemente como el signo de una permutación por el lema de Zolotarev .
El símbolo de Jacobi (a/norte) es un carácter de Dirichlet al módulo n .
Cálculo del símbolo de Jacobi
Las fórmulas anteriores conducen a un algoritmo O (log a log b ) [3] eficiente para calcular el símbolo de Jacobi, análogo al algoritmo euclidiano para encontrar el mcd de dos números. (Esto no debería sorprender a la luz de la regla 2.)
- Reducir el módulo "numerador" el "denominador" usando la regla 2.
- Extrae cualquier "numerador" par usando la regla 9.
- Si el "numerador" es 1, las reglas 3 y 4 dan un resultado de 1. Si el "numerador" y el "denominador" no son coprimos, la regla 3 da un resultado de 0.
- De lo contrario, el "numerador" y el "denominador" ahora son números enteros primos coprimos positivos impares, por lo que podemos voltear el símbolo usando la regla 6 y luego regresar al paso 1.
Implementación en Lua
función jacobi ( n , k ) aseverar ( k > 0 y k % 2 == 1 ) n = n % k t = 1 mientras n ~ = 0 hacer mientras n % 2 == 0 hacer n = n / 2 r = k % 8 si r == 3 o r == 5 entonces t = - t end end n , k = k , n si n % 4 == 3 y k % 4 == 3 entonces t = - t end n = n % k end si k == 1 entonces retorna t si no retorna 0 end end
Ejemplo de calculos
El símbolo de Legendre (a/pag) solo se define para primos impares p . Obedece las mismas reglas que el símbolo de Jacobi (es decir, reciprocidad y las fórmulas complementarias para (−1/pag) y (2/pag) y multiplicatividad del "numerador".)
Problema: dado que 9907 es primo, calcule (1001/9907) .
Usando el símbolo de Legendre
Usando el símbolo de Jacobi
La diferencia entre los dos cálculos es que cuando se usa el símbolo de Legendre, el "numerador" debe factorizarse en potencias primas antes de que se invierta el símbolo. Esto hace que el cálculo usando el símbolo de Legendre sea significativamente más lento que el que usa el símbolo de Jacobi, ya que no existe un algoritmo de tiempo polinomial conocido para factorizar números enteros. [4] De hecho, esta es la razón por la que Jacobi introdujo el símbolo.
Prueba de primordialidad
Hay otra forma en que los símbolos de Jacobi y Legendre difieren. Si la fórmula del criterio de Euler se usa módulo un número compuesto, el resultado puede ser o no el valor del símbolo de Jacobi, y de hecho puede que ni siquiera sea -1 o 1. Por ejemplo,
Entonces, si se desconoce si un número n es primo o compuesto, podemos elegir un número aleatorio a , calcular el símbolo de Jacobi (a/norte) y compararlo con la fórmula de Euler; si difieren módulo n , entonces n es compuesto; si tienen el mismo residuo módulo n para muchos valores diferentes de a , entonces n es "probablemente primo".
Ésta es la base para la prueba de primalidad probabilística de Solovay-Strassen y refinamientos como la prueba de primalidad de Baillie-PSW y la prueba de primaria de Miller-Rabin .
Como uso indirecto, es posible usarlo como una rutina de detección de errores durante la ejecución de la prueba de primalidad Lucas-Lehmer que, incluso en el hardware de computadora moderno, puede tardar semanas en completarse cuando se procesan los números de Mersenne por encima de(la prima de Mersenne más grande conocida a diciembre de 2018). En casos nominales, el símbolo de Jacobi:
Esto también es válido para el residuo final. y por lo tanto se puede utilizar como una verificación de validez probable. Sin embargo, si se produce un error en el hardware, existe un 50% de probabilidad de que el resultado se convierta en 0 o 1 y no cambie con los términos posteriores de (a menos que ocurra otro error y lo cambie de nuevo a -1).
Ver también
- Símbolo de Kronecker , una generalización del símbolo de Jacobi a todos los números enteros.
- Símbolo de residuo de poder , una generalización del símbolo de Jacobi a residuos de poderes superiores.
Notas
- ↑ Jacobi, CGJ (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Berlín : 127-136.
- ^ Irlanda y Rosen págs. 56–57 o Lemmermeyer pág. 10
- ^ Cohen, págs. 29–31
- ^ El tamiz de campo numérico , el algoritmo más rápido conocido, requiere
Referencias
- Cohen, Henri (1993). Un curso de teoría de números algebraicos computacionales . Berlín: Springer . ISBN 3-540-55640-0.
- Irlanda, Kenneth; Rosen, Michael (1990). Una introducción clásica a la teoría de números moderna (segunda edición) . Nueva York: Springer . ISBN 0-387-97329-X.
- Lemmermeyer, Franz (2000). Leyes de reciprocidad: de Euler a Eisenstein . Berlín: Springer . ISBN 3-540-66957-4.
- Shallit, Jeffrey (diciembre de 1990). "En el peor de los casos de tres algoritmos para calcular el símbolo de Jacobi" . Revista de Computación Simbólica . 10 (6): 593–61. doi : 10.1016 / S0747-7171 (08) 80160-5 . Informe técnico informático PCS-TR89-140.
- Vallée, Brigitte ; Lemée, Charly (octubre de 1998). Análisis de casos promedio de tres algoritmos para calcular el símbolo de Jacobi (Informe técnico). CiteSeerX 10.1.1.32.3425 .
- Eikenberry, Shawna Meyer; Sorenson, Jonathan P. (octubre de 1998). "Algoritmos eficientes para calcular el símbolo de Jacobi" (PDF) . Revista de Computación Simbólica . 26 (4): 509–523. CiteSeerX 10.1.1.44.2423 . doi : 10.1006 / jsco.1998.0226 .
enlaces externos
- Calcular símbolo de Jacobi muestra los pasos del cálculo.