Residuo cuadrático

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:

x2↑ ↑ q()modn).{displaystyle x^{2}equiv q{pmod {n}}

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

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

Historia, convenciones y hechos elementales

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

Para un n dado, se puede obtener una lista de los residuos cuadráticos módulo n simplemente elevando al cuadrado los números 0, 1,..., n − 1. Porque a² ≡ (n − a)² (mod n), la lista de cuadrados módulo n es simétrica alrededor de n/2, y la lista solo necesita ir tan alto. Esto se puede ver en la siguiente tabla.

Así, el número de residuos cuadráticos módulo n no puede exceder n/2 + 1 (n par) o (n + 1)/2 (n impar).

El producto de dos residuos siempre es un residuo.

Módulo primo

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

Modulo un número primo impar p hay (p + 1)/2 residuos (incluyendo 0) y (p − 1) /2 no residuos, por el criterio de Euler. En este caso, se acostumbra considerar el 0 como un caso especial y trabajar dentro del grupo multiplicativo de elementos distintos de cero del campo Z/pZ. (En otras palabras, cada clase de congruencia excepto módulo cero p tiene un inverso multiplicativo. Esto no es cierto para módulos compuestos).

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

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

Modulo a 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.

El primer suplemento 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 módulo sin residuos 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 alguna potencia mayor de 2, entonces a es un residuo módulo m si y solo si a ≡ 1 (mod 8).

Por ejemplo, mod (32) los cuadrados impares son

1² ↑ 15² ↑ 1

3² ↑ 13² ↑ 9

5² ↑ 11² ↑ 25

7² ↑ 9² Resultados 49

y los incluso son

0² ↑ 8² ↑ 16² ↑

2² ↑ 6²↑ 10² ↑ 14²↑ 4

4² ↑ 12² ↑ 16.

Entonces, un número distinto de cero es un residuo mod 8, 16, etc., si y solo si es de la forma 4^k(8n + 1).

Un número a relativamente primo a un primo impar p es un residuo módulo cualquier potencia de p si y solo si es un residuo módulo p.

Si el módulo es pⁿ,

entonces p^ka

es un modulo de residuos pⁿ si k ≥ n

es un modulo no residual pⁿ si k. n Es extraño.

es un modulo de residuos pⁿ si k. n es incluso a es un residuo

es un modulo no residual pⁿ si k. n es incluso a es un no residuo.

Observe que las reglas son diferentes para potencias de dos y potencias de números primos impares.

Módulo una potencia prima impar n = p^k, los productos de residuos y no residuos primos relativos a p obedecen las mismas reglas que mod 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 ocurre con las permutaciones de 3, 5 y 7. De hecho, el grupo multiplicativo de los no residuos y 1 forman el grupo de cuatro de Klein.

Módulo compuesto no potencia prima

El hecho básico en este caso es

si a es un modulo de residuos n, entonces a es un modulo de residuos p^k para cada uno potencia principal división n.

si a es un modulo no residual n, entonces a es un modulo no residual p^k para al menos uno potencia principal división 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 residual 5 es el residuo 3, mientras que el producto del residuo 4 y el no residual 2 es el no residual 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 residual 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 multiplicación, llamado grupo de unidades del anillo Z/nZ, y los cuadrados son un subgrupo del mismo. Diferentes no residuos pueden pertenecer a diferentes clases laterales, y no existe una regla simple que prediga en cuál estará su producto. Modulo a primo, solo existe el subgrupo de cuadrados y una sola clase lateral.

El hecho de que, por ejemplo, el 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 Z/nZ, que tiene divisores cero para el compuesto n.

Por esta razón, algunos autores agregan a la definición que un residuo cuadrático a no solo debe ser un cuadrado sino que también debe ser primo relativo al módulo n. (a es coprimo de n si y solo si a² es coprimo de n.)

Aunque aclara las cosas, este artículo no insiste en que los residuos deben ser coprimos con el módulo.

Anotaciones

Gauss usó R y N para indicar residuos y no residuos, 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, 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

()ap)={}0sipdividecionesa+1siaR⁡ ⁡ pypno dividea− − 1siaN⁡ ⁡ pypno dividea{displaystyle left({frac {a}{p}right)={begin{cases};;;,0 limit{text{ if }p{ divides }a\+1 ventaja {text{ if }aoperatorname {R} p{text{ >}p{text{ no divide }a\1⁄4text{ if }aoperatorname {N}p{text{ and }p{text{ does not divide }aend{cases}}}}}}}} {f}}

Hay dos razones por las que los números ≡ 0 (mod p) son tratados especialmente. Como hemos visto, hace que muchas fórmulas y teoremas sean más fáciles de decir. La otra razón (relacionada) es que el carácter cuadrático es un homomorfismo del grupo multiplicativo de clases de congruencia no cero modulo p a los números complejos bajo multiplicación. Ajuste ()npp)=0{displaystyle ({tfrac {p}}=0} permite que su dominio sea extendido al semigrupo multiplicativo de todos los enteros.

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

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

Distribución de residuos cuadráticos

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

Usando el teorema de Dirichlet sobre números primos en progresiones aritméticas, la ley de reciprocidad cuadrática y el teorema chino del resto (CRT), es fácil ver que para cualquier M > 0 hay 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 modulo p, y así todos los números 1-10 serán. El CRT dice que esto es lo mismo 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² Resultados 2, 123² 3, 2² ngel 4, 643² TOR 5, 87² ↑ 6, 668² ↑ 7, 429² 8, 3² 9 y 529² (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. Sea q un número primo, s una variable compleja y defina una función L de Dirichlet como

L()s)=.. n=1JUEGO JUEGO ()nq)n− − s.{displaystyle L(s)=sum _{n=1}{infty }left({frac {n}right)n^{-s}

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

0.}" xmlns="http://www.w3.org/1998/Math/MathML">L()1)=− − π π q.. n=1q− − 1nq()nq)■0.{displaystyle L(1)=-{frac {pi } { sqrt {q}sum} ¿Por qué? {fn}fn}fn}m}m}m}m}m} {fn}m} {fnfnfn} {fn} {fn}fn}fn}c}c}m}cH00}m}cHFF}cH00}m}m}m}m}m}m}m}m}m}m}m}c}c}c}m}m}p}c}m}c}m}c}c}c}c}c}c}c}m}c}c}c}c}c}c}c}c}c}c}c}c}c}cH00}cH00}cH00c}c}c}c}cHFF}c}c} {n} {q}right)}0}0." aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87cf5c68cced3ca6a912af48694c00724ba85438" style="vertical-align: -3.005ex; width:30.61ex; height:7.343ex;"/>

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, modulo 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 par de q si q ■ 3. En contraste, para la primera q 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 q()q− − 1)4{displaystyle {frac {q(q-1)}{4}}.

Dirichlet también demostró que para números primos q ≡ 3 (mod 4),

0.}" xmlns="http://www.w3.org/1998/Math/MathML">L()1)=π π ()2− − ()2q))q.. n=1q− − 12()nq)■0.{displaystyle L(1)={frac {fnMicroc} {fnfn} {fnfnfn}}}derecha)! {sqrt {q}}}}sum _{n=1}{frac} {fnfnfnfn0} {q-1}{2}left({frac {n}right)}}}}}0." aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a64877aefd23a8ccf3f2146d0fa3fa527358bec3" style="vertical-align: -4.505ex; width:37.396ex; height:10.343ex;"/>

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

Por ejemplo, modulo 11 hay cuatro residuos menos de 6 (nombre 1, 3, 4 y 5), pero sólo un no residual (2).

Un hecho intrigante sobre 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 ninguna de las afirmaciones.

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:

()pq)()qp)=()− − 1)p− − 12⋅ ⋅ q− − 12{displaystyle left({frac {fnK}right)left({frac} {q}p}right)=(-1)^{frac {p-1}{2}cdot {frac {q-1}{2}}}

Donde ()pq){displaystyle left({frac {q}right)} es el símbolo Legendre.

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

Pares de residuos y no residuos

Módulo a 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, sea p un primo impar. Para i, j = 0, 1 define los conjuntos

Aij={}k▪ ▪ {}1,2,...... ,p− − 2}:()kp)=()− − 1)i∧ ∧ ()k+1p)=()− − 1)j},{displaystyle A_{ij}=left{kin {1,2,dotsp-2}:left({frac {k}{p}right)=(-1)^{i}land left({frac {k+1}{p}right)=(-1)^{j}right}}

y dejar

α α ij=SilencioAijSilencio.{displaystyle alpha - Hola.

Es decir,

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

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

α₁₀ 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 residual.

Entonces si p ≡ 1 (mod 4)

α α 00=p− − 54,α α 01=α α 10=α α 11=p− − 14{displaystyle alpha {fnMicroc {p-5}{4}};Alpha # {01}=alpha ################################################################################################################################################################################################################################################################ ¿Qué? {p-1}{4}}

y si p ≡ 3 (mod 4)

α α 01=p+14,α α 00=α α 10=α α 11=p− − 34.{displaystyle alpha {01}={frac {p+1}{4}};alpha ¿Qué? ################################################################################################################################################################################################################################################################ ¿Qué? {p-3}{4}}

Por ejemplo: negrita)

Modulo 17

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

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

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

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

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

Modulo 19

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

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

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

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

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

Gauss (1828) introdujo este tipo de conteo cuando demostró que si p ≡ 1 (mod 4) entonces x⁴ ≡ 2 (mod p) se puede resolver si y solo si p = a² + 64 b².

La desigualdad de Pólya-Vinogradov

Los valores de ()ap){displaystyle ({tfrac {}{p}}} por valores consecutivos a imitar una variable al azar como una moneda. Específicamente, Pólya y Vinogradov demostraron (independientemente) en 1918 que para cualquier personaje no principal Dirichlet χ(nModulo q y cualquier entero M y N,

Silencio.. n=M+1M+Nχ χ ()n)Silencio=O()qlog⁡ ⁡ q),{displaystyle left durablesum ################################################################################################################################################################################################################################################################

en notación O grande. Configuración

χ χ ()n)=()nq),{displaystyle chi (n)=left({frac {n}right),}

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

12N+O()qlog⁡ ⁡ q).No.

Es fácil demostrar que

<math alttext="{displaystyle left|sum _{n=M+1}^{M+N}left({frac {n}{q}}right)right|Silencio.. n=M+1M+N()nq)Silencio.qlog⁡ ⁡ q.{displaystyle left durablesum ¿Por qué? {q}log q.}<img alt="left|sum _{{n=M+1}}^{{M+N}}left({frac {n}{q}}right)right|

De hecho,

<math alttext="{displaystyle left|sum _{n=M+1}^{M+N}left({frac {n}{q}}right)right|Silencio.. n=M+1M+N()nq)Silencio.4π π 2qlog⁡ ⁡ q+0.41q+0.61.{displaystyle left durablesum ¿Por qué? {4}{pi ^{2}}{sqrt {q}log q+0.41{sqrt {q}+0.61}<img alt="left|sum _{{n=M+1}}^{{M+N}}left({frac {n}{q}}right)right|

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

Silencio.. n=M+1M+Nχ χ ()n)Silencio=O()qlog⁡ ⁡ log⁡ ⁡ q).{displaystyle left durablesum ¿Por qué? }

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

{frac {1}{2pi }}{sqrt {q}}}" xmlns="http://www.w3.org/1998/Math/MathML">maxNSilencio.. n=1N()nq)Silencio■12π π q{displaystyle max _{N}left foreversum ¿Por qué? } { sqrt {q}{frac {1}{2pi }}{sqrt q}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6e8610c0248aefb525b70a4bfbf6a701dc136bda" style="vertical-align: -3.171ex; width:24.835ex; height:7.509ex;"/>

y Paley habían demostrado en 1932 que

{frac {1}{7}}{sqrt {d}}log log d}" xmlns="http://www.w3.org/1998/Math/MathML">maxNSilencio.. n=1N()dn)Silencio■17dlog⁡ ⁡ log⁡ ⁡ d{displaystyle max _{N}left foreversum ¿Por qué? {1}{7}{sqrt {d}log log d}{frac {1}{7}}{sqrt d}log log d" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4c0dd9ddd3b53b4c89941f397570a3ae24896697" style="vertical-align: -3.171ex; width:31.97ex; height:7.509ex;"/>

para infinitas d > 0.

Mínimo sin residuo cuadrático

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

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

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

Asumiendo la hipótesis de Riemann Generalizada, Ankeny obtuvo n(p) ≪ (log p)².

Linnik demostró que el número de p menor que X tal que n(p) > X^ε está acotado por una constante que depende de ε.

El mod menos cuadrático sin residuos p para primos impares p es:

2, 3, 2, 3, 2, 5, 2, 3, 2,... A053760 en el 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 el 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.

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 x solución x² ↑ a (modelo) n) existe
2. suponiendo que uno exista, para calcularlo?

Aquí aparece una diferencia importante entre 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 un producto de potencias de primos distintos, y hay n₁ raíces módulo el el primero, n₂ mod el segundo,..., habrá n₁n ₂... raíces módulo n.

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

Por ejemplo:

Solve x² 6 (mod 15).

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

y hay dos soluciones modulo 15: 6 y 9.

Solve x² (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 modulo 15: 2, 7, 8 y 13.

Solve x² (mod 15).

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

y no hay soluciones modulo 15.

Prime o módulo de potencia principal

Primero, si el módulo n es el símbolo de la leyenda ()an){displaystyle left({frac {n}right)} se puede calcular rápidamente utilizando una variación del algoritmo de Euclid o el criterio de Euler. Si es −1 no hay solución. En segundo lugar, suponiendo que ()an)=1{displaystyle left({frac {a} {n}right)=1}, si n Lagrange encontró que las soluciones son dadas por

x↑ ↑ ± ± a()n+1)/4()modn),{displaystyle xequiv pm ;a^{(n+1)/4}{pmod {n}}

y Legendre encontraron una solución similar si n ≡ 5 (mod 8):

x↑ ↑ {}± ± a()n+3)/8()modn)siaes un modulo de residuos cuárticosn± ± a()n+3)/82()n− − 1)/4()modn)siaes un modulo no residual quarticon{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fn} {fn} {fn} {fnfn}} {fnfnfnfnfnfn} {fnfnfnfnfnfnfn} {fnfnfn}fnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnfnh00}fnfn

Para el mejor n Sin embargo, no hay fórmula conocida. Tonelli (en 1891) y Cipolla encontraron algoritmos eficientes que funcionan para todos los moduli primo. Ambos algoritmos requieren encontrar un modulo no residual cuadrático n, y no hay un algoritmo determinista eficiente conocido por hacer eso. Pero desde la mitad de los números entre 1 y n no son residuos, selección de números x al azar y calcular el símbolo Legendre ()xn){displaystyle left({frac {x}}right)} hasta que se encuentre un no residuo producirá rápidamente uno. Una ligera variante de este algoritmo es el algoritmo Tonelli-Shanks.

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

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 modulo 4 y el símbolo Kronecker ()an)=− − 1{displaystyle left({tfrac {a} {n}right)=-1} entonces no hay solución; si n es congruente con 2 modulo 4 y ()an/2)=− − 1{displaystyle left({tfrac {a}{n/2}right)=-1}, entonces tampoco hay solución. Si n no es congruente con 2 modulo 4 y ()an)=1{displaystyle left({tfrac {n}right)=1}, o n es congruente con 2 modulo 4 y ()an/2)=1{displaystyle left({tfrac {a}{n/2}right)=1}, puede o no haber uno.

Si la factorización completa n no es conocido, y ()an)=1{displaystyle left({tfrac {n}right)=1} y n no es congruente con 2 modulo 4, o n es congruente con 2 modulo 4 y ()an/2)=1{displaystyle left({tfrac {a}{n/2}right)=1}, se sabe que el problema es equivalente a la factorización del entero n (es decir, se podría utilizar una solución eficiente para resolver el otro de manera eficiente).

La discusión anterior indica cómo conocer los factores n nos permite encontrar las raíces de manera eficiente. Digamos que había un algoritmo eficiente para encontrar raíces cuadradas modulo un número compuesto. El artículo congruencia de cuadrados habla de cómo encontrar dos números x y donde x² ↑ Sí.² (modelo) n) y x ±Sí. suficiente para factorizar n eficientemente. Generar un número al azar, cuadrado que modulo n, y tener el algoritmo de raíz cuadrado eficiente encontrar una raíz. Repita hasta que devuelva un número no igual al que originalmente hemos cuadrado (o su modulo negativo) n), luego siga el algoritmo descrito en congruencia de cuadrados. La eficiencia del algoritmo de factorización depende de las características exactas del filtro raíz (por ejemplo, ¿devuelve todas las raíces? ¿El más pequeño? aleatorio?), pero será eficiente.

Determinar si a es un residuo cuadrático o módulo no residuo n (denotado a R n o a N n) se puede hacer de manera eficiente para números primos n calculando el símbolo de Legendre. Sin embargo, para n compuesto, 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 algún límite dado c, este problema es NP-completo; sin embargo, este es un problema tratable de 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 usar el siguiente teorema:

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

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

Nota: Este teorema esencialmente requiere que se conozca la factorización de n. También observe que si mcd(a,n) = m, entonces la congruencia puede reducirse a a/m ≡ x²/m (mod n/m), pero 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, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6,... A000224 en el OEIS)

Stangl proporciona una fórmula para contar el número de cuadrados módulo n.

Aplicaciones de residuos cuadráticos

Acústica

Los difusores de sonido se han basado en conceptos teóricos de números, como raíces primitivas y residuos cuadráticos.

Teoría de grafos

Los gráficos de Paley son gráficos densos no dirigidos, uno para cada número primo p ≡ 1 (mod 4), que forman una familia infinita de gráficos de conferencias, que producen una familia infinita de matrices de conferencias 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 conferencia antisimétricas.

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

Criptografía

El hecho de que encontrar la raíz cuadrada de un número módulo un gran compuesto n es equivalente a la factorización (que se cree que es un problema difícil) se ha utilizado para construir esquemas criptográficos como el Criptosistema Rabin y la transferencia olvidada. El problema de los residuos cuadráticos es la base del criptosistema Goldwasser-Micali.

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

Pruebas 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 calcularse o no (a|p) correctamente. La prueba de primalidad de Solovay-Strassen para determinar si un número dado n es primo o compuesto elige un a aleatorio y calcula (a|n ) usando una modificación del algoritmo de Euclides, y también usando el criterio de Euler. Si los resultados no están de acuerdo, n es compuesto; si están de acuerdo, n puede ser compuesto o primo. Para un compuesto n al menos la mitad de los valores de a en el rango 2, 3,..., n − 1 devolverá "n es compuesto"; para primos n ninguno lo hará. Si, después de usar muchos valores diferentes de a, n no se ha demostrado que es compuesto, se denomina "primo probable".

La prueba de primalidad de Miller-Rabin se basa en los mismos principios. Hay una versión determinista del mismo, 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 el GRH es falso". Si alguna vez se produce la segunda salida para un n compuesto, entonces el GRH sería falso, lo que tendría implicaciones en muchas ramas de las matemáticas.

Factorización de enteros

En el § VI de las Disquisitiones Arithmeticae, Gauss analiza dos algoritmos de factorización que usan 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 de campos numéricos) generan pequeños residuos cuadráticos (módulo el número que se factoriza) en un intento de encontrar una congruencia de cuadrados que producirán una factorización. La criba de campos numéricos 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 el OEIS) enumera los residuos cuadráticos mod 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 los residuos cuadráticos distintos de cero, consulte OEIS: A046071.)