Símbolo de jacobi

El símbolo de Jacobi es una generalización del símbolo de Legendre. Introducido por Jacobi en 1837, 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 en pruebas de primalidad y factorización de enteros; estos 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/n) se define como el producto de los símbolos de Legendre correspondientes a los factores primos de n:

()an)=()ap1)α α 1()ap2)α α 2⋯ ⋯ ()apk)α α k,{displaystyle left({frac {n}right)=left({frac} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}}} {fnMicrosoft Sans Serif} ¿Por qué? ¿Qué?

dónde

n=p1α α 1p2α α 2⋯ ⋯ pkα α k{displaystyle ################################################################################################################################################################################################################################################################ {fnMicrosoft Sans Serif} ¿Qué? ¿Qué? ¿Qué?

es la descomposición en factores primos de n.

El símbolo de Legendre (a /p) se define para todos los números enteros a y todos los primos impares p por

()ap)={}0sia↑ ↑ 0()modp),1sia≢0()modp)y para algunos enterosx:: a↑ ↑ x2()modp),− − 1sia≢0()modp)y no hay talx.{displaystyle left({frac {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft} {fnMicrosoft Sans Serif} {fnMicrosoft {fnMicrosoft Sans Serif}fnMicrosoft}fnMicrosoft}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}

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/n ) 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.

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 impar positivo.

1. Si n es (un extraño) primo, entonces el símbolo Jacobi ()a/n) es igual a (y escrito lo mismo que) el símbolo Legendre correspondiente.

2. Si a ↑ b (modelo) n), entonces ()an)=()bn)=()a± ± m⋅ ⋅ nn){displaystyle left({frac {n}right)=left({frac {n}right)=left({frac)=frac {apm mcdot n}right)}

3. ()an)={}0sigcd()a,n)ل ل 1,± ± 1sigcd()a,n)=1.{displaystyle left({frac {n}right)={begin{cases}0 limit{text{if}}gcd(a,n)neq 1,\\pm 1 limite{text{if }gcd(a,n)=1.end{cases}}}}}}}

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

4. ()abn)=()an)()bn),Así que...()a2n)=()an)2=1o0.{displaystyle left({frac {ab}}right)=left({frac} {fn}derecha)left({frac {b} {n}right),quad {text{so }left({frac {fn}{n}}}}right)=left({frac} {fn} {fn}fnMicrosoft Sans Serif}

5. ()amn)=()am)()an),Así que...()an2)=()an)2=1o0.{displaystyle left({frac {a}{mn}right)=left({frac {a}{m}}right)left({frac {n}}right),quad {text{so}left({frac {frac} {frac} {fn}}}fn}f}f}}f}f}f}f}f}fnh00}f}f}f}f}f}fnh00}fnh00}fnh00}fnh00}f}f}f}fnhnh00}f}fnh00}fnhnh}fnh00}fnh00}fnh00}f}fnh}fnh}fnh00}fnh00}s00}fnh00}f}fnh Está bien. {fn} {fn}fnMicrosoft Sans Serif}

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

6. ()mn)()nm)=()− − 1)m− − 12⋅ ⋅ n− − 12={}1sin↑ ↑ 1()mod4)om↑ ↑ 1()mod4),− − 1sin↑ ↑ m↑ ↑ 3()mod4){displaystyle left({frac {n}right)left({frac} [n} {m}right)=(-1)^{tfrac {m-1}{2}cdot {tfrac} {n-1}{2}}={begin{cases}1 {text{if} }nequiv 1{pmod {4}{text{ or }mequiv 1{pmod {4}},\\1 âtext{if}nequiv mequiv 3{pmod {4}end{cases}}

y sus complementos

7. ()− − 1n)=()− − 1)n− − 12={}1sin↑ ↑ 1()mod4),− − 1sin↑ ↑ 3()mod4),{displaystyle left({frac {-1}{n}right)=(-1)^{tfrac {n-1}{2}={begin{cases}1 }nequiv 1{pmod {4}},\1 golpe{if}nequiv 3{pmod {4}},end{cases}},

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

8. ()2n)=()− − 1)n2− − 18={}1sin↑ ↑ 1,7()mod8),− − 1sin↑ ↑ 3,5()mod8).{displaystyle left({frac {2}{n}right)=(-1)^{tfrac {n^{2}-1}{8}={begin{cases}1 sentimiento{if} }nequiv 1,7{pmod {8}},\1 golpe{if}nequiv 3,5{pmod {8}}}end{cases}}

Combinando las propiedades 4 y 8 se obtiene:

9. ()2an)=()2n)()an)={}()an)sin↑ ↑ 1,7()mod8),− − ()an)sin↑ ↑ 3,5()mod8).{displaystyle left({frac {2a}{n}right)=left({frac {2}{n}right)left({frac] {}{n}right)={begin{cases}left({frac] {a}{n}right) }nequiv 1,7{pmod {8},\{-left({frac {}{n}right)} {text{if}nequiv 3,5{pmod {8}}end{cases}}}}}

Como el símbolo de Legendre:

• Si ()a/n)= 1 - entonces a es un modulo no residual cuadrático n.

• Si a es un modulo de residuos cuadráticos n y gcd(a,n= 1, entonces ()a/n)= 1.

Pero, a diferencia del símbolo de Legendre:

Si ()a/n)= 1 entonces a puede o no ser un modulo de residuos cuadráticos 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 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 /n) es un carácter de Dirichlet para el módulo n.

Cálculo del símbolo de Jacobi

Las fórmulas anteriores conducen a un algoritmo O(log a log b) eficiente para calcular el símbolo de Jacobi, análogo al algoritmo de Euclides para encontrar el mcd de dos números. (Esto no debería sorprender a la luz de la regla 2).

1. Reducir el "numerador" modulo el "denominador" usando la regla 2.
2. Extraiga cualquier "numerador" usando la regla 9.
3. Si el "numerador" es 1, reglas 3 y 4 dan un resultado de 1. Si el "numerador" y "denominador" no son coprime, la regla 3 da un resultado de 0.
4. De lo contrario, el "numerador" y "denominador" ahora son extraños enteros coprime positivos, por lo que podemos cambiar el símbolo usando la regla 6, luego volver al paso 1.

Implementación en Lua

función jacobi()n, k) afirmación()k ■ 0 y k % 2 == 1) n = n % k t = 1 mientras n ~= 0 do mientras n % 2 == 0 do n = n / 2 r = k % 8 si r == 3 o r == 5 entonces t = -t final final n, k = k, n si n % 4 == 3 y k % 4 == 3 entonces t = -t final n = n % k final si k == 1 entonces retorno t más retorno 0 finalfinal

Implementación en C++

// a/n está representado como (a,n)int jacobi()int a, int n) {} afirmación()n ■ 0 " n%2 == 1); //Paso 1 a = a % n; int t = 1; int r; //Paso 3 mientras ()a ! 0) {} //Paso 2 mientras ()a % 2 == 0) {} //Desvío rápido por 2 usando un poco de cambio a = a > 1; r = n % 8; si ()r == 3 Silencio r == 5) {} t = -t; } } //Paso 4 r = n; n = a; a = r; si ()a % 4 == 3 " n % 4 == 3) {} t = -t; } a = a % n; } si ()n == 1) {} retorno t; } más {} retorno 0; }}

Ejemplo de cálculos

El símbolo de Legendre (a /p) 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 complementarias para ( −1/p) y (2/p) y multiplicatividad del "numerador").

Problema: dado que 9907 es primo, calcule (1001/9907).

Uso del símbolo de Legendre

()10019907)=()79907)()119907)()139907).()79907)=− − ()99077)=− − ()27)=− − 1.()119907)=− − ()990711)=− − ()711)=()117)=()47)=1.()139907)=()990713)=()113)=1.()10019907)=− − 1.{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnMicrosoft} {fnMicrosoft} {fnMicrosoft} {fnMicros} {fnMicros} {fnMicrosoft} {fnMicrosoft}} {c}}}}} {b}}}}f}} {cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccH0}ccc}}}cc {4}{7}right)=1.\left({frac {13}{9907}right) âleft({frac {9907}{13}}right)=left({frac {1}{13}right)=1.\left({frac {frac {1001}{9907}right)}right)=1.

Uso del símbolo de Jacobi

()10019907)=()99071001)=()8981001)=()21001)()4491001)=()4491001)=()1001449)=()103449)=()449103)=()37103)=()10337)=()2937)=()3729)=()829)=()229)3=− − 1.{fnMicrosoft Sans Serif}

La diferencia entre los dos cálculos es que cuando se usa el símbolo de Legendre, el "numerador" tiene que tenerse en cuenta en las potencias principales antes de que se invierta el símbolo. Esto hace que el cálculo que usa el símbolo de Legendre sea significativamente más lento que el que usa el símbolo de Jacobi, ya que no se conoce ningún algoritmo de tiempo polinomial para factorizar números enteros. De hecho, esta es la razón por la que Jacobi introdujo el símbolo.

Pruebas de primalidad

Hay otra diferencia entre los símbolos de Jacobi y Legendre. Si se utiliza la fórmula del criterio de Euler módulo un número compuesto, el resultado puede o no ser el valor del símbolo de Jacobi y, de hecho, puede que ni siquiera sea −1 o 1. Por ejemplo,

()1945)=1y1945− − 12↑ ↑ 1()mod45).()821)=− − 1pero821− − 12↑ ↑ 1()mod21).()521)=1pero521− − 12↑ ↑ 16()mod21).{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft} {} {fnMicrosoft} {f} {fnMicrosoft} {fnMicrosoft}}}} {fnMicrosoft} {fnMicrosoft}} {fnMicrosoft}}}f}}}}fnMicrom}}}f}fnMinMinMicrosoft}fnMicrosoft}}fnMicrosoft} {fnMicrocfnun}fnun}fnun}}}}fnMicrosoft} {fnun}fnun}}fnMicrosoft {fnMicrosoft}fnun}}fnMicrosoft}fnun}f}}fnMi

Entonces, si no se sabe si un número n es primo o compuesto, podemos elegir un número aleatorio a, calcular el símbolo de Jacobi (a/n) y compáralo 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 para la prueba de primalidad probabilística de Solovay-Strassen y mejoras como la prueba de primalidad de Baillie-PSW y la prueba de primalidad de Miller-Rabin.

Como uso indirecto, es posible utilizarlo como rutina de detección de errores durante la ejecución de la prueba de primalidad Lucas-Lehmer que, incluso en hardware moderno, puede tomar semanas para completar al procesar los números de Mersenne sobre 282,589,933− − 1{displaystyle {begin{aligned}2}{82,589,933}-1end{aligned}} (el mayor conocido Mersenne de diciembre de 2018). En casos nominales, el símbolo Jacobi:

()si− − 2Mp)=− − 1iل ل 0{displaystyle {begin{aligned}left({frac {fnMicrosoft Sans Serif}

Esto también tiene para el residuo final sp− − 2{displaystyle {begin{aligned}s_{p-2}end{aligned}} y por lo tanto se puede utilizar como una verificación de validez probable. Sin embargo, si un error ocurre en el hardware, hay un 50% de probabilidad de que el resultado se convertirá en 0 o 1 en lugar, y no cambiará con términos posteriores de s{displaystyle {begin{aligned}send{aligned}} (a menos que ocurra otro error y lo cambie a -1).