Residuo cuadrático

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

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

De lo contrario, q se denomina módulo cuadrático sin residuos 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 ^[1] y formaron conjeturas ^[2] sobre 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 podrá eliminar el adjetivo "cuadrático".

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

Por lo tanto, el número de residuos cuadráticos módulo n no puede exceder n /2 + 1 ( n par) o ( n + 1)/2 ( n impar). ^[3]

El producto de dos residuos es siempre un residuo.

módulo primo

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

En módulo de un número primo impar p , hay ( 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 distintos de cero del campo . (En otras ^palabras , cada clase de congruencia excepto módulo cero p tiene un inverso multiplicativo. Esto no es cierto para los módulos compuestos). $(\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 de un número primo impar, hay un número igual de residuos y no residuos. ^[4]

Módulo 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. ^[5]

El primer complemento ^[6] a la ley de la reciprocidad cuadrática es que si p ≡ 1 (mod 4), entonces −1 es un módulo de residuo cuadrático p , y si p ≡ 3 (mod 4), entonces −1 es un módulo de no residuo 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 tanto también ≡ 1 (mod 4). Si a es un número impar y m = 8, 16 o alguna potencia superior de 2, entonces a es un módulo residual m si y sólo 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 mod 8, 16, etc., si y solo si es de la forma 4 ^k (8 n + 1).

Un número entre primos relativos y primos impares p es un residuo módulo cualquier potencia de p si y solo si es un residuo módulo p . ^[8]

Si el módulo es p ⁿ ,

entonces pk a

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

es un módulo sin residuos p ⁿ si k < n es impar

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

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

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

El módulo compuesto no es una potencia primaria

El hecho básico en este caso es

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

si a es un módulo sin residuo n , entonces a es un módulo sin residuo p ^k para al menos una potencia primaria que divide 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 del 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 con respecto al módulo son un grupo bajo multiplicación, llamado grupo de unidades del anillo , 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. Módulo primo, solo existe el subgrupo de cuadrados y una única clase lateral. $(\mathbb {Z} /n\mathbb {Z} )$

El hecho de que, por ejemplo, en 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 cero para compuesto $(\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 que también debe ser primo relativo con respecto al módulo n . ( a es coprimo con respecto a n si y solo si a ² es coprimo con respecto a n .)

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

Notaciones

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

por ejemplo,

2 R 7

5 N 7

, o

1 R 8

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$ primos impares positivos $p$ como

\left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{ si }}p{\text{ divide }}a\ \+1&{\text{ si }}a\operatorname {R} p{\text{ y }}p{\text{ no divide }}a\\-1&{\text{ si }}a\operatorname { N} p{\text{ y }}p{\text{ no divide }}a\end{cases}}

Hay dos razones por las que los números ≡ 0 (mod $p$ ) reciben un tratamiento especial. Como hemos visto, 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 extender su dominio al semigrupo multiplicativo de todos los números enteros. ^[14] $({\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. ^[dieciséis]

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 saber si $un$ $R$ $m$ o $un$ $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. $({\tfrac {a}{m}})=-1,$ $({\tfrac {a}{m}})=1,$ $({\tfrac {a}{m}})=1$ $({\tfrac {2}{15}})=1$ $({\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 se ha explotado en aplicaciones tales como acústica y 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 los residuos módulo p .

Por ejemplo, si p ≡ 1 (mod 8), (mod 12), (mod 5) y (mod 28), entonces, según la ley de reciprocidad cuadrática, 2, 3, 5 y 7 serán todos residuos módulo p , y por tanto, todos los números del 1 al 10 lo serán. La CRT 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).

Las fórmulas de Dirichlet

La primera de estas regularidades surge 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 formas cuadráticas binarias . ^[17] Sea q un número primo, s una variable compleja y defina una función L de Dirichlet como

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

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

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 el primo 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 . ^[^{cita necesaria}^] ${\frac {q(q-1)}{4}}$

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

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, en el módulo 11 hay cuatro residuos menores que 6 (es decir, 1, 3, 4 y 5), pero solo un no residuo (2).

Un hecho intrigante acerca de estos dos teoremas es que todas las demostraciones conocidas se basan en el análisis; nadie ha publicado nunca una prueba simple o directa de cualquiera de las afirmaciones. ^[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:

\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 ? $\left({\frac {p}{q}}\right)$

Por lo tanto, para los números a y los 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, ^[20]^[21] sea p un primo impar. Para i , j = 0, 1 define los conjuntos

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 deja

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

Eso es,

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

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

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

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

Entonces si p ≡ 1 (mod 4)

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

y si p ≡ 3 (mod 4)

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

Por ejemplo: (restos en negrita )
Módulo 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},
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
A ₀₀ = {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] (de forma independiente) en 1918 que para cualquier carácter no principal de Dirichlet χ( n ) módulo q y cualquier número entero M y N , $({\tfrac {a}{p}})$

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

en notación O grande . Configuración

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

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

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

Es fácil ^[25] demostrar que

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

De hecho, ^[26]

\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 cierta, entonces

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

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

\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

\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.

No residuo menos cuadrático

El mod p mínimo del residuo cuadrático es claramente 1. La cuestión de la magnitud del no 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 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]

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

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

Los mod p sin residuos menos cuadráticos para primos impares p son:

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... (secuencia 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 de E siempre es 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

para saber si existe una x que resuelve x ² ≡ a (mod n )
suponiendo que exista uno, ¿para 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 ₂ mod el segundo, ..., habrá n ₁n ₂ ... raíces módulo n .

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

Por ejemplo:
Resuelve 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, a saber, 6 y 9.
Resuelve 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, a saber, 2, 7, 8 y 13.
Resuelve 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 $\left({\frac {a}{n}}\right)$ $\left({\frac {a}{n}}\right)=1$

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

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

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 el primo 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 módulo n cuadrático sin residuos , y no existe ningún algoritmo determinista eficiente conocido para hacerlo. Pero como la mitad de los números entre 1 y n no son residuos, seleccionar números x al azar y calcular el símbolo de Legendre hasta que se encuentre un no residuo rápidamente producirá uno. Una ligera variante de este algoritmo es el algoritmo Tonelli-Shanks . $\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 py "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 analizó 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 uno o no. $\left({\tfrac {a}{n}}\right)=-1$ $\left({\tfrac {a}{n/2}}\right)=-1$ $\left({\tfrac {a}{n}}\right)=1$ $\left({\tfrac {a}{n/2}}\right)=1$

Si no se conoce la factorización completa de n , y 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 problema podría usarse para resolver el otro eficientemente). $\left({\tfrac {a}{n}}\right)=1$ $\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 hay un algoritmo eficiente para encontrar el módulo de raíces cuadradas de un número compuesto. El artículo congruencia de cuadrados analiza cómo encontrar dos números xey donde $x 2 \equiv y 2 (mod n)$ y $x \neq \pm 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 no igual al que originalmente elevamos al cuadrado (o su módulo 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 buscador de raíces (por ejemplo, ¿devuelve todas las raíces? ¿solo la más pequeña? ¿una aleatoria?), pero será eficiente. ^[35]

Determinar si a es un módulo n con residuo o sin residuo cuadrático (denotado $como R n$ o $N n)$ se puede hacer 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 sí lo es.

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

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

Sea $n > 1$ y $mcd(a, n) = 1$ . Entonces $x 2 \equiv a (mod n)$ tiene solución si y sólo si:

El símbolo de Legendre para todos los divisores primos impares p de n . $\left({\tfrac {a}{p}}\right)=1$
$a \equiv 1 (mod 4)$ si n es divisible por 4 pero no por 8; o $a \equiv 1 (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 se puede reducir a $a / m \equiv x 2 / 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, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ... (secuencia A000224 en el OEIS )

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

Aplicaciones de residuos cuadráticos.

Acústica

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

Teoría de grafos

Los gráficos de Paley son gráficos densos no dirigidos, uno para cada primo p ≡ 1 (mod 4), que forman una familia infinita de gráficos 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 encontrar una raíz cuadrada de un número módulo un compuesto grande n es equivalente a factorizar (que se cree ampliamente que es un problema difícil ) se ha utilizado para construir esquemas criptográficos como el criptosistema Rabin y la transferencia ajena . El problema de la residuosidad cuadrática es la base del criptosistema Goldwasser-Micali .

El logaritmo discreto es un problema similar que también se utiliza 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 calcular o no ( a | p ) correctamente. La prueba de primalidad de Solovay-Strassen para determinar si un número dado n es primo o compuesto selecciona una a aleatoria 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 están de acuerdo, n puede ser compuesto o primo. Para un n compuesto al menos 1/2, los valores de a en el rango 2, 3, ..., n − 1 devolverán " n es compuesto"; para el número primo n ninguno lo hará. Si, después de usar muchos valores diferentes de a , no se ha demostrado que n sea compuesto, se le llama " 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 " n es primo o GRH es falso". Si alguna vez ocurre el segundo resultado 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 ^[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 , el tamiz cuadrático y el tamiz de campo numérico ) generan pequeños residuos cuadráticos (módulo del número que se factoriza) en un intento de encontrar una congruencia de cuadrados que produzca una factorización. El tamiz de campos numéricos es el algoritmo de factorización de propósito general más rápido conocido.

Tabla de residuos cuadráticos.

La siguiente tabla (secuencia A096008 en 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 residuos cuadráticos distintos de cero, consulte OEIS : A046071 ).

Ver también

Notas

^ Lemmemeyer, cap. 1
^ Lemmermeyer, págs. 6 a 8, pág. 16 y siguientes
^ Gauss, DA, arte. 94
^ ab Gauss, DA, arte. 96
^ ab Gauss, DA, arte. 98
^ Gauss, DA, artículo 111
^ Gauss, DA, arte. 103
^ ab Gauss, DA, arte. 101
^ Gauss, DA, arte. 102
^ por ejemplo, Irlanda y Rosen 1990, p. 50
^ Gauss, DA, arte. 131
^ por ejemplo, Hardy y Wright lo usan
^ Gauss, DA, artículos 230 y siguientes.
^ Esta extensión del dominio es necesaria para definir funciones L.
^ Consulte el símbolo de Legendre#Propiedades del símbolo de Legendre para ver ejemplos
^ Lemmermeyer, págs. 111 – final
^ Davenport 2000, págs. 8–9, 43–51. Estos son resultados clásicos.
^ Davenport 2000, págs. 49–51 (conjeturada por Jacobi , probada por Dirichlet)
^ Davenport 2000, pag. 9
^ Lemmermeyer, pag. 29 ej. 1,22; cf. págs. 26 y 27, cap. 10
^ Crandall y Pomerance, ex 2.38, págs. 106-108
^ Gauss, Theorie der biquadratischen Reste, Erste Abhandlung (págs. 511–533 de Untersuchungen über hohere Arithmetik)
^ Crandall & Pomerance, ex 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 esa misma cantidad de cruces. La desigualdad VP descarta eso para los residuos.
^ Davenport 2000, págs. 135-137 (prueba de P – V (de hecho, la O grande puede reemplazarse por 2); referencias de revistas de Paley, Montgomery y Schur)
^ Planet Math: prueba de la desigualdad Pólya-Vinogradov en enlaces externos. La demostración ocupa una página y sólo requiere datos elementales sobre las sumas gaussianas.
^ Pomerance y Crandall, ex 2,38 págs. 106-108. resultado de T. Cochrane, "Sobre una desigualdad trigonométrica de Vinogradov", J. Number Theory , 27:9–16, 1987
^ ab Friedlander, John B .; Iwaniec, Henryk (2010). Ópera De Cribro . Sociedad Matemática Estadounidense . pag. 156.ISBN 978-0-8218-4970-5. Zbl 1226.11099.
^ Montgomery, Hugh L. (1994). Diez conferencias sobre la interfaz entre la teoría analítica de números y el análisis armónico . Sociedad Matemática Estadounidense . pag. 176.ISBN 0-8218-0737-4. Zbl 0814.11001.
^ Bateman, Paul T .; Diamante, Harold G. (2004). Teoría analítica de números . Científico mundial. pag. 250.ISBN 981-256-080-7. Zbl 1074.11001.
^ 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 .
^ Bach y Shallit 1996, pág. 113; La informática requiere O (log a log n ) pasos $\left({\frac {a}{n}}\right)$
^ Lemmermeyer, pag. 29
^ Bach y Shallit 1996, pág. 156 y siguientes; el algoritmo requiere O(log ⁴n ) pasos.
^ Bach y Shallit 1996, pág. 156 y siguientes; el algoritmo requiere O(log ³ n ) pasos y tampoco es determinista.
^ Crandall y Pomerance, ej. 6.5 y 6.6, p.273
^ Manders y Adleman 1978
^ Burton, David (2007). Teoría elemental de números . Nueva York: McGraw Hill. pag. 195.
^ Stangl, Walter D. (octubre de 1996), "Contar cuadrados en ℤn" (PDF) , Revista de Matemáticas , 69 (4): 285–289, doi :10.2307/2690536, JSTOR 2690536
^ Walker, R. "El diseño y aplicación de elementos difusores acústicos modulares" (PDF) . Departamento de Investigación de la BBC . Consultado el 25 de octubre de 2016 .
^ Bach y Shallit 1996, pág. 113
^ Bach y Shallit 1996, págs. 109-110; El criterio de Euler requiere O(log ³ n ) pasos
^ 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 la reciprocidad cuadrática, la determinación del signo de la suma de Gauss , las investigaciones sobre la reciprocidad bicuadrática y notas inéditas.

Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae , 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. Yo, 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 ed.), 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 integridad NP , 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), " NP -Problemas de decisión 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". MundoMatemático .
Prueba de la desigualdad de Pólya-Vinogradov en PlanetMath .