Resíduo quadrático - Quadratic residue

Na teoria dos números , um inteiro q é chamado de resíduo quadrático módulo n se for congruente a um quadrado perfeito módulo n ; ou seja, se existe um inteiro x tal que:

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

Caso contrário, q é chamado de módulo não residual quadrático n .

Originalmente um conceito matemático abstrato do ramo da teoria dos números conhecido como aritmética modular , os resíduos quadráticos são agora usados em aplicações que vão desde a engenharia acústica até a criptografia e a fatoração de grandes números .

História, convenções e fatos elementares

Fermat , Euler , Lagrange , Legendre , e outros teóricos de números no séculos 17 e 18 estabelecido teoremas e formou conjecturas sobre resíduos quadráticos, mas o primeiro tratamento sistemático é § IV de Gauss 's Disquisitiones Arithmeticae (1801). O Artigo 95 introduz a terminologia "resíduo quadrático" e "não-resíduo quadrático", e afirma que, se o contexto deixar claro, o adjetivo "quadrático" pode ser eliminado.

Para um dado n, uma lista de resíduos quadráticos módulo n pode ser obtida simplesmente elevando ao quadrado os números 0, 1, ..., n - 1 . Como a ² ≡ ( n - a ) ² (mod n ), a lista de quadrados módulo n é simétrica em torno de n / 2, e a lista só precisa ser tão alta. Isso pode ser visto na tabela abaixo .

Assim, o número de resíduos quadráticos módulo n não pode exceder n / 2 + 1 ( n par) ou ( n + 1) / 2 ( n ímpar).

O produto de dois resíduos é sempre um resíduo.

Módulo principal

Módulo 2, todo inteiro é um resíduo quadrático.

Módulo um número primo ímpar p onde há ( p + 1) / 2 resíduos (incluindo 0) e ( p - 1) / 2 não- resíduos , pelo critério de Euler . Neste caso, costuma-se considerar 0 como um caso especial e trabalhar dentro do grupo multiplicativo de elementos diferentes de zero do campo Z / p Z . (Em outras palavras, todas as classes de congruência, exceto o módulo p zero, têm um inverso multiplicativo. Isso não é verdade para os módulos compostos.)

Seguindo essa convenção, o inverso multiplicativo de um resíduo é um resíduo e o inverso de um não-resíduo é um não-resíduo.

Seguindo essa convenção, módulo um número primo ímpar, há um número igual de resíduos e não-resíduos.

Módulo a prime, o produto de dois não-resíduos é um resíduo e o produto de um não-resíduo e um resíduo (diferente de zero) é um não-resíduo.

O primeiro suplemento à lei da reciprocidade quadrática é que se p ≡ 1 (mod 4) então −1 é um módulo de resíduo quadrático p , e se p ≡ 3 (mod 4) então −1 é um módulo não residual p . Isso implica o seguinte:

Se p ≡ 1 (mod 4), o negativo de um resíduo módulo p é um resíduo e o negativo de um não- resíduo é um não-resíduo.

Se p ≡ 3 (mod 4), o negativo de um resíduo módulo p é um não- resíduo e o negativo de um não-resíduo é um resíduo.

Módulo de potência principal

Todos os quadrados ímpares são ≡ 1 (mod 8) e, portanto, também ≡ 1 (mod 4). Se um é um número impar e m = 8, 16, ou pouco maior potência de dois, em seguida, um é um resíduo módulo m se e apenas se um ≡ 1 (mod 8).

Por exemplo, mod (32) os quadrados ímpares são

1 ² ≡ 15 ² ≡ 1

3 ² ≡ 13 ² ≡ 9

5 ² ≡ 11 ² ≡ 25

7 ² ≡ 9 ² ≡ 49 ≡ 17

e os pares são

0 ² ≡ 8 ² ≡ 16 ² ≡ 0

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

4 ² ≡ 12 ² ≡ 16.

Portanto, um número diferente de zero é um resíduo mod 8, 16, etc., se e somente se for da forma 4 ^k (8 n + 1).

Um número um relativamente primos para um primo ímpar p é um módulo resíduo qualquer poder de p se e só se for um módulo resíduo p .

Se o módulo for p ⁿ ,

então p ^k a

é um módulo de resíduo p ⁿ se k ≥ n

é um módulo não residual p ⁿ se k < n for ímpar

é um módulo de resíduo p ⁿ se k < n for par e a for um resíduo

é um módulo não residual p ⁿ se k < n for par e a for um não residual.

Observe que as regras são diferentes para potências de dois e potências de primos ímpares.

Módulo uma potência primária ímpar n = p ^k , os produtos de resíduos e não-resíduos relativamente primos para p obedecem às mesmas regras que o mod p ; p é um não-resíduo e, em geral, todos os resíduos e não-resíduos obedecem às mesmas regras, exceto que os produtos serão zero se a potência de p no produto ≥ n .

Módulo 8, o produto dos não-resíduos 3 e 5 é o não-resíduo 7, e da mesma forma para as permutações de 3, 5 e 7. Na verdade, o grupo multiplicativo dos não-resíduos e 1 forma o quatro grupo de Klein .

Módulo composto não é uma potência principal

O fato básico neste caso é

se a é um módulo residual n , então a é um módulo residual p ^k para cada potência primária dividindo n .

se a é um módulo não residual n , então a é um módulo não residual p ^k para pelo menos uma potência principal dividindo n .

Módulo um número composto, o produto de dois resíduos é um resíduo. O produto de um resíduo e um não-resíduo pode ser um resíduo, um não-resíduo ou zero.

Por exemplo, da tabela para o módulo 6 1 , 2, 3 , 4 , 5 (resíduos em negrito ).

O produto do resíduo 3 e do não-resíduo 5 é o resíduo 3, enquanto o produto do resíduo 4 e do não-resíduo 2 é o não-resíduo 2.

Além disso, o produto de dois não-resíduos pode ser um resíduo, um não-resíduo ou zero.

Por exemplo, da tabela para o módulo 15 1 , 2, 3, 4 , 5, 6 , 7, 8, 9 , 10 , 11, 12, 13, 14 (resíduos em negrito ).

O produto dos não-resíduos 2 e 8 é o resíduo 1, enquanto o produto dos não-resíduos 2 e 7 é o não-resíduo 14.

Este fenômeno pode ser melhor descrito usando o vocabulário da álgebra abstrata. As classes de congruência relativamente primos ao módulo são um grupo em multiplicação, chamado o grupo de unidades do anel Z / n Z , e os quadrados são um subgrupo dele. Diferentes não-resíduos podem pertencer a diferentes cosets , e não existe uma regra simples que preveja em qual deles seu produto estará. Módulo a primo, há apenas o subgrupo de quadrados e um único coset.

O fato de que, por exemplo, módulo 15 o produto dos não-resíduos 3 e 5, ou do não-resíduo 5 e o resíduo 9, ou os dois resíduos 9 e 10 são todos zero vem de trabalhar no anel completo Z / n Z , que tem zero divisores para composto n .

Por esta razão, alguns autores acrescentam à definição que um resíduo quadrático a não deve ser apenas um quadrado, mas também deve ser relativamente primo ao módulo n . ( a é coprime para n se e somente se a ² for coprime para n .)

Embora torne as coisas mais organizadas, este artigo não insiste que os resíduos devem ser coprimos do módulo.

Notações

Gauss usou $R$ e $N$ para denotar residuosidade e não residuosidade, respectivamente;

por exemplo,

2 R 7

e

5 N 7

, ou

1 R 8

e

3 N 8

.

Embora essa notação seja compacta e conveniente para alguns propósitos, uma notação mais útil é o símbolo de Legendre , também chamado de caractere quadrático , que é definido para todos os inteiros $a$ e números primos ímpares positivos $p$ como

{\ displaystyle \ left ({\ frac {a} {p}} \ right) = {\ begin {cases} \; \; \, 0 & {\ text {if}} p {\ text {divide}} a \ \ +1 & {\ text {if}} a \ operatorname {R} p {\ text {e}} p {\ text {não divide}} a \\ - 1 & {\ text {if}} a \ operatorname { N} p {\ text {e}} p {\ text {não divide}} a \ end {casos}}}

Existem duas razões pelas quais os números ≡ 0 (mod $p$ ) são tratados de maneira especial. Como vimos, isso torna muitas fórmulas e teoremas mais fáceis de definir. A outra razão (relacionada) é que o caractere quadrático é um homomorfismo do grupo multiplicativo de classes de congruência diferente de zero módulo $p$ para os números complexos sob multiplicação. A configuração permite que seu domínio seja estendido ao semigrupo multiplicativo de todos os inteiros. ${\ displaystyle ({\ tfrac {np} {p}}) = 0}$

Uma vantagem dessa notação sobre a de Gauss é que o símbolo de Legendre é uma função que pode ser usada em fórmulas. Também pode ser facilmente generalizado para resíduos cúbicos , quárticos e de maior potência.

Há uma generalização do símbolo de Legendre para valores compostos de $p$ , o símbolo de Jacobi , mas suas propriedades não são tão simples: se $m$ é composto e o símbolo de Jacobi então $a$ $N$ $m$ , e se $a$ $R$ $m$ então, mas se não saber se $um$ $R$ $m$ ou $um$ $N$ $m$ . Por exemplo: e , mas $2 N 15$ e $4 R 15$ . Se $m$ é primo, os símbolos de Jacobi e Legendre concordam. ${\ 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}$

Distribuição de resíduos quadráticos

Embora os resíduos quadráticos parecem ocorrer de forma bastante ao acaso padrão de módulo n , e isto tem sido explorado em tais aplicações como acústica e criptografia , a sua distribuição também exibe algumas regularidades marcantes.

Usando o teorema de Dirichlet sobre os primos em progressões aritméticas , a lei da reciprocidade quadrática e o teorema do resto chinês (CRT), é fácil ver que para qualquer M > 0 existem primos p tais que os números 1, 2, ..., M são todos os resíduos módulo p .

Por exemplo, se p ≡ 1 (mod 8), (mod 12), (mod 5) e (mod 28), então pela lei da reciprocidade quadrática 2, 3, 5 e 7 serão todos resíduos módulo p , e portanto, todos os números de 1 a 10 serão. O CRT diz que isso é o mesmo que p ≡ 1 (mod 840), e o teorema de Dirichlet diz que há um número infinito de primos dessa forma. 2521 é o menor e, de fato, 1 ² ≡ 1, 1046 ² ≡ 2, 123 ² ≡ 3, 2 ² ≡ 4, 643 ² ≡ 5, 87 ² ≡ 6, 668 ² ≡ 7, 429 ² ≡ 8, 3 ² ≡ 9 e 529 ² ≡ 10 (mod 2521).

Fórmulas de Dirichlet

A primeira dessas regularidades deriva do trabalho de Peter Gustav Lejeune Dirichlet (na década de 1830) sobre a fórmula analítica para o número de classe de formas quadráticas binárias . Seja q um número primo, s uma variável complexa, e defina uma função L de Dirichlet como

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

Dirichlet mostrou que se q ≡ 3 (mod 4), então

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

Portanto, neste caso (primo q ≡ 3 (mod 4)), a soma dos resíduos quadráticos menos a soma dos não-resíduos no intervalo 1, 2, ..., q - 1 é um número negativo.

Por exemplo, módulo 11,

1 , 2, 3 , 4 , 5 , 6, 7, 8, 9 , 10 (resíduos em negrito )

1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, e a diferença é −11.

Na verdade, a diferença sempre será um múltiplo ímpar de q se q > 3. Em contraste, para o primo q ≡ 1 (mod 4), a soma dos resíduos quadráticos menos a soma dos não-resíduos no intervalo 1, 2,. .., q - 1 é zero, o que implica que ambas as somas são iguais . ${\ displaystyle {\ frac {q (q-1)} {4}}}$

Dirichlet também provou que para o 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.}

Isso implica que há mais resíduos quadráticos do que não-resíduos entre os números 1, 2, ..., ( q - 1) / 2.

Por exemplo, no módulo 11, há quatro resíduos menores que 6 (a saber, 1, 3, 4 e 5), mas apenas um não-resíduo (2).

Um fato intrigante sobre esses dois teoremas é que todas as provas conhecidas dependem de análise; ninguém jamais publicou uma prova simples ou direta de qualquer uma das afirmações.

Lei da reciprocidade quadrática

Se p e q forem primos ímpares, então:

(( p é um resíduo quadrático mod q ) se e somente se ( q é um resíduo quadrático mod p )) se e somente se (pelo menos um de p e q é congruente a 1 mod 4).

Isso é:

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

onde está o símbolo Legendre . ${\ displaystyle \ left ({\ frac {p} {q}} \ right)}$

Assim, para números a e números primos ímpares p que não dividem a :

uma	a é um resíduo quadrático mod p se e somente se	uma	a é um resíduo quadrático mod p se e somente se
1	(todo primo p )	-1	p ≡ 1 (mod 4)
2	p ≡ 1, 7 (mod 8)	-2	p ≡ 1,3 (mod 8)
3	p ≡ 1,11 (mod 12)	-3	p ≡ 1 (mod 3)
4	(todo primo p )	-4	p ≡ 1 (mod 4)
5	p ≡ 1,4 (mod 5)	-5	p ≡ 1, 3, 7, 9 (mod 20)
6	p ≡ 1, 5, 19, 23 (mod 24)	-6	p ≡ 1, 5, 7, 11 (mod 24)
7	p ≡ 1, 3, 9, 19, 25, 27 (mod 28)	-7	p ≡ 1, 2, 4 (mod 7)
8	p ≡ 1, 7 (mod 8)	-8	p ≡ 1,3 (mod 8)
9	(todo primo p )	-9	p ≡ 1 (mod 4)
10	p ≡ 1, 3, 9, 13, 27, 31, 37, 39 (mod 40)	-10	p ≡ 1, 7, 9, 11, 13, 19, 23, 37 (mod 40)
11	p ≡ 1, 5, 7, 9, 19, 25, 35, 37, 39, 43 (mod 44)	-11	p ≡ 1, 3, 4, 5, 9 (mod 11)
12	p ≡ 1,11 (mod 12)	-12	p ≡ 1 (mod 3)

Pares de resíduos e não-resíduos

Módulo a primo p , o número de pares n , n + 1 onde n R p e n + 1 R p , ou n N p e n + 1 R p , etc., são quase iguais. Mais precisamente, seja p um primo ímpar. Para i , j = 0, 1 defina os 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 \},}

e deixar

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

Isso é,

α ₀₀ é o número de resíduos que são seguidos por um resíduo,

α ₀₁ é o número de resíduos que são seguidos por um não-resíduo,

α ₁₀ é o número de não-resíduos que são seguidos por um resíduo, e

α ₁₁ é o número de não-resíduos seguidos por um não-resíduo.

Então, se p ≡ 1 (mod 4)

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

e se p ≡ 3 (mod 4)

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

Por exemplo: (resíduos em negrito )

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},

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

A ₁₁ = {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},

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

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

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

Gauss (1828) introduziu esse tipo de contagem ao provar que se p ≡ 1 (mod 4) então x ⁴ ≡ 2 (mod p ) pode ser resolvido se e somente se p = a ² + 64 b ² .

A desigualdade Pólya – Vinogradov

Os valores de para valores consecutivos de uma variável aleatória imita, como um cara ou coroa . Especificamente, Pólya e Vinogradov provaram (independentemente) em 1918 que para qualquer caractere Dirichlet não principal χ ( n ) módulo q e quaisquer inteiros M e N , ${\ displaystyle ({\ tfrac {a} {p}})}$

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

na notação O grande . Configuração

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

isso mostra que o número de resíduos quadráticos módulo q em qualquer intervalo de comprimento N é

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

É fácil provar que

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

Na verdade,

{\ 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 e Vaughan melhoraram isso em 1977, mostrando que, se a hipótese generalizada de Riemann for verdadeira, então

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

Este resultado não pode ser substancialmente melhorado, pois Schur provou em 1918 que

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

e Paley provou em 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 infinitamente muitos d > 0.

Menor não-resíduo quadrático

O menor resíduo quadrático mod p é claramente 1. A questão da magnitude do menor não-resíduo quadrático n ( p ) é mais sutil, mas é sempre primo, com 7 aparecendo pela primeira vez em 71.

A desigualdade Pólya – Vinogradov acima nos dá O ( √ p log p ).

A melhor estimativa incondicional é n ( p ) ≪ p ^θ para qualquer θ> 1/4 √ e , obtida por estimativas de Burgess em somas de caracteres .

Assumindo a hipótese de Riemann generalizada , Ankeny obteve n ( p ) ≪ (log p ) ² .

Linnik mostrou que o número de p menor que X tal que n ( p )> X ^ε é limitado por uma constante dependente de ε.

Os menos não-resíduos quadráticos mod p para números primos ímpares p são:

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... (sequência A053760 no OEIS )

Excesso quadrático

Seja p um primo ímpar. O excesso quadrático E ( p ) é o número de resíduos quadráticos no intervalo (0, p / 2) menos o número no intervalo ( p / 2, p ) (sequência A178153 no OEIS ). Para p congruente a 1 mod 4, o excesso é zero, pois −1 é um resíduo quadrático e os resíduos são simétricos sob r ↔ p - r . Para p congruente a 3 mod 4, o excesso E é sempre positivo.

Complexidade de encontrar raízes quadradas

Ou seja, dado um número a e um módulo n , quão difícil é

para dizer se existe um x resolvendo x ² ≡ a (mod n )
assumindo que existe, para calculá-lo?

Uma diferença importante entre os módulos primos e compostos é mostrada aqui. Módulo a primo p , um resíduo quadrático a tem 1 + ( a | p ) raízes (ou seja, zero se a N p , um se a ≡ 0 (mod p ), ou dois se a R p e mdc ( a, p ) = 1.)

Em geral, se um módulo composto n é escrito como um produto de potências de primos distintos, e há n ₁ raízes módulo o primeiro, n ₂ mod o segundo, ..., haverá n ₁n ₂ ... raízes modulo n .

A maneira teórica pela qual as soluções módulo e as potências primárias são combinadas para formar as soluções módulo n é chamada de teorema do resto chinês ; pode ser implementado com um algoritmo eficiente.

Por exemplo:

Resolva x ² ≡ 6 (mod 15).

x ² ≡ 6 (mod 3) tem uma solução, 0; x ² ≡ 6 (mod 5) tem dois, 1 e 4.

e há duas soluções módulo 15, ou seja, 6 e 9.

Resolva x ² ≡ 4 (mod 15).

x ² ≡ 4 (mod 3) tem duas soluções, 1 e 2; x ² ≡ 4 (mod 5) tem dois, 2 e 3.

e há quatro soluções módulo 15, a saber 2, 7, 8 e 13.

Resolva x ² ≡ 7 (mod 15).

x ² ≡ 7 (mod 3) tem duas soluções, 1 e 2; x ² ≡ 7 (mod 5) não tem soluções.

e não há soluções módulo 15.

Módulo de potência principal ou principal

Em primeiro lugar, se o módulo n for primo, o símbolo de Legendre pode ser rapidamente calculado usando uma variação do algoritmo de Euclides ou o critério de Euler . Se for -1, não há solução. Em segundo lugar, assumindo que , se n ≡ 3 (mod 4), Lagrange descobriu que as soluções são 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}},}

e Legendre encontrou uma solução semelhante se n ≡ 5 (mod 8):

{\ displaystyle x \ equiv {\ begin {cases} \ pm \; a ^ {(n + 3) / 8} {\ pmod {n}} & {\ text {if}} a {\ text {é um quártico módulo de resíduo}} n \\\ pm \; a ^ {(n + 3) / 8} 2 ^ {(n-1) / 4} {\ pmod {n}} & {\ text {if}} a { \ text {é um módulo quártico de não resíduo}} n \ end {casos}}}

Para o primo n ≡ 1 (mod 8), entretanto, não há fórmula conhecida. Tonelli (em 1891) e Cipolla encontraram algoritmos eficientes que funcionam para todos os módulos primos. Ambos os algoritmos requerem encontrar um módulo n não residual quadrático , e não existe um algoritmo determinístico eficiente conhecido para fazer isso. Mas, como metade dos números entre 1 e n são não-residuais, escolher números x aleatoriamente e calcular o símbolo de Legendre até que um não-resíduo seja encontrado rapidamente produzirá um. Uma ligeira variante desse algoritmo é o algoritmo de Tonelli-Shanks . ${\ displaystyle \ left ({\ frac {x} {n}} \ right)}$

Se o módulo n é uma potência primária n = p ^e , uma solução pode ser encontrada módulo p e "elevada" para uma solução módulo n usando o lema de Hensel ou um algoritmo de Gauss.

Módulo composto

Se o módulo n foi fatorado em potências primárias, a solução foi discutida acima.

Se n não for congruente com 2 módulo 4 e o símbolo de Kronecker, então não há solução; se n for congruente com 2 módulo 4 e , então também não há solução. Se n não for congruente com 2 módulo 4 e , ou n for congruente com 2 módulo 4 e , pode ou não haver um. ${\ 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}$

Se Fatorização completo de n não é conhecido, e e n não é congruente com duas módulo 4, ou n é congruente com duas módulo 4 e , o problema é conhecido por ser equivalente a fatoração número inteiro de n (isto é uma solução eficaz, quer problema poderia ser usado para resolver o outro de forma eficiente). ${\ displaystyle \ left ({\ tfrac {a} {n}} \ right) = 1}$ ${\ displaystyle \ left ({\ tfrac {a} {n / 2}} \ right) = 1}$

A discussão acima indica como conhecer os fatores de n nos permite encontrar as raízes com eficiência. Digamos que haja um algoritmo eficiente para encontrar raízes quadradas módulo um número composto. O artigo congruência de quadrados discute como encontrar dois números xey onde $x 2 \equiv y 2 (mod n)$ e $x \neq \pm y$ é suficiente para fatorar n eficientemente. Gere um número aleatório, eleve ao quadrado o módulo n e faça com que o algoritmo de raiz quadrada eficiente encontre uma raiz. Repita até que ele retorne um número diferente daquele que originalmente elevamos ao quadrado (ou seu módulo negativo n ), então siga o algoritmo descrito em congruência de quadrados. A eficiência do algoritmo de fatoração depende das características exatas do localizador de raízes (por exemplo, ele retorna todas as raízes? Apenas a menor? Uma aleatória?), Mas será eficiente.

Determinar se um é um resíduo quadrática ou nonresidue módulo n (denotado $um R n$ ou $um N n$ ) pode ser feito de forma eficiente para privilegiada n calculando o símbolo Legendre. No entanto, para o composto n , isso forma o problema de residuosidade quadrática , que não é tão difícil quanto a fatoração, mas é considerado bastante difícil.

Por outro lado, se quisermos saber se existe uma solução para x menor que algum limite c dado , esse problema é NP-completo ; entretanto, este é um problema tratável de parâmetro fixo , onde c é o parâmetro.

Em geral, para determinar se a é um resíduo quadrático módulo composto n , pode-se usar o seguinte teorema:

Seja $n > 1$ e $mdc (a, n) = 1$ . Então $x 2 \equiv a (mod n)$ é solucionável se e somente se:

O símbolo de Legendre para todos os divisores primos ímpares p de n . ${\ displaystyle \ left ({\ tfrac {a} {p}} \ right) = 1}$
$a \equiv 1 (mod 4)$ se n for divisível por 4, mas não por 8; ou $a \equiv 1 (mod 8)$ se n for divisível por 8.

Nota: Este teorema requer essencialmente que a fatoração de n seja conhecida. Observe também que se $mdc (a, n) = m$ , então a congruência pode ser reduzida a $a / m \equiv x 2 / m (mod n / m)$ , mas então isso tira o problema dos resíduos quadráticos (a menos que m seja um quadrado).

O número de resíduos quadráticos

A lista do número de resíduos quadráticos módulo n , para n = 1, 2, 3 ..., é semelhante a:

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ... (sequência A000224 no OEIS )

Uma fórmula para contar o número de quadrados módulo n é fornecida por Stangl.

Aplicações de resíduos quadráticos

Acústica

Os difusores de som foram baseados em conceitos da teoria dos números, como raízes primitivas e resíduos quadráticos.

Teoria dos grafos

Os gráficos de Paley são gráficos densos não direcionados, um para cada primo p ≡ 1 (mod 4), que formam uma família infinita de gráficos de conferência , que produzem uma família infinita de matrizes de conferência simétricas .

Os dígrafos de Paley são análogos direcionados dos gráficos de Paley, um para cada p ≡ 3 (mod 4), que produzem matrizes de conferência anti-simétricas .

A construção desses gráficos utiliza resíduos quadráticos.

Criptografia

O fato de encontrar uma raiz quadrada de um módulo numérico de um grande composto n é equivalente à fatoração (que se acredita ser um problema difícil ) tem sido usado para construir esquemas criptográficos , como o criptosistema Rabin e a transferência inconsciente . O problema da residuosidade quadrática é a base do criptosistema Goldwasser-Micali .

O logaritmo discreto é um problema semelhante que também é usado em criptografia.

Teste de Primalidade

O critério de Euler é uma fórmula para o símbolo de Legendre ( a | p ) onde p é primo. Se p for composto, a fórmula pode ou não calcular ( a | p ) corretamente. O teste primality Solovay-Strassen de se um dado número de n é picaretas primo ou composto uma aleatório um e calcula ( uma | n ) utilizando uma modificação do algoritmo de Euclides, e também usando o critério de Euler. Se os resultados discordarem, n é composto; se eles concordarem, n pode ser composto ou primo. Para um composto n, pelo menos 1/2 dos valores de a no intervalo 2, 3, ..., n - 1 retornará " n é composto"; para o primo n nenhum o fará. Se, depois de usar muitos valores diferentes de a , n foi provado composto, ele é chamado de " primo provável ".

O teste de primalidade de Miller-Rabin é baseado nos mesmos princípios. Há uma versão determinística disso, mas a prova de que funciona depende da hipótese generalizada de Riemann ; a saída desse teste é " n é definitivamente composto" ou "ou n é primo ou o GRH é falso". Se a segunda saída ocorrer para um n composto , o GRH seria falso, o que teria implicações em muitos ramos da matemática.

Fatoração de inteiros

No § VI do Disquisitiones Arithmeticae Gauss discute dois algoritmos de fatoração que usam resíduos quadráticos e a lei da reciprocidade quadrática .

Vários algoritmos de fatoração modernos (incluindo o algoritmo de Dixon , o método de fração contínua , a peneira quadrática e a peneira de campo numérico ) geram pequenos resíduos quadráticos (módulo o número sendo fatorado) em uma tentativa de encontrar uma congruência de quadrados que produzirá uma fatoração. A peneira de campo numérico é o algoritmo de fatoração de propósito geral mais rápido conhecido.

Tabela de resíduos quadráticos

A tabela a seguir (sequência A096008 no OEIS ) lista os resíduos quadráticos mod 1 a 75 (um número vermelho significa que não é coprime com n ). (Para o coprime de resíduos quadráticos para n , consulte OEIS : A096103 , e para resíduos quadráticos diferentes de zero, consulte OEIS : A046071 .)

n	mod n de resíduos quadráticos	n	mod n de resíduos quadráticos	n	mod n de resíduos quadráticos
1	0	26	0 , 1, 3, 4 , 9, 10 , 12 , 13 , 14 , 16 , 17, 22 , 23, 25	51	0 , 1, 4, 9 , 13, 15 , 16, 18 , 19, 21 , 25, 30 , 33 , 34 , 36 , 42 , 43, 49
2	0 , 1	27	0 , 1, 4, 7, 9 , 10, 13, 16, 19, 22, 25	52	0 , 1, 4 , 9, 12 , 13 , 16 , 17, 25, 29, 36 , 40 , 48 , 49
3	0 , 1	28	0 , 1, 4 , 8 , 9, 16 , 21 , 25	53	0 , 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52
4	0 , 1	29	0 , 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28	54	0 , 1, 4 , 7, 9 , 10 , 13, 16 , 19, 22 , 25, 27 , 28 , 31, 34 , 36 , 37, 40 , 43, 46 , 49, 52
5	0 , 1, 4	30	0 , 1, 4 , 6 , 9 , 10 , 15 , 16 , 19, 21 , 24 , 25	55	0 , 1, 4, 5 , 9, 11 , 14, 15 , 16, 20 , 25 , 26, 31, 34, 36, 44 , 45 , 49
6	0 , 1, 3 , 4	31	0 , 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28	56	0 , 1, 4 , 8 , 9, 16 , 25, 28 , 32 , 36 , 44 , 49
7	0 , 1, 2, 4	32	0 , 1, 4 , 9, 16 , 17, 25	57	0 , 1, 4, 6 , 7, 9 , 16, 19 , 24 , 25, 28, 30 , 36 , 39 , 42 , 43, 45 , 49, 54 , 55
8	0 , 1, 4	33	0 , 1, 3 , 4, 9 , 12 , 15 , 16, 22 , 25, 27 , 31	58	0 , 1, 4 , 5, 6 , 7, 9, 13, 16 , 20 , 22 , 23, 24 , 25, 28 , 29 , 30 , 33, 34 , 35, 36 , 38 , 42 , 45, 49, 51, 52 , 53, 54 , 57
9	0 , 1, 4, 7	34	0 , 1, 2 , 4 , 8 , 9, 13, 15, 16 , 17 , 18 , 19, 21, 25, 26 , 30 , 32 , 33	59	0 , 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57
10	0 , 1, 4 , 5 , 6 , 9	35	0 , 1, 4, 9, 11, 14 , 15 , 16, 21 , 25 , 29, 30	60	0 , 1, 4 , 9 , 16 , 21 , 24 , 25 , 36 , 40 , 45 , 49
11	0 , 1, 3, 4, 5, 9	36	0 , 1, 4 , 9 , 13, 16 , 25, 28	61	0 , 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60
12	0 , 1, 4 , 9	37	0 , 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	62	0 , 1, 2 , 4 , 5, 7, 8 , 9, 10 , 14 , 16 , 18 , 19, 20 , 25, 28 , 31 , 32 , 33, 35, 36 , 38 , 39, 40 , 41, 45, 47, 49, 50 , 51, 56 , 59
13	0 , 1, 3, 4, 9, 10, 12	38	0 , 1, 4 , 5, 6 , 7, 9, 11, 16 , 17, 19 , 20 , 23, 24 , 25, 26 , 28 , 30 , 35, 36	63	0 , 1, 4, 7 , 9 , 16, 18 , 22, 25, 28 , 36 , 37, 43, 46, 49 , 58
14	0 , 1, 2 , 4 , 7 , 8 , 9, 11	39	0 , 1, 3 , 4, 9 , 10, 12 , 13 , 16, 22, 25, 27 , 30 , 36	64	0 , 1, 4 , 9, 16 , 17, 25, 33, 36 , 41, 49, 57
15	0 , 1, 4, 6 , 9 , 10	40	0 , 1, 4 , 9, 16 , 20 , 24 , 25 , 36	65	0 , 1, 4, 9, 10 , 14, 16, 25 , 26 , 29, 30 , 35 , 36, 39 , 40 , 49, 51, 51, 55 , 56, 61, 64
16	0 , 1, 4 , 9	41	0 , 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 32, 33, 36, 37, 39, 40	66	0 , 1, 3 , 4 , 9 , 12 , 15 , 16 , 22 , 25, 27 , 31, 33 , 34 , 36 , 37, 42 , 45 , 48 , 49, 55 , 58 , 60 , 64
17	0 , 1, 2, 4, 8, 9, 13, 15, 16	42	0 , 1, 4 , 7 , 9 , 15 , 16 , 18 , 21 , 22 , 25, 28 , 30 , 36 , 37, 39	67	0 , 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65
18	0 , 1, 4 , 7, 9 , 10 , 13, 16	43	0 , 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41	68	0 , 1, 4 , 8 , 9, 13, 16 , 17 , 21, 25, 32 , 33, 36 , 49, 52 , 53, 60 , 64
19	0 , 1, 4, 5, 6, 7, 9, 11, 16, 17	44	0 , 1, 4 , 5, 9, 12 , 16 , 20 , 25, 33 , 36 , 37	69	0 , 1, 3 , 4, 6 , 9 , 12 , 13, 16, 18 , 24 , 25, 27 , 31, 36 , 39 , 46 , 48 , 49, 52, 54 , 55, 58, 64
20	0 , 1, 4 , 5 , 9, 16	45	0 , 1, 4, 9 , 10 , 16, 19, 25 , 31, 34, 36 , 40	70	0 , 1, 4 , 9, 11, 14 , 15 , 16 , 21 , 25 , 29, 30 , 35 , 36 , 39, 44 , 46 , 49 , 50 , 51, 56 , 60 , 64 , 65
21	0 , 1, 4, 7 , 9 , 15 , 16, 18	46	0 , 1, 2 , 3, 4 , 6 , 8 , 9, 12 , 13, 16 , 18 , 23 , 24 , 25, 26 , 27, 29, 31, 32 , 35, 36 , 39, 41	71	0 , 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 29, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 58, 60, 64
22	0 , 1, 3, 4 , 5, 9, 11 , 12 , 14 , 15, 16 , 20	47	0 , 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42	72	0 , 1, 4 , 9 , 16 , 25, 28 , 36 , 40 , 49, 52 , 64
23	0 , 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18	48	0 , 1, 4 , 9 , 16 , 25, 33 , 36	73	0 , 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 25, 27, 32, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 55, 57, 61, 64, 65, 67, 69, 70, 71, 72
24	0 , 1, 4 , 9 , 12 , 16	49	0 , 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 36, 37, 39, 43, 44, 46	74	0 , 1, 3, 4 , 7, 9, 10 , 11, 12 , 16 , 21, 25, 26 , 27, 28 , 30 , 33, 34 , 36 , 37 , 38 , 40 , 41, 44 , 46 , 47, 48 , 49, 53, 58 , 62 , 63, 64 , 65, 67, 70 , 71, 73
25	0 , 1, 4, 6, 9, 11, 14, 16, 19, 21, 24	50	0 , 1, 4 , 6 , 9, 11, 14 , 16 , 19, 21, 24 , 25 , 26 , 29, 31, 34 , 36 , 39, 41, 44 , 46 , 49	75	0 , 1, 4, 6 , 9 , 16, 19, 21 , 24 , 25 , 31, 34, 36 , 39 , 46, 49, 51 , 54 , 61, 64, 66 , 69

Resíduos quadráticos (ver também A048152 , A343720 )
x	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
x ²	1	4	9	16	25	36	49	64	81	100	121	144	169	196	225	256	289	324	361	400	441	484	529	576	625
mod 1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
mod 2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
mod 3	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1
mod 4	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
mod 5	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0
mod 6	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1
mod 7	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2
mod 8	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1
mod 9	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4
mod 10	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5
mod 11	1	4	9	5	3	3	5	9	4	1	0	1	4	9	5	3	3	5	9	4	1	0	1	4	9
mod 12	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1
mod 13	1	4	9	3	12	10	10	12	3	9	4	1	0	1	4	9	3	12	10	10	12	3	9	4	1
mod 14	1	4	9	2	11	8	7	8	11	2	9	4	1	0	1	4	9	2	11	8	7	8	11	2	9
mod 15	1	4	9	1	10	6	4	4	6	10	1	9	4	1	0	1	4	9	1	10	6	4	4	6	10
mod 16	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1
mod 17	1	4	9	16	8	2	15	13	13	15	2	8	16	9	4	1	0	1	4	9	16	8	2	15	13
mod 18	1	4	9	16	7	0	13	10	9	10	13	0	7	16	9	4	1	0	1	4	9	16	7	0	13
mod 19	1	4	9	16	6	17	11	7	5	5	7	11	17	6	16	9	4	1	0	1	4	9	16	6	17
mod 20	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5
mod 21	1	4	9	16	4	15	7	1	18	16	16	18	1	7	15	4	16	9	4	1	0	1	4	9	16
mod 22	1	4	9	16	3	14	5	20	15	12	11	12	15	20	5	14	3	16	9	4	1	0	1	4	9
mod 23	1	4	9	16	2	13	3	18	12	8	6	6	8	12	18	3	13	2	16	9	4	1	0	1	4
mod 24	1	4	9	16	1	12	1	16	9	4	1	0	1	4	9	16	1	12	1	16	9	4	1	0	1
mod 25	1	4	9	16	0	11	24	14	6	0	21	19	19	21	0	6	14	24	11	0	16	9	4	1	0

Veja também

Notas

Referências

O Disquisitiones Arithmeticae foi traduzido do latim ciceroniano de Gauss para o inglês e o alemão . A edição alemã inclui todos os seus artigos sobre a teoria dos números: todas as provas de reciprocidade quadrática, a determinação do sinal da soma de Gauss , as investigações sobre a reciprocidade biquadrática e notas não publicadas.

Gauss, Carl Friedrich; Clarke, Arthur A. (tradutor para o inglês) (1986), Disquisitiones Arithemeticae (Segunda edição corrigida), Nova York: Springer , ISBN 0-387-96254-9
Gauss, Carl Friedrich; Maser, H. (tradutor para o alemão) (1965), Untersuchungen über hohere Arithmetik [ Disquisitiones Arithemeticae & other papers on number theory ] (segunda ed.), New York: Chelsea, ISBN 0-8284-0191-8
Bach, Eric; Shallit, Jeffrey (1996), Efficient Algorithms , Algorithmic Number Theory, I , Cambridge: The MIT Press , ISBN 0-262-02405-5
Crandall, Richard; Pomerance, Carl (2001), Prime Numbers: A Computational Perspective , Nova York: Springer, ISBN 0-387-94777-9
Davenport, Harold (2000), Multiplicative Number Theory (terceira ed.), New York: Springer, ISBN 0-387-95097-4
Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, ISBN 0-7167-1045-5 A7.1: AN1, pág.249.
Hardy, GH ; Wright, EM (1980), Uma Introdução à Teoria dos Números (quinta edição), Oxford: Oxford University Press , ISBN 978-0-19-853171-5
Irlanda, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (segunda edição), New York: Springer, ISBN 0-387-97329-X
Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein , Berlin: Springer, ISBN 3-540-66957-4
Manders, Kenneth L .; Adleman, Leonard (1978), " NP -Complete Decision Problems for Binary Quadratics", Journal of Computer and System Sciences , 16 (2): 168-184, doi : 10.1016 / 0022-0000 (78) 90044-2 .

Languages

In other projects