Residuos cuadráticos

Entero que es un cuadrado perfecto módulo algún entero

En teoría de números , un número entero q se denomina residuo cuadrático módulo n si es congruente con un cuadrado perfecto módulo n ; es decir, si existe un número entero x tal que:

${\displaystyle x^{2}\equiv q{\pmod {n}}.}$

De lo contrario, q se denomina residuo cuadrático no módulo n .

Los residuos cuadráticos, que originalmente eran un concepto matemático abstracto de la rama de la teoría de números conocida como aritmética modular , ahora se utilizan en aplicaciones que van desde la ingeniería acústica hasta la criptografía y la factorización de números grandes .

Historia, convenciones y hechos elementales

Fermat , Euler , Lagrange , Legendre y otros teóricos de números de los siglos XVII y XVIII establecieron teoremas ^[1] y formularon conjeturas ^[2] sobre los residuos cuadráticos, pero el primer tratamiento sistemático es el § IV de las Disquisitiones Arithmeticae de Gauss (1801). El artículo 95 introduce la terminología "residuo cuadrático" y "no residuo cuadrático", y establece que si el contexto lo deja claro, se puede omitir el adjetivo "cuadrático".

Para un n dado, se puede obtener una lista de los residuos cuadráticos módulo n simplemente elevando al cuadrado todos los números 0, 1, ..., n − 1. Como a ≡ b (mod n ) implica a ² ≡ b ² (mod n ), cualquier otro residuo cuadrático es congruente (mod n ) con algún residuo de la lista obtenida. Pero la lista obtenida no está compuesta únicamente de residuos cuadráticos mutuamente incongruentes (mod n). Como a ² ≡( n − a ) ² (mod n ), la lista obtenida al elevar al cuadrado todos los números en la lista 1, 2, ..., n − 1 (o en la lista 0, 1, ..., n ) es simétrica (mod n ) alrededor de su punto medio, por lo tanto, en realidad solo es necesario elevar al cuadrado todos los números en la lista 0, 1, ..., n /2 . La lista así obtenida todavía puede contener números mutuamente congruentes (mod n ). Por lo tanto, el número de residuos cuadráticos mutuamente no congruentes módulo n no puede exceder n /2 + 1 ( n par) o ( n + 1)/2 ( n impar). ^[3] ${\displaystyle \lfloor }$ ${\displaystyle \rfloor }$

El producto de dos residuos es siempre un residuo.

Módulo primo

Módulo 2, todo entero es un residuo cuadrático.

Módulo un número primo impar p existen ( p + 1)/2 residuos (incluido 0) y ( p − 1)/2 no residuos, según el criterio de Euler . En este caso, se acostumbra considerar 0 como un caso especial y trabajar dentro del grupo multiplicativo de elementos no nulos del cuerpo . (En otras palabras, cada clase de congruencia excepto cero módulo p tiene un inverso multiplicativo. Esto no es cierto para los módulos compuestos.) ^[4] ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )}$

Siguiendo esta convención, el inverso multiplicativo de un residuo es un residuo, y el inverso de un no residuo es un no residuo. ^[5]

Siguiendo esta convención, módulo un número primo impar hay un número igual de residuos y no residuos. ^[4]

Módulo un primo, el producto de dos no residuos es un residuo y el producto de un no residuo y un residuo (distinto de cero) es un no residuo. ^[5]

El primer complemento ^[6] a la ley de reciprocidad cuadrática es que si p ≡ 1 (mod 4) entonces −1 es un residuo cuadrático módulo p , y si p ≡ 3 (mod 4) entonces −1 es un no residuo módulo p . Esto implica lo siguiente:

Si p ≡ 1 (mod 4) el negativo de un residuo módulo p es un residuo y el negativo de un no residuo es un no residuo.

Si p ≡ 3 (mod 4) el negativo de un residuo módulo p es un no residuo y el negativo de un no residuo es un residuo.

Módulo de potencia principal

Todos los cuadrados impares son ≡ 1 (mod 8) y, por lo tanto, también ≡ 1 (mod 4). Si a es un número impar y m = 8, 16 o una potencia superior a 2, entonces a es un residuo módulo m si y solo si a ≡ 1 (mod 8). ^[7]

Por ejemplo, mod (32) los cuadrados impares son

1 ² ≡ 15 ² ≡ 1

3 ² ≡ 13 ² ≡ 9

5 ² ≡ 11 ² ≡ 25

7 ² ≡ 9 ² ≡ 49 ≡ 17

y los pares son

0 ² ≡ 8 ² ≡ 16 ² ≡ 0

2 ² ≡ 6 ² ≡ 10 ² ≡ 14 ² ≡ 4

4 ² ≡ 12 ² ≡ 16.

Entonces, un número distinto de cero es un residuo módulo 8, 16, etc., si y sólo si es de la forma 4 ^k (8 n + 1).

Un número relativamente primo a un primo impar p es un residuo módulo cualquier potencia de p si y sólo si es un residuo módulo p . ^[8]

Si el módulo es p ⁿ ,

entonces p ^k a

es un residuo módulo p ⁿ si k ≥ n

es un no residuo módulo p ⁿ si k < n es impar

es un residuo módulo p ⁿ si k < n es par y a es un residuo

es un no residuo módulo p ⁿ si k < n es par y a es un no residuo. ^[9]

Tenga en cuenta que las reglas son diferentes para potencias de dos y potencias de primos impares.

Módulo una potencia prima impar n = p ^k , los productos de residuos y no residuos relativamente primos a p obedecen las mismas reglas que módulo p ; p es un no residuo y, en general, todos los residuos y no residuos obedecen las mismas reglas, excepto que los productos serán cero si la potencia de p en el producto ≥ n .

Módulo 8, el producto de los no residuos 3 y 5 es el no residuo 7, y lo mismo para las permutaciones de 3, 5 y 7. De hecho, el grupo multiplicativo de los no residuos y 1 forman el cuatrigrupo de Klein .

El módulo compuesto no es una potencia prima

El hecho básico en este caso es

si a es un residuo módulo n , entonces a es un residuo módulo p ^k para cada potencia prima que divide a n .

si a es un no residuo módulo n , entonces a es un no residuo módulo p ^k para al menos una potencia prima que divide a n .

Módulo de un número compuesto, el producto de dos residuos es un residuo. El producto de un residuo y un no residuo puede ser un residuo, un no residuo o cero.

Por ejemplo, de la tabla para el módulo 6   1 , 2, 3 , 4 , 5 (residuos en negrita ).

El producto del residuo 3 y el no residuo 5 es el residuo 3, mientras que el producto del residuo 4 y el no residuo 2 es el no residuo 2.

Además, el producto de dos no residuos puede ser un residuo, un no residuo o cero.

Por ejemplo, de la tabla para el módulo 15   1 , 2, 3, 4 , 5 , 6 , 7, 8, 9, 10 , 11, 12, 13, 14 (residuos en negrita ).

El producto de los no residuos 2 y 8 es el residuo 1, mientras que el producto de los no residuos 2 y 7 es el no residuo 14.

Este fenómeno se puede describir mejor utilizando el vocabulario del álgebra abstracta. Las clases de congruencia relativamente primas al módulo son un grupo bajo la multiplicación, llamado el grupo de unidades del anillo , y los cuadrados son un subgrupo de este. Diferentes no residuos pueden pertenecer a diferentes clases laterales , y no existe una regla simple que prediga en cuál estará su producto. Módulo un primo, solo existe el subgrupo de cuadrados y una única clase lateral. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$

El hecho de que, por ejemplo, módulo 15 el producto de los no residuos 3 y 5, o del no residuo 5 y el residuo 9, o los dos residuos 9 y 10 sean todos cero proviene de trabajar en el anillo completo , que tiene divisores de cero para el compuesto n . ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$

Por esta razón algunos autores ^[10] añaden a la definición que un residuo cuadrático a no sólo debe ser un cuadrado sino también debe ser relativamente primo al módulo n ( a es coprimo a n si y sólo si a ² es coprimo a n ).

Aunque esto hace las cosas más ordenadas, este artículo no insiste en que los residuos deben ser coprimos con el módulo.

Notaciones

Gauss ^[11] utilizó R y N para denotar residuosidad y no residuosidad, respectivamente;

por ejemplo, 2 R 7 y 5 N 7 , o 1 R 8 y 3 N 8 .

Aunque esta notación es compacta y conveniente para algunos propósitos, ^{[12] [13]} una notación más útil es el símbolo de Legendre , también llamado carácter cuadrático , que se define para todos los números enteros a y números primos impares positivos p como

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{ if }}p{\text{ divides }}a\\+1&{\text{ if }}a\operatorname {R} p{\text{ and }}p{\text{ does not divide }}a\\-1&{\text{ if }}a\operatorname {N} p{\text{ and }}p{\text{ does not divide }}a\end{cases}}}$

Hay dos razones por las que los números ≡ 0 (mod p ) reciben un tratamiento especial. Como hemos visto, esto hace que muchas fórmulas y teoremas sean más fáciles de enunciar. La otra razón (relacionada) es que el carácter cuadrático es un homomorfismo del grupo multiplicativo de clases de congruencia distintas de cero módulo p a los números complejos bajo multiplicación. La configuración permite que su dominio se extienda al semigrupo multiplicativo de todos los números enteros. ^[14] ${\displaystyle ({\tfrac {np}{p}})=0}$

Una ventaja de esta notación sobre la de Gauss es que el símbolo de Legendre es una función que se puede utilizar en fórmulas. ^[15] También se puede generalizar fácilmente a residuos cúbicos , cuárticos y de mayor potencia. ^[16]

Existe una generalización del símbolo de Legendre para valores compuestos de p , el símbolo de Jacobi , pero sus propiedades no son tan simples: si m es compuesto y el símbolo de Jacobi entonces a N m , y si a R m entonces pero si no sabemos si a R m o a N m . Por ejemplo: y , pero 2 N 15 y 4 R 15 . Si m es primo, los símbolos de Jacobi y Legendre concuerdan. ${\displaystyle ({\tfrac {a}{m}})=-1,}$ ${\displaystyle ({\tfrac {a}{m}})=1,}$ ${\displaystyle ({\tfrac {a}{m}})=1}$ ${\displaystyle ({\tfrac {2}{15}})=1}$ ${\displaystyle ({\tfrac {4}{15}})=1}$

Distribución de residuos cuadráticos

Aunque los residuos cuadráticos parecen ocurrir en un patrón bastante aleatorio módulo n , y esto ha sido explotado en aplicaciones tales como acústica y criptografía, su distribución también exhibe algunas regularidades sorprendentes.

Utilizando el teorema de Dirichlet sobre primos en progresiones aritméticas , la ley de reciprocidad cuadrática y el teorema del resto chino (TRC), es fácil ver que para cualquier M > 0 existen primos p tales que los números 1, 2, ..., M son todos residuos módulo p .

Por ejemplo, si p ≡ 1 (mod 8), (mod 12), (mod 5) y (mod 28), entonces por la ley de reciprocidad cuadrática 2, 3, 5 y 7 serán todos residuos módulo p y, por lo tanto, todos los números del 1 al 10 lo serán. La TRC dice que esto es lo mismo que p ≡ 1 (mod 840), y el teorema de Dirichlet dice que hay un número infinito de primos de esta forma. 2521 es el más pequeño, y de hecho 1 ² ≡ 1, 1046 ² ≡ 2, 123 ² ≡ 3, 2 ² ≡ 4, 643 ² ≡ 5, 87 ² ≡ 6, 668 ² ≡ 7, 429 ² ≡ 8, 3 ² ≡ 9 y 529 ² ≡ 10 (mod 2521).

Fórmulas de Dirichlet

La primera de estas regularidades proviene del trabajo de Peter Gustav Lejeune Dirichlet (en la década de 1830) sobre la fórmula analítica para el número de clase de las formas cuadráticas binarias . ^[17] Sea q un número primo, s una variable compleja y definamos una L-función de Dirichlet como

${\displaystyle L(s)=\sum _{n=1}^{\infty }\left({\frac {n}{q}}\right)n^{-s}.}$

Dirichlet demostró que si q ≡ 3 (mod 4), entonces

${\displaystyle L(1)=-{\frac {\pi }{\sqrt {q}}}\sum _{n=1}^{q-1}{\frac {n}{q}}\left({\frac {n}{q}}\right)>0.}$

Por lo tanto, en este caso (primo q ≡ 3 (mod 4)), la suma de los residuos cuadráticos menos la suma de los no residuos en el rango 1, 2, ..., q − 1 es un número negativo.

Por ejemplo, módulo 11,

1 , 2, 3 , 4 , 5 , 6, 7, 8, 9 , 10 (residuos en negrita )

1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, y la diferencia es −11.

De hecho, la diferencia siempre será un múltiplo impar de q si q > 3. ^[18] Por el contrario, para q primo ≡ 1 (mod 4), la suma de los residuos cuadráticos menos la suma de los no residuos en el rango 1, 2, ..., q − 1 es cero, lo que implica que ambas sumas son iguales . ^{[ cita requerida ]} ${\displaystyle {\frac {q(q-1)}{4}}}$

Dirichlet también demostró que para el primo q ≡ 3 (mod 4),

${\displaystyle L(1)={\frac {\pi }{\left(2-\left({\frac {2}{q}}\right)\right)\!{\sqrt {q}}}}\sum _{n=1}^{\frac {q-1}{2}}\left({\frac {n}{q}}\right)>0.}$

Esto implica que hay más residuos cuadráticos que no residuos entre los números 1, 2, ..., ( q − 1)/2.

Por ejemplo, módulo 11 hay cuatro residuos menores que 6 (a saber, 1, 3, 4 y 5), pero solo un no residuo (2).

Un hecho intrigante acerca de estos dos teoremas es que todas las pruebas conocidas se basan en el análisis; nadie ha publicado nunca una prueba simple o directa de ninguno de los enunciados. ^[19]

Ley de reciprocidad cuadrática

Si p y q son primos impares, entonces:

(( p es un residuo cuadrático mod q ) si y solo si ( q es un residuo cuadrático mod p )) si y solo si (al menos uno de p y q es congruente con 1 mod 4).

Eso es:

${\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}}$

¿Dónde está el símbolo de Legendre ? ${\displaystyle \left({\frac {p}{q}}\right)}$

Así, para los números a y los primos impares p que no dividen a a :

Pares de residuos y no residuos

Módulo un primo p , el número de pares n , n + 1 donde n R p y n + 1 R p , o n N p y n + 1 R p , etc., son casi iguales. Más precisamente, ^{[20] [21]} sea p un primo impar. Para i , j = 0, 1 definamos los conjuntos

${\displaystyle A_{ij}=\left\{k\in \{1,2,\dots ,p-2\}:\left({\frac {k}{p}}\right)=(-1)^{i}\land \left({\frac {k+1}{p}}\right)=(-1)^{j}\right\},}$

y dejar

${\displaystyle \alpha _{ij}=|A_{ij}|.}$

Eso es,

α ₀₀ es el número de residuos que van seguidos de un residuo,

α ₀₁ es el número de residuos que van seguidos de un no residuo,

α ₁₀ es el número de no residuos que son seguidos por un residuo, y

α ₁₁ es el número de no residuos que son seguidos por un no residuo.

Entonces si p ≡ 1 (mod 4)

${\displaystyle \alpha _{00}={\frac {p-5}{4}},\;\alpha _{01}=\alpha _{10}=\alpha _{11}={\frac {p-1}{4}}}$

y si p ≡ 3 (mod 4)

${\displaystyle \alpha _{01}={\frac {p+1}{4}},\;\alpha _{00}=\alpha _{10}=\alpha _{11}={\frac {p-3}{4}}.}$

Por ejemplo: (residuos en negrita )

Módulo 17

1 , 2 , 3, 4 , 5, 6, 7, 8 , 9 , 10, 11, 12, 13 , 14, 15 , 16

Un ₀₀ = {1,8,15},

Un ₀₁ = {2,4,9,13},

Un ₁₀ = {3,7,12,14},

Un ₁₁ = {5,6,10,11}.

Módulo 19

1 , 2, 3, 4 , 5 , 6 , 7 , 8, 9 , 10, 11 , 12, 13, 14, 15, 16 , 17 , 18

Un ₀₀ = {4,5,6,16},

Un ₀₁ = {1,7,9,11,17},

Un ₁₀ = {3,8,10,15},

Un ₁₁ = {2,12,13,14}.

Gauss (1828) ^[22] introdujo este tipo de conteo cuando demostró que si p ≡ 1 (mod 4) entonces x ⁴ ≡ 2 (mod p ) puede resolverse si y sólo si p  =  a ²  + 64  b ² .

La desigualdad Pólya-Vinogradov

Los valores de para valores consecutivos de a imitan una variable aleatoria como el lanzamiento de una moneda . ^[23] Específicamente, Pólya y Vinogradov demostraron ^[24] (independientemente) en 1918 que para cualquier carácter de Dirichlet no principal χ( n ) módulo q y cualesquiera números enteros M y N , ${\displaystyle ({\tfrac {a}{p}})}$

${\displaystyle \left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log q\right),}$

en notación O grande . Configuración

${\displaystyle \chi (n)=\left({\frac {n}{q}}\right),}$

Esto demuestra que el número de residuos cuadráticos módulo q en cualquier intervalo de longitud N es

${\displaystyle {\frac {1}{2}}N+O({\sqrt {q}}\log q).}$

Es fácil ^[25] demostrar que

${\displaystyle \left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\sqrt {q}}\log q.}$

De hecho, ^[26]

${\displaystyle \left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\frac {4}{\pi ^{2}}}{\sqrt {q}}\log q+0.41{\sqrt {q}}+0.61.}$

Montgomery y Vaughan mejoraron esto en 1977, demostrando que, si la hipótesis generalizada de Riemann es verdadera, entonces

${\displaystyle \left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log \log q\right).}$

Este resultado no se puede mejorar sustancialmente, ya que Schur había demostrado en 1918 que

${\displaystyle \max _{N}\left|\sum _{n=1}^{N}\left({\frac {n}{q}}\right)\right|>{\frac {1}{2\pi }}{\sqrt {q}}}$

y Paley había demostrado en 1932 que

${\displaystyle \max _{N}\left|\sum _{n=1}^{N}\left({\frac {d}{n}}\right)\right|>{\frac {1}{7}}{\sqrt {d}}\log \log d}$

para infinitos d > 0.

Mínimo residuo cuadrático no residual

El residuo cuadrático mínimo mod p es claramente 1. La cuestión de la magnitud del residuo no cuadrático mínimo n ( p ) es más sutil, pero siempre es primo, y 7 aparece por primera vez en 71.

La desigualdad de Pólya-Vinogradov anterior da O( √ p log p ).

La mejor estimación incondicional es n ( p ) ≪ p ^θ para cualquier θ>1/4 √ e , obtenida mediante estimaciones de Burgess sobre sumas de caracteres . ^[27]

Suponiendo la hipótesis de Riemann generalizada , Ankeny obtuvo n ( p ) ≪ (log p ) ² . ^[28]

Linnik demostró que el número de p menores que X tales que n ( p ) > X ^ε está limitado por una constante que depende de ε. ^[27]

Los residuos no cuadráticos mínimos mod p para primos impares p son:

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... (secuencia A053760 en la OEIS )

Exceso cuadrático

Sea p un primo impar. El exceso cuadrático E ( p ) es el número de residuos cuadráticos en el rango (0, p /2) menos el número en el rango ( p /2, p ) (secuencia A178153 en la OEIS ). Para p congruente con 1 mod 4, el exceso es cero, ya que −1 es un residuo cuadrático y los residuos son simétricos bajo r ↔ p − r . Para p congruente con 3 mod 4, el exceso E es siempre positivo. ^[29]

Complejidad de encontrar raíces cuadradas

Es decir, dado un número a y un módulo n , ¿qué tan difícil es?

1. Para saber si existe una x que resuelve x ² ≡ a (mod n )
2. Suponiendo que exista, ¿cómo calcularlo?

Aquí se muestra una diferencia importante entre los módulos primos y compuestos. Módulo a primo p , un residuo cuadrático a tiene 1 + ( a | p ) raíces (es decir, cero si a N p , uno si a ≡ 0 (mod p ), o dos si a R p y mcd( a,p ) = 1).

En general, si un módulo compuesto n se escribe como producto de potencias de primos distintos, y hay n ₁ raíces módulo el primero, n ₂ módulo el segundo, ..., habrá n ₁ n ₂ ... raíces módulo n .

La forma teórica en que se combinan las soluciones módulo potencias primas para formar soluciones módulo n se denomina teorema del resto chino ; se puede implementar con un algoritmo eficiente. ^[30]

Por ejemplo:

Resuelva x ² ≡ 6 (mod 15).

x ² ≡ 6 (mod 3) tiene una solución, 0; x ² ≡ 6 (mod 5) tiene dos, 1 y 4.

y hay dos soluciones módulo 15, es decir, 6 y 9.

Resuelva x ² ≡ 4 (mod 15).

x ² ≡ 4 (mod 3) tiene dos soluciones, 1 y 2; x ² ≡ 4 (mod 5) tiene dos, 2 y 3.

y hay cuatro soluciones módulo 15, es decir, 2, 7, 8 y 13.

Resuelva x ² ≡ 7 (mod 15).

x ² ≡ 7 (mod 3) tiene dos soluciones, 1 y 2; x ² ≡ 7 (mod 5) no tiene soluciones.

y no hay soluciones módulo 15.

Módulo de potencia principal o principal

En primer lugar, si el módulo n es primo, el símbolo de Legendre se puede calcular rápidamente utilizando una variación del algoritmo de Euclides ^[31] o el criterio de Euler . Si es −1 no hay solución. En segundo lugar, suponiendo que , si n ≡ 3 (mod 4), Lagrange encontró que las soluciones están dadas por ${\displaystyle \left({\frac {a}{n}}\right)}$ ${\displaystyle \left({\frac {a}{n}}\right)=1}$

${\displaystyle x\equiv \pm \;a^{(n+1)/4}{\pmod {n}},}$

y Legendre encontró una solución similar ^[32] si n ≡ 5 (mod 8):

${\displaystyle x\equiv {\begin{cases}\pm \;a^{(n+3)/8}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic residue modulo }}n\\\pm \;a^{(n+3)/8}2^{(n-1)/4}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic non-residue modulo }}n\end{cases}}}$

Sin embargo, para los primos n ≡ 1 (mod 8), no existe una fórmula conocida. Tonelli ^[33] (en 1891) y Cipolla ^[34] encontraron algoritmos eficientes que funcionan para todos los módulos primos. Ambos algoritmos requieren encontrar un no residuo cuadrático módulo n , y no se conoce ningún algoritmo determinista eficiente para hacerlo. Pero como la mitad de los números entre 1 y n son no residuos, elegir números x al azar y calcular el símbolo de Legendre hasta que se encuentre un no residuo producirá uno rápidamente. Una ligera variante de este algoritmo es el algoritmo de Tonelli-Shanks . ${\displaystyle \left({\frac {x}{n}}\right)}$

Si el módulo n es una potencia prima n = p ^e , se puede encontrar una solución módulo p y "elevarla" a una solución módulo n utilizando el lema de Hensel o un algoritmo de Gauss. ^[8]

Módulo compuesto

Si el módulo n se ha factorizado en potencias primas, la solución se discutió anteriormente.

Si n no es congruente con 2 módulo 4 y el símbolo de Kronecker , entonces no hay solución; si n es congruente con 2 módulo 4 y , entonces tampoco hay solución. Si n no es congruente con 2 módulo 4 y , o n es congruente con 2 módulo 4 y , puede haber una o no. ${\displaystyle \left({\tfrac {a}{n}}\right)=-1}$ ${\displaystyle \left({\tfrac {a}{n/2}}\right)=-1}$ ${\displaystyle \left({\tfrac {a}{n}}\right)=1}$ ${\displaystyle \left({\tfrac {a}{n/2}}\right)=1}$

Si no se conoce la factorización completa de n , y n no es congruente con 2 módulo 4, o n es congruente con 2 módulo 4 y , se sabe que el problema es equivalente a la factorización entera de n (es decir, una solución eficiente para cualquiera de los problemas podría usarse para resolver el otro de manera eficiente). ${\displaystyle \left({\tfrac {a}{n}}\right)=1}$ ${\displaystyle \left({\tfrac {a}{n/2}}\right)=1}$

La discusión anterior indica cómo conocer los factores de n nos permite encontrar las raíces de manera eficiente. Digamos que hubiera un algoritmo eficiente para encontrar raíces cuadradas módulo un número compuesto. El artículo congruencia de cuadrados analiza cómo encontrar dos números x e y donde x ² ≡ y ² (mod n ) y x ≠ ± y es suficiente para factorizar n de manera eficiente. Genere un número aleatorio, elévelo al cuadrado módulo n , y haga que el algoritmo eficiente de raíz cuadrada encuentre una raíz. Repita hasta que devuelva un número distinto del que originalmente elevamos al cuadrado (o su negativo módulo n ), luego siga el algoritmo descrito en congruencia de cuadrados. La eficiencia del algoritmo de factorización depende de las características exactas del buscador de raíces (por ejemplo, ¿devuelve todas las raíces? ¿Solo la más pequeña? ¿Una aleatoria?), pero será eficiente. ^[35]

La determinación de si a es un residuo cuadrático o un no residuo módulo n (denotado como R n o como N n ) se puede realizar de manera eficiente para el primo n calculando el símbolo de Legendre. Sin embargo, para el compuesto n , esto forma el problema de residuosidad cuadrática , que no se sabe que sea tan difícil como la factorización, pero se supone que es bastante difícil.

Por otro lado, si queremos saber si hay una solución para x menor que un límite dado c , este problema es NP-completo ; ^[36] sin embargo, este es un problema manejable con parámetros fijos , donde c es el parámetro.

En general, para determinar si a es un residuo cuadrático módulo compuesto n , se puede utilizar el siguiente teorema: ^[37]

Sea n > 1 y mcd( a , n ) = 1. Entonces x ² ≡ a (mod n ) es solucionable si y solo si:

• El símbolo de Legendre para todos los divisores primos impares p de n . ${\displaystyle \left({\tfrac {a}{p}}\right)=1}$
• a ≡ 1 (mod 4) si n es divisible por 4 pero no por 8; o a ≡ 1 (mod 8) si n es divisible por 8.

Nota: Este teorema requiere esencialmente que se conozca la factorización de n . Observe también que si mcd( a , n ) = m , entonces la congruencia se puede reducir a a / m ≡ x ² / m (mod n / m ) , pero entonces esto elimina el problema de los residuos cuadráticos (a menos que m sea un cuadrado).

El número de residuos cuadráticos

La lista del número de residuos cuadráticos módulo n , para n = 1, 2, 3 ..., se ve así:

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ... (secuencia A000224 en la OEIS )

Stangl da una fórmula para contar el número de cuadrados módulo n . ^[38]

Aplicaciones de los residuos cuadráticos

Acústica

Los difusores de sonido se han basado en conceptos de teoría de números como raíces primitivas y residuos cuadráticos. ^[39]

Teoría de grafos

Los grafos de Paley son grafos densos no dirigidos, uno para cada primo p ≡ 1 (mod 4), que forman una familia infinita de grafos de conferencia , que producen una familia infinita de matrices de conferencia simétricas .

Los dígrafos de Paley son análogos dirigidos de los gráficos de Paley, uno para cada p ≡ 3 (mod 4), que producen matrices de conferencia antisimétricas .

La construcción de estos gráficos utiliza residuos cuadráticos.

Criptografía

El hecho de que hallar la raíz cuadrada de un número módulo un número compuesto grande n es equivalente a factorizar (lo que se considera un problema difícil ) se ha utilizado para construir esquemas criptográficos como el criptosistema de Rabin y el de transferencia inconsciente . El problema de residuosidad cuadrática es la base del criptosistema de Goldwasser-Micali .

El logaritmo discreto es un problema similar que también se utiliza en criptografía.

Prueba de primalidad

El criterio de Euler es una fórmula para el símbolo de Legendre ( a | p ) donde p es primo. Si p es compuesto la fórmula puede o no calcular ( a | p ) correctamente. La prueba de primalidad de Solovay-Strassen para determinar si un número dado n es primo o compuesto escoge un a aleatorio y calcula ( a | n ) utilizando una modificación del algoritmo de Euclides, ^[40] y también utilizando el criterio de Euler. ^[41] Si los resultados no coinciden, n es compuesto; si coinciden, n puede ser compuesto o primo. Para un n compuesto al menos la mitad de los valores de a en el rango 2, 3, ..., n − 1 devolverán " n es compuesto"; para n primo ninguno lo hará. Si, después de utilizar muchos valores diferentes de a , no se ha demostrado que n sea compuesto, se denomina " primo probable ".

La prueba de primalidad de Miller-Rabin se basa en los mismos principios. Existe una versión determinista de la misma, pero la prueba de que funciona depende de la hipótesis generalizada de Riemann ; el resultado de esta prueba es " n es definitivamente compuesto" o "o bien n es primo o la GRH es falsa". Si alguna vez se da el segundo resultado para un n compuesto , entonces la GRH sería falsa, lo que tendría implicaciones en muchas ramas de las matemáticas.

Factorización de números enteros

En el § VI de las Disquisitiones Arithmeticae ^[42] Gauss analiza dos algoritmos de factorización que utilizan residuos cuadráticos y la ley de reciprocidad cuadrática .

Varios algoritmos de factorización modernos (incluido el algoritmo de Dixon , el método de fracción continua , la criba cuadrática y la criba del cuerpo numérico ) generan pequeños residuos cuadráticos (módulo del número que se está factorizando) en un intento de encontrar una congruencia de cuadrados que produzca una factorización. La criba del cuerpo numérico es el algoritmo de factorización de propósito general más rápido que se conoce.

Tabla de residuos cuadráticos

La siguiente tabla (secuencia A096008 en la OEIS ) enumera los residuos cuadráticos módulo 1 a 75 (un número rojo significa que no es coprimo con n ). (Para los residuos cuadráticos coprimos con n , consulte OEIS : A096103 , y para residuos cuadráticos distintos de cero, consulte OEIS : A046071 ).

Véase también

• Criterio de Euler
• Lema de Gauss
• Lema de Zolotarev
• Suma de caracteres
• Ley de reciprocidad cuadrática
• Código de residuo cuadrático

Notas

1. Lemmemeyer, Cap. 1
2. Lemmermeyer, págs. 6-8, pág. 16 y siguientes
3. Gauss, DA, artículo 94
4. Gauss, DA, artículo 96
5. Gauss, DA, artículo 98
6. Gauss, DA, artículo 111
7. Gauss, DA, artículo 103
8. Gauss, DA, artículo 101
9. Gauss, DA, artículo 102
10. Por ejemplo, Ireland & Rosen 1990, pág. 50
11. Gauss, DA, artículo 131
12. Por ejemplo, Hardy y Wright lo utilizan.
13. Gauss, DA, artículo 230 y siguientes.
14. Esta extensión del dominio es necesaria para definir funciones L.
15. Consulte el símbolo de Legendre#Propiedades del símbolo de Legendre para ver ejemplos
16. Lemmermeyer, págs. 111-fin
17. Davenport 2000, págs. 8-9, 43-51. Éstos son resultados clásicos.
18. Davenport 2000, pp. 49–51, (conjeturado por Jacobi , demostrado por Dirichlet)
19. Davenport 2000, pág. 9
20. Lemmermeyer, pág. 29, ej. 1.22; cf. págs. 26-27, cap. 10
21. Crandall y Pomerance, ejemplo 2.38, págs. 106-108
22. Gauss, Theorie der biquadratischen Reste, Erste Abhandlung (págs. 511–533 de Untersuchungen über hohere Arithmetik)
23. Crandall y Pomerance, ejemplo 2.38, págs. 106-108, analizan las similitudes y diferencias. Por ejemplo, al lanzar n monedas, es posible (aunque poco probable) obtener n /2 caras seguidas de la misma cantidad de cruces. La desigualdad de VP descarta esta posibilidad para los residuos.
24. Davenport 2000, pp. 135-137, (prueba de P–V, (de hecho, el O grande puede reemplazarse por 2); referencias de revistas para Paley, Montgomery y Schur)
25. Planet Math: Prueba de la desigualdad de Pólya-Vinogradov en enlaces externos. La prueba ocupa una página y solo requiere datos elementales sobre sumas gaussianas
26. Pomerance & Crandall, ex 2.38 pp.106–108. resultado de T. Cochrane, "Sobre una desigualdad trigonométrica de Vinogradov", J. Number Theory , 27:9–16, 1987
27. Friedlander, John B .; Iwaniec, Henryk (2010). Opera De Cribro . Sociedad Matemática Americana . pág. 156. ISBN. 978-0-8218-4970-5.Zbl 1226.11099  .
28. Montgomery, Hugh L. (1994). Diez conferencias sobre la interfaz entre la teoría analítica de números y el análisis armónico . American Mathematical Society . pág. 176. ISBN. 0-8218-0737-4.Zbl 0814.11001  .
29. Bateman, Paul T. ; Diamond, Harold G. (2004). Teoría analítica de números . World Scientific. pág. 250. ISBN 981-256-080-7.Zbl 1074.11001  .
30. Bach y Shallit 1996, pág. 104 y siguientes; requiere O(log ² m ) pasos donde m es el número de primos que dividen a n .
31. Bach y Shallit 1996, pág. 113; el cálculo requiere O(log a log n ) pasos ${\displaystyle \left({\frac {a}{n}}\right)}$
32. Lemmermeyer, pág. 29
33. Bach y Shallit 1996, pág. 156 y siguientes; el algoritmo requiere O(log ⁴ n ) pasos.
34. Bach y Shallit 1996, pág. 156 y siguientes; el algoritmo requiere O(log ³ n ) pasos y también es no determinista.
35. Crandall y Pomerance, ejemplos 6.5 y 6.6, pág. 273
36. Manders y Adleman 1978
37. Burton, David (2007). Teoría elemental de números . Nueva York: McGraw Hill. pág. 195.
38. Stangl, Walter D. (octubre de 1996), "Contar cuadrados en ℤn" (PDF) , Mathematics Magazine , 69 (4): 285–289, doi :10.2307/2690536, JSTOR  2690536
39. Walker, R. "El diseño y la aplicación de elementos modulares de difusión acústica" (PDF) . Departamento de Investigación de la BBC . Consultado el 25 de octubre de 2016 .
40. Bach y Shallit 1996, pág. 113
41. Bach y Shallit 1996, págs. 109-110; el criterio de Euler requiere O(log ³ n ) pasos
42. Gauss, DA, artículos 329–334

Referencias

Las Disquisitiones Arithmeticae han sido traducidas del latín ciceroniano de Gauss al inglés y al alemán . La edición alemana incluye todos sus artículos sobre teoría de números: todas las pruebas de reciprocidad cuadrática, la determinación del signo de la suma de Gauss , las investigaciones sobre reciprocidad bicuadrática y notas inéditas.

• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae , traducido por Clarke, Arthur A. (segunda edición corregida), Nueva York: Springer , ISBN 0-387-96254-9
• Gauss, Carl Friedrich (1965), Untersuchungen über hohere Arithmetik [ Disquisitiones Arithmeticae y otros artículos sobre teoría de números ], traducido por Maser, H. (segunda ed.), Nueva York: Chelsea, ISBN 0-8284-0191-8
• Bach, Eric; Shallit, Jeffrey (1996), Algoritmos eficientes , Teoría algorítmica de números, vol. I, Cambridge: The MIT Press , ISBN 0-262-02405-5
• Crandall, Richard; Pomerance, Carl (2001), Números primos: una perspectiva computacional , Nueva York: Springer, ISBN 0-387-94777-9
• Davenport, Harold (2000), Teoría de números multiplicativos (tercera edición), Nueva York: Springer, ISBN 0-387-95097-4
• Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, ISBN 0-7167-1045-5A7.1: AN1, pág.249.
• Hardy, GH ; Wright, EM (1980), Introducción a la teoría de números (quinta ed.), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Irlanda, Kenneth; Rosen, Michael (1990), Una introducción clásica a la teoría de números moderna (segunda ed.), 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
• Manders, Kenneth L.; Adleman, Leonard (1978), " Problemas de decisión NP -completos para cuadráticas binarias", Journal of Computer and System Sciences , 16 (2): 168–184, doi : 10.1016/0022-0000(78)90044-2 .

Enlaces externos

• Weisstein, Eric W. "Residuo cuadrático". MathWorld .
• Prueba de la desigualdad de Pólya-Vinogradov en PlanetMath .