Símbolo de Jacobi

Generalización del símbolo de Legendre en la teoría de números

Carl Gustav Jacob Jacobi quien introdujo el símbolo.

Símbolo de Jacobi ( ⁠a/norte⁠ ) ​​para varios k (en la parte superior) y n (en el lado izquierdo). Solo se muestran 0 ≤ k < n , ya que debido a la regla (2) a continuación, cualquier otro k puede reducirse módulo n . Los residuos cuadráticos están resaltados en amarillo; tenga en cuenta que ninguna entrada con un símbolo de Jacobi de −1 es un residuo cuadrático, y si k es un residuo cuadrático módulo un coprimo n , entonces ( ⁠a/norte⁠ ) ​​= 1 , pero no todas las entradas con un símbolo de Jacobi de 1 (ver lasfilas n = 9 y n = 15 ) son residuos cuadráticos. Observe también que cuando n o k es un cuadrado, todos los valores son no negativos.

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 computacionales , especialmente en las pruebas de primalidad y la factorización de números enteros ; estas a su vez son importantes en criptografía .

Definición

Para cualquier entero a y cualquier entero impar positivo n , el símbolo de Jacobi ( ⁠a/norte⁠ ) ​​se define como el producto de los símbolos de Legendre correspondientes a los factores primos de n :

${\displaystyle \left({\frac {a}{n}}\right):=\left({\frac {a}{p_{1}}}\right)^{\alpha _{1}}\left({\frac {a}{p_{2}}}\right)^{\alpha _{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{\alpha _{k}},}$

dónde

${\displaystyle n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}}$

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

${\displaystyle \left({\frac {a}{p}}\right):=\left\{{\begin{array}{rl}0&{\text{if }}a\equiv 0{\pmod {p}},\\1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{array}}\right.}$

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 ( ⁠a/norte⁠ ) ​​con n  ≤ 59, k  ≤ 30, n impar.

Propiedades

Los siguientes hechos, incluso las leyes de reciprocidad, son deducciones directas 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 entero y el argumento inferior ("denominador") es un entero impar positivo.

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 ${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)}$

3. ${\displaystyle \left({\frac {a}{n}}\right)={\begin{cases}0&{\text{if }}\gcd(a,n)\neq 1,\\\pm 1&{\text{if }}\gcd(a,n)=1.\end{cases}}}$

Si el argumento superior o inferior es fijo, el símbolo de Jacobi es una función completamente multiplicativa en el argumento restante:

4. ${\displaystyle \left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right),\quad {\text{so }}\left({\frac {a^{2}}{n}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.}$

5. ${\displaystyle \left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right),\quad {\text{so }}\left({\frac {a}{n^{2}}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.}$

La ley de reciprocidad cuadrática : si m y n son números enteros coprimos positivos impares, entonces

6. ${\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}\cdot {\tfrac {n-1}{2}}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}}{\text{ or }}m\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}}$

y sus suplementos

7. , ${\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv 3{\pmod {4}},\end{cases}}}$

y ${\displaystyle \left({\frac {1}{n}}\right)=\left({\frac {n}{1}}\right)=1}$

8. ${\displaystyle \left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}1&{\text{if }}n\equiv 1,7{\pmod {8}},\\-1&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}}$

Combinando las propiedades 4 y 8 se obtiene:

9. ${\displaystyle \left({\frac {2a}{n}}\right)=\left({\frac {2}{n}}\right)\left({\frac {a}{n}}\right)={\begin{cases}\left({\frac {a}{n}}\right)&{\text{if }}n\equiv 1,7{\pmod {8}},\\{-\left({\frac {a}{n}}\right)}&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}}$

Al igual que el símbolo de Legendre:

• Si ( ⁠a/norte⁠ )  ​​= −1 entonces a es un residuo cuadrático módulo n .

• Si a es un residuo cuadrático módulo n y mcd ( a , n ) = 1, entonces ( ⁠a/norte⁠ )  ​​= 1.

Pero, a diferencia del símbolo de Legendre:

Si ( ⁠a/norte⁠ )  ​​= 1 entonces a puede ser o no un residuo cuadrático módulo n .

Esto se debe a que para que a sea un residuo cuadrático módulo n , tiene que ser un residuo cuadrático módulo cada factor primo de n . Sin embargo, el símbolo de Jacobi es igual a uno si, por ejemplo, a es un no residuo módulo exactamente dos de los factores primos de n .

Aunque el símbolo de Jacobi no puede interpretarse uniformemente en términos de cuadrados y no cuadrados, puede interpretarse uniformemente como el signo de una permutación según el lema de Zolotarev .

El símbolo de Jacobi ( ⁠a/norte⁠ ) ​​es un carácter de Dirichlet para el módulo n .

Calculando el 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 hallar el mcd de dos números. (Esto no debería sorprender a la luz de la regla 2).

1. Reduce el "numerador" módulo el "denominador" usando la regla 2.
2. Extrae cualquier "numerador" par usando la regla 9.
3. 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.
4. De lo contrario, el "numerador" y el "denominador" ahora son números enteros coprimos positivos impares, por lo que podemos invertir el símbolo usando la regla 6 y luego regresar al paso 1.

Además del código a continuación, Riesel ^[4] lo tiene en Pascal.

Implementación enLua

función  jacobi ( n ,  k )  assert ( 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  fin  fin  n ,  k  =  k ,  n  si  n  %  4  ==  3  y  k  %  4  ==  3  entonces  t  =  - t  fin  n  =  n  %  k  fin  si  k  ==  1  entonces  devuelve  t  de lo contrario  devuelve  0  fin fin

Implementación enC++

// a/n se representa como (a,n) int jacobi ( int a , int n ) { assert ( n > 0 && n % 2 == 1 ); //paso 1 a = a % n ; int t = 1 ; int r ; //paso 3 while ( a != 0 ) { //paso 2 while ( a % 2 == 0 ) { a /= 2 ; r = n % 8 ; if ( r == 3 || r == 5 ) { t = - t ; } } //paso 4 r = n ; n = a ; a = r ; if ( a % 4 == 3 && n % 4 == 3 ) { t = - t ; } a = a % n ; } if ( n == 1 ) { return t ; } de lo contrario { devolver 0 ; } }                                                                                                          

Ejemplo de cálculos

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, la reciprocidad y las fórmulas suplementarias para ( ⁠-1/pag⁠ ) ​​y ( ⁠2/pag) y la multiplicidad del "numerador".)

Problema: Dado que 9907 es primo, calcula ( ⁠1001/9907⁠ ) ​​.

Usando el símbolo de Legendre

${\displaystyle {\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right).\\\left({\frac {7}{9907}}\right)&=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1.\\\left({\frac {11}{9907}}\right)&=-\left({\frac {9907}{11}}\right)=-\left({\frac {7}{11}}\right)=\left({\frac {11}{7}}\right)=\left({\frac {4}{7}}\right)=1.\\\left({\frac {13}{9907}}\right)&=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1.\\\left({\frac {1001}{9907}}\right)&=-1.\end{aligned}}}$

Usando el símbolo de Jacobi

${\displaystyle {\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)\\&=\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)\\&=\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.\end{aligned}}}$

La diferencia entre ambos cálculos es que cuando se utiliza el símbolo de Legendre, el "numerador" debe factorizarse en potencias primos antes de invertir el símbolo. Esto hace que el cálculo con el símbolo de Legendre sea significativamente más lento que el que utiliza el símbolo de Jacobi, ya que no se conoce ningún algoritmo de tiempo polinomial para factorizar números enteros. ^[5] De hecho, esta es la razón por la que Jacobi introdujo el símbolo.

Prueba de primalidad

Existe otra forma en la que los símbolos de Jacobi y Legendre difieren. Si se utiliza la fórmula del criterio de Euler 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,

${\displaystyle {\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ and }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ but }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ but }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}}$

Entonces, si no se sabe si un número n es primo o compuesto, podemos elegir un número aleatorio a y 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 ".

Esta es la base de la prueba de primalidad probabilística de Solovay-Strassen y refinamientos como la prueba de primalidad de Baillie-PSW y la prueba de primalidad de Miller-Rabin .

Como uso indirecto, es posible utilizarlo como una rutina de detección de errores durante la ejecución de la prueba de primalidad de Lucas-Lehmer que, incluso en hardware de computadoras modernas, puede tardar semanas en completarse cuando se procesan números de Mersenne (el primo de Mersenne más grande conocido a diciembre de 2018). En casos nominales, el símbolo de Jacobi: ${\displaystyle {\begin{aligned}2^{82,589,933}-1\end{aligned}}}$

${\displaystyle {\begin{aligned}\left({\frac {s_{i}-2}{M_{p}}}\right)&=-1&i\neq 0\end{aligned}}}$

Esto también es válido para el residuo final y, por lo tanto, se puede utilizar como verificación de la validez probable. Sin embargo, si se produce un error en el hardware, existe un 50 % de posibilidades de que el resultado sea 0 o 1, y no cambie con los términos subsiguientes (a menos que se produzca otro error y vuelva a cambiarlo a -1). ${\displaystyle {\begin{aligned}s_{p-2}\end{aligned}}}$ ${\displaystyle {\begin{aligned}s\end{aligned}}}$

Véase 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 potencia , una generalización del símbolo de Jacobi a residuos de potencias superiores.

Notas

1. Jacobi, CGJ (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Berlín : 127-136.
2. Ireland & Rosen págs. 56-57 o Lemmermeyer pág. 10
3. Cohen, págs. 29-31
4. pág. 285
5. El tamiz de campos numéricos , el algoritmo más rápido conocido, requiere

   ${\displaystyle O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)}$

   Operaciones para factorizar n . Véase Cohen, pág. 495.

Referencias

• Cohen, Henri (1993). Un curso de teoría algebraica computacional de números . Berlín: Springer . ISBN. 3-540-55640-0.
• Ireland, 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.
• Riesel, Hans (1994), Números primos y métodos informáticos para factorización (segunda edición) , Boston: Birkhäuser, ISBN 0-8176-3743-5
• Shallit, Jeffrey (diciembre de 1990). "Sobre el peor caso de tres algoritmos para calcular el símbolo de Jacobi". Journal of Symbolic Computation . 10 (6): 593–61. doi : 10.1016/S0747-7171(08)80160-5 . Informe técnico de informática 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) . Journal of Symbolic Computation . 26 (4): 509–523. CiteSeerX  10.1.1.44.2423 . doi :10.1006/jsco.1998.0226.

Enlaces externos

• Calcular el símbolo de Jacobi Archivado 2016-10-05 en Wayback Machine muestra los pasos del cálculo.