Residuo cadrático

número do que o seu cadrado é residuo módulo un enteiro

En teoría de números, un número enteiro q chámase residuo cadrático módulo n se é congruente cun cadrado perfecto módulo n; é dicir, se existe un número enteiro x tal que:

En caso contrario, q sería non residuo cadrático módulo n .

Historia, convencións e feitos elementais

editar

Fermat, Euler, Lagrange, Legendre e outros teóricos dos números dos séculos XVII e XVIII xa estableceron teoremas [1] e formaron conxecturas [2] sobre residuos cadráticos, mais o primeiro tratamento sistemático é o § IV das Disquisitiones Arithmeticae de Gauss (1801). O artigo 95 introduce a terminoloxía «residuo cadrático» e «non residuo cadrático», e establece que se o contexto o deixa claro, poderá abandonarse o adxectivo «cadrático».

Pódese obter unha lista dos residuos cadráticos módulo n simplemente calculando o cadrado dos números 0, 1,... , n − 1. Debido a que a2 ≡ (na)2 (mod n ), a lista de cadrados módulo n é simétrica arredor de n /2. Isto pódese ver na táboa de abaixo.

Módulo un número primo

editar

Módulo un número primo impar p hai (p + 1)/2 residuos (incluíndo 0) e (p - 1)/2 non residuos, segundo o criterio de Euler.

É habitual traballar sen considerar o 0.

Seguindo esta convención, o inverso multiplicativo dun residuo é un residuo e o inverso dun non residuo é un non residuo. [3]

Sen o 0, módulo un número primo impar hai un número igual de residuos e non residuos. [4]

Se p ≡ 1 (mod 4) o negativo dun residuo módulo p é un residuo e o negativo dun non residuo é un non residuo.

O primeiro suplemento [5] á lei da reciprocidade cuadrática é que se p ≡ 1 (mod 4) entón −1 é un residuo cuadrático módulo p, e se p ≡ 3 (mod 4) entón −1 é un non residuo módulo p. Isto implica o seguinte:

Se p ≡ 3 (mod 4) o negativo dun residuo módulo p é un non residuo e o negativo dun non residuo é un residuo.

Módulos de potencias de primos

editar

Todos os cadrados dos impares son ≡ 1 (mod 8) e, polo tanto, tamén ≡ 1 (mod 4). Se a é un número impar e m = 2n, n > 2, daquela a é un residuo módulo m se e só se a ≡ 1 (mod 8). [6]

Por exemplo, mod (32=25) os cadrados dos impares son

12 ≡ 152 ≡ 1
32 ≡ 132 ≡ 9
52 ≡ 112 ≡ 25
72 ≡ 92 ≡ 49 ≡ 17

e os cadrados dos pares son

02 ≡ 82 ≡ 162 ≡ 0
22 ≡ 62 ≡ 102 ≡ 14 2 ≡ 4
42 ≡ 122 ≡ 16.

Polo tanto, un número distinto de cero é un residuo mod 2n, n > 2, se e só se é da forma 4k (8 n + 1).

Un número a coprimo a un primo impar p é un residuo módulo calquera potencia de p se e só se é un residuo módulo p. [7]

Cando o módulo é pn, temos que pka

é un residuo módulo pn se kn
é un non residuo módulo pn se k < n é impar
é un residuo módulo pn se k < n é par e a é un residuo
é un non residuo módulo pn se k < n é par e a é un non residuo. [8]

Teña en conta que as regras son diferentes para potencias de dous e potencias de primos impares.

Módulo unha potencia dun primo impar n = pk, os produtos de residuos e non residuos relativamente primos para p obedecen as mesmas regras que o visto para mod p; p é un non residuo e, en xeral, todos os residuos e non residuos obedecen ás mesmas regras, excepto que os produtos serán cero se a potencia de p no produto ≥ n .

Módulo números compostos que non son unha potencia dun primo

editar

Neste caso temos dous feitos básicos:

Se a é un residuo módulo n, entón a é un residuo módulo   para toda potencia de primo que divida a n.
Se a é un non residuo módulo n, entón a é un non residuo módulo p k para polo menos unha potencia de primo que divida a n.

Modulo un número composto hai tres posibilidades:

O produto de dous residuos é un residuo.

O produto dun residuo e un non residuo pode ser un residuo, un non residuo ou cero.

O produto de dous non residuos pode ser un residuo, un non residuo ou cero.

Exemplos:

A partir da táboa de módulo 6: 1, 2, 3, 4, 5 (residuos en grosa). O produto do residuo 3 e do non residuo 5 é o residuo 3, mentres que o produto do residuo 4 e do non residuo 2 é o non residuo 2.

.

A partir da táboa do módulo 15: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 (residuos en grosa). O produto dos non residuos 2 e 8 é o residuo 1, mentres que o produto dos non-residuos 2 e 7 é o non residuo 14.

Por esta razón algúns autores [9] engaden á definición de que un residuo cadrático a non só debe ser un cadrado senón que tamén debe ser coprimo co módulo n.

Notacións

editar

Gauss [10] utilizou R e N para indicar residuos e non residuos, respectivamente;

por exemplo, 2 R 7 e 5 N 7, ou 1 R 8 e 3 N 8 .

Aínda que esta notación é compacta e conveniente para algúns propósitos, [11] [12] unha notación máis útil é o símbolo de Legendre, tamén chamado carácter cadrático, que se define para todos os números enteiros a e números primos impares positivos p como

 

Hai dúas razóns polas que os números ≡ 0 (mod p) trátanse especialmente. Como vimos, facilita a formulación de moitas fórmulas e teoremas. A outra razón (relacionada con esta) é que o carácter cadrático é un homomorfismo entre o grupo multiplicativo de números enteiros distintos de cero módulo p e os números complexos baixo multiplicación. Definindo   podemos estender o seu dominio ao semigrupo multiplicativo de todos os números enteiros. [13]

Unha vantaxe desta notación sobre a de Gauss é que o símbolo de Legendre é unha función que se pode usar nas fórmulas. [14] Tamén se pode xeneralizar facilmente a residuos dunha potencia maior. [15]

Co tempo os símbolos de Legendre foron xeneralizándose:

Símbolo de Jacobi: sexa a un número enteiro e n un número natural impar, con factorización   o símbolo de Jacobi sería:

 

sendo   o símbolo de Legendre. Cando n é un número primo impar, os símbolo de Jacobi e de Legendre coinciden.

Símbolo de Kronecker: sexa   un enteiro distinto de 0, con factorización   onde  . Sexa   un enteiro, o símbolo de Kronecker sería:

 

E nos tres casos con cadansúa lei de reciprocidade cadrática.

Distribución dos residuos cadráticos

editar

Existen certas regularidades na distribución dos residuos cadráticos.

A primeira destas regularidades provén do traballo de Peter Gustav Lejeune Dirichlet (na década de 1830) sobre a fórmula analítica para o número de clase das formas cadráticas binarias. [16] Sexa q un número primo, s unha variable complexa e definimos unha función L de Dirichlet como

 

Dirichlet demostrou que se q ≡ 3 (mod 4), daquela

 

Polo tanto, neste caso, a suma dos residuos cadráticos menos a suma dos non residuos no rango 1, 2, ... , q − 1 é un número negativo.

Por exemplo, módulo 11,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (residuos en grosa)
1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, e a diferenza é − 11.

Dirichlet tamén demostrou que para o primo q ≡ 3 (mod 4),

 

Isto implica que hai máis residuos cuadráticos que non residuos entre os números 1, 2,... , ( q − 1)/2.

Por exemplo, no módulo 11 hai catro residuos inferiores a 6 (é dicir, 1, 3, 4 e 5), pero só un non residuo (o 2).

Todas as demostracións coñecidas destes dous teoremas dependen da análise; ninguén publicou nunca unha proba simple ou directa de ningunha das dúas afirmacións. [17]

Lei da reciprocidade cuadrática

editar

Se p e q son primos impares, entón:

( (p é un residuo cuadrático mod q) se e só se (q é un residuo cuadrático mod p ) ) se e só se (polo menos un de p e q é congruente con 1 mod 4).

É dicir:

 

onde   é o símbolo de Legendre .

Así, para os números a e os primos impares p que non dividen a, temos:

a a é un residuo cuadrático mod p se e só se a a é un residuo cuadrático mod p se e só se
1 (todo p primo) −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 p primo) −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 p primo) −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)

Atopar raíces cadradas módulo n

editar

Aquí aparece unha diferenza importante entre os módulos primos e compostos. Módulo un primo p, un residuo cadrático a ten cero raíces se a N p, unha se a ≡ 0 (mod p) ou dúas se a R p e mcd(a, p) = 1.

En xeral, se escribimos un módulo composto n na súa factorización en primos  , e hai   raíces módulo  ,   módulo  ,   módulo  ,... , haberá o produto      ... raíces módulo n.

A forma teórica de combinar solucións módulo potencias primas para facer solucións módulo n chámase teorema chinés do resto. [18]

Por exemplo:

Solucionar x2 ≡ 6 (mod 15).
x2 ≡ 6 (mod 3) ten unha solución = 0; e por outra parte x2 ≡ 6 (mod 5) ten dúas = 1 e 4.
e hai dúas solucións módulo 15, que son 6 e 9 (calculadas co teorema chinés do resto).
Solucionar x2 ≡ 4 (mod 15).
x2 ≡ 4 (mod 3) ten dúas solucións = 1 e 2; e por outra parte x2 ≡ 4 (mod 5) ten outras dúas = 2 e 3.
e hai catro solucións módulo 15, é dicir, 2, 7, 8 e 13 (calculadas co teorema chinés do resto).
Solucionar x2 ≡ 7 (mod 15).
x2 ≡ 7 (mod 3) ten dúas solucións, 1 e 2; e despois temos x2 ≡ 7 (mod 5) non ten solucións.
e por tanto non hai solucións módulo 15.


Módulo de potencia de primo

editar

Primeiro de todo, se o módulo n é primo, o símbolo de Legendre   pódese calcular rapidamente usando unha variante do algoritmo de Euclides [19] ou o criterio de Euler . Se é −1 non hai solución. En segundo lugar, asumindo que  , se n ≡ 3 (mod 4), Lagrange descubriu que as solucións están dadas por

 

e Legendre atopou unha solución similar [20] se n ≡ 5 (mod 8):

 

Para un primo de tipo n ≡ 1 (mod 8), porén, non hai unha fórmula coñecida. Tonelli [21] (en 1891) e Cipolla [22] atoparon algoritmos eficientes que funcionan para tódolos módulos primos. Ambos algoritmos requiren atopar un non residuo módulo n, e non hai un algoritmo determinista eficiente coñecido para facelo. Mais como a metade dos números entre 1 e n son non residuos, escollemos números x ao azar e calculando o símbolo de Legendre   ata que se atope un non residuo rapidamente. Unha pequena variante deste algoritmo é o algoritmo de Tonelli–Shanks .

Se o módulo n é unha potencia de primo n = p e, pódese atopar unha solución módulo p e "elevarse" a unha solución módulo n usando o lema de Hensel ou un algoritmo de Gauss. [7]

Módulo composto

editar

Se o módulo n foi factorizado en potencias primas, a solución foi discutida anteriormente.

Se n non é congruente con 2 módulo 4 e o símbolo de Kronecker   daquela non hai solución. Se n é congruente con 2 módulo 4 e  , daquela tampouco non hai solución. Se n non é congruente con 2 módulo 4 e  , ou n é congruente con 2 módulo 4 e  , pode haber ou non.

Se non se coñece a factorización completa de n, e   e n non é congruente con 2 módulo 4, ou n é congruente con 2 módulo 4 e  , sábese que o problema é equivalente á factorización de n (é dicir, unha solución eficiente a calquera dos problemas podería usarse para resolver o outro de forma eficiente).

O artigo congruencia de cadrados analiza como atopar dous números x e y onde x2y2 (mod n) e x ≠ ±y é suficiente para factorizar n de forma eficiente. [23]

Determinar se a é un residuo cuadrático ou non residuo módulo n pódese facer de forma eficiente para n primo calculando o símbolo de Legendre. Non obstante, para o composto n, isto forma o problema dos residuos cuadrático, asumíndose que é bastante difícil.

En xeral, para determinar se a é un residuo cuadrático módulo un n composto, pódese usar o seguinte teorema: [24]

Sexa n > 1 e gcd(a,n) = 1 . Entón x2a (mod n) ten solución se e só se:

  • O símbolo Legendre   para todos os divisores primos impares p de n .
  • a ≡ 1 (mod 4) se n é divisible por 4 mais non por 8; ou a ≡ 1 (mod 8) se n é divisible por 8.

Aplicacións dos residuos cadráticos

editar

Acústica

editar

Os difusores de son baseáronse nos conceptos de raíces módulo n e residuos cadráticos. [25]

Teoría de grafos

editar

Os grafos de Paley son grafos densos e non dirixidos, un por cada primo p ≡ 1 (mod 4), que forman unha familia infinita de grafos de conferencia, que dan lugar a unha familia infinita de matrices de conferencia simétricas.

Criptografía

editar

O feito de que atopar unha raíz cadrada dun número módulo un composto n moi grande é equivalente á factorización (o cal considérase un problema difícil), utilizouse para construír esquemas criptográficos como o sistema criptográfico Rabin e a transferencia incosciente. O problema dos residuos cuadráticos é a base do sistema criptográfico Goldwasser-Micali .

Test de primalidade

editar

O criterio de Euler é unha fórmula para calcular o símbolo de Legendre (a|p) onde p é primo. Se p é composto, a fórmula pode calcular correctamente (a|p) ou non. A proba de primalidade de Solovay-Strassen para determinar se un determinado número n é primo ou composto elixe un a aleatorio e calcula (a|n) usando unha modificación do algoritmo de Euclides, [26] e tamén usando o criterio de Euler. [27] Se os resultados discrepan, n é composto; se coinciden, n pode ser composto ou primo. Para un composto n polo menos a metade dos valores de a no intervalo 2, 3,... , n − 1 devolverá "n é composto"; para un primo n non devolve ningún. Se despois de usar moitos valores diferentes de a, n non se demostrou composto, denomínase "primo probable".

O test de primalidade de Miller-Rabin baséase nos mesmos principios. Hai unha versión determinista do mesmo, pero a proba de que funciona depende da hipótese xeneralizada de Riemann; a saída desta proba é "n é definitivamente composto" ou "n é primo ou a GRH é falsa".

Táboa de residuos cadráticos

editar

A seguinte táboa (secuencia A096008 na OEIS) enumera os residuos cadráticos mod 1 a 75 (un número rubio significa que non é coprimo con n ). (Para os residuos cadráticos coprimos con n, ver OEIS : A096103, e para os residuos cadráticos distintos de cero, ver (secuencia A046071 na OEIS).)

n residuos cadráticos mod n n residuos cadráticoss mod n n residuos cadráticos mod n
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, 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, 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, 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
Residuos cadráticos (véxase tamén (secuencia A048152 na OEIS), (secuencia A343720 na OEIS))
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
x2 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
  1. Lemmemeyer, Ch. 1
  2. Lemmermeyer, pp 6–8, p. 16 ff
  3. Gauss, DA, art. 98
  4. Gauss, DA, art. 96
  5. Gauss, DA, art 111
  6. Gauss, DA, art. 103
  7. 7,0 7,1 Gauss, DA, art. 101
  8. Gauss, DA, art. 102
  9. e.g., Ireland & Rosen 1990, p. 50
  10. Gauss, DA, art. 131
  11. e.g. Hardy and Wright use it
  12. Gauss, DA, art 230 ff.
  13. This extension of the domain is necessary for defining L functions.
  14. Véxase Legendre symbol#Properties of the Legendre symbol para exemplos
  15. Lemmermeyer, pp 111–end
  16. Davenport 2000, p. 8–9, 43–51. These are classical results.
  17. Davenport 2000, p. 9
  18. Bach & Shallit 1996, p. 104 ff; it requires O(log2 m) steps where m is the number of primes dividing n.
  19. Bach & Shallit 1996, p. 113; computing   requires O(log a log n) steps
  20. Lemmermeyer, p. 29
  21. Bach & Shallit 1996, p. 156 ff; the algorithm requires O(log4n) steps.
  22. Bach & Shallit 1996, p. 156 ff; o algoritmo require O(log3 n) pasos e non é determinístico.
  23. Crandall & Pomerance, ex. 6.5 & 6.6, p.273
  24. . 2007. p. 195.  Falta o |title= (Axuda)
  25. (PDF) http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf.  Falta o |title= (Axuda)
  26. Bach & Shallit 1996, p. 113
  27. Bach & Shallit 1996, p. 109–110; Euler's criterion requires O(log3 n) steps

Véxase tamén

editar

Bibliografía

editar

Outros artigos

editar

Ligazóns externas

editar