Artigos

5: Raízes Primitivas e Resíduos Quadráticos


Neste capítulo, discutimos a estrutura multiplicativa do módulo de inteiros (n ). Introduzimos o conceito de ordem do módulo inteiro (n ) e, em seguida, estudamos suas propriedades. Em seguida, definimos o módulo de raízes primitivas (n ) e mostramos como determinar se um inteiro é um módulo primitivo (n ) ou não. Posteriormente, encontramos todos os inteiros positivos com raízes primitivas e provamos resultados relacionados. Definimos o conceito de resíduo quadrático e estabelecemos suas propriedades básicas. Em seguida, apresentamos o símbolo de Legendre e também desenvolvemos suas propriedades básicas. Também introduzimos a lei da reciprocidade quadrática. Posteriormente, generalizamos a noção do símbolo de Legendre para o símbolo de Jacobi e discutimos a lei da reciprocidade relacionada ao símbolo de Jacobi.

  • 5.1: A ordem de inteiros e raízes primitivas
  • 5.2: Raízes primitivas para primos
    Nesta seção, mostramos que todo inteiro possui uma raiz primitiva. Para fazer isso, precisamos introduzir a congruência polinomial.
  • 5.3: A existência de raízes primitivas
    Nesta seção, demonstramos quais inteiros têm raízes primitivas. Começamos mostrando que toda potência de um primo ímpar tem uma raiz primitiva e, para fazer isso, começamos mostrando que todo quadrado de um primo ímpar tem uma raiz primitiva.
  • 5.4: Introdução aos Resíduos Quadráticos e Não Resíduos
  • 5.5: Símbolo de Legendre
    Nesta seção, definimos o símbolo de Legendre que é uma notação associada a resíduos quadráticos e provamos teoremas relacionados.
  • 5.6: A Lei da Reciprocidade Quadrática
    Dado que peq são primos ímpares. Suponha que saibamos se q é um resíduo quadrático de p ou não. A questão que esta seção responderá é se p será um resíduo quadrático de q ou não. Antes de declararmos a lei da reciprocidade quadrática, apresentaremos um Lema de Eisenstein que será usado na prova da lei da reciprocidade. O seguinte lema relacionará o símbolo de Legendre com os pontos da rede de contagem no triângulo.
  • 5.7: Símbolo de Jacobi
    Nesta seção, definimos o símbolo Jacobi, que é uma generalização do símbolo Legendre. O símbolo de Legendre foi definido em termos de primos, enquanto o símbolo de Jacobi será generalizado para quaisquer inteiros ímpares e será dado em termos de símbolo de Legendre.

Soma das raízes primitivas e resíduos quadráticos quando $ p equiv 3 pmod 4 $

Isso parece tão confuso, então vou explicar este tópico realmente interessante (pelo menos muito para mim).

Quando $ p equiv 1 pmod 4 $, é realmente fácil calcular a soma de todos os elementos em $ R_p $, que chamo de 'o sistema residual de raiz primitiva menos positiva $ pmod p

Conteúdo

O número 3 é um módulo raiz primitivo 7 [1] porque

Aqui vemos que o período de 3 k módulo 7 é 6. Os restantes no período, que são 3, 2, 6, 4, 5, 1, formam um rearranjo de todos os resíduos diferentes de zero módulo 7, implicando que 3 é de fato um raiz primitiva módulo 7. Isso deriva do fato de que uma sequência (gk módulo n) sempre se repete após algum valor de k, uma vez que o módulo n produz um número finito de valores. Se g for uma raiz primitiva do módulo n e n for primo, o período de repetição será n - 1. Curiosamente, as permutações criadas dessa maneira (e seus deslocamentos circulares) mostraram ser matrizes de Costas.

Se n for um número inteiro positivo, os inteiros entre 0 e n - 1 que são coprime com n (ou equivalentemente, as classes de congruência com coprime com n) formam um grupo, com o módulo de multiplicação n como a operação é denotado por Z < displaystyle mathbb > ×
n , e é chamado de grupo de unidades módulo n, ou grupo de classes primitivas módulo n. Conforme explicado no artigo grupo multiplicativo de módulo de inteiros n, este grupo multiplicativo (Z < displaystyle mathbb > ×
n ) é cíclico se e apenas se n é igual a 2, 4, p k ou 2 p k, em que p k é a potência de um número primo ímpar. [2] [3] [4] Quando (e somente quando) este grupo Z < displaystyle mathbb > ×
n é cíclico, um gerador deste grupo cíclico é chamado de raiz primitiva módulo n [5] (ou em linguagem mais completa raiz primitiva do módulo de unidade n , enfatizando seu papel como solução fundamental do raízes da unidade equações polinomiais X m
- 1 no ringue Z < displaystyle mathbb > n ), ou simplesmente um elemento primitivo de Z < displaystyle mathbb > ×
n . Quando Z < displaystyle mathbb > ×
n é não cíclico, tais elementos primitivos mod n não existem.

Para qualquer n (seja ou não Z < displaystyle mathbb > ×
n é cíclico), a ordem de (ou seja, o número de elementos em) Z < displaystyle mathbb > ×
n é dado pela função totiente de Euler φ (n) (sequência A000010 no OEIS). E então, o teorema de Euler diz que a φ (n) ≡ 1 (mod n) para cada coprime a n a menor potência de a que é congruente a 1 módulo n é chamada de ordem multiplicativa de um módulo n. Em particular, para a ser uma raiz primitiva módulo n, φ (n) tem que ser a menor potência de a que é congruente a 1 módulo n.

A ordem de 1 é 1, as ordens de 3 e 5 são 6, as ordens de 9 e 11 são 3 e a ordem de 13 é 2. Assim, 3 e 5 são as raízes primitivas módulo 14.

Como não há número cuja ordem seja 8, não há raízes primitivas módulo 15. De fato, λ (15) = 4, onde λ é a função de Carmichael. (sequência A002322 no OEIS)

Tabela de raízes primitivas Editar

Números que têm uma raiz primitiva são

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 98, 101, 103, 106, 107, 109, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 142, 146, 149,. (sequência A033948 no OEIS)

Esta é a tabela de Gauss das raízes primitivas do Disquisitiones. Ao contrário da maioria dos autores modernos, ele nem sempre escolheu a menor raiz primitiva. Em vez disso, ele escolheu 10 se for uma raiz primitiva, se não for, ele escolheu qualquer raiz que fornecesse 10 o menor índice e, se houver mais de um, escolheu o menor deles. Isso não é apenas para tornar o cálculo manual mais fácil, mas é usado no § VI, onde as expansões decimais periódicas de números racionais são investigadas.

As linhas da tabela são rotuladas com as potências principais (exceto 2, 4 e 8) menores que 100 a segunda coluna é um módulo raiz primitivo desse número. As colunas são rotuladas com os primos menores que 100. A entrada na linha p, coluna q é o índice de q módulo p para a raiz fornecida.

Por exemplo, na linha 11, 2 é dado como a raiz primitiva e na coluna 5 a entrada é 4. Isso significa que 2 4 = 16 ≡ 5 (mod 11).

Para o índice de um número composto, adicione os índices de seus fatores primos.

Por exemplo, na linha 11, o índice de 6 é a soma dos índices de 2 e 3: 2 1 + 8 = 512 ≡ 6 (mod 11). O índice de 25 é o dobro do índice 5: 2 8 = 256 ≡ 25 (mod 11). (Claro, desde 25 ≡ 3 (mod 11), a entrada para 3 é 8).

A tabela é simples para as potências primárias ímpares. Mas as potências de 2 (16, 32 e 64) não têm raízes primitivas em vez disso, as potências de 5 respondem por metade dos números ímpares menos que a potência de 2 e seus módulos negativos a potência de 2 são responsáveis ​​por a outra metade. Todas as potências de 5 são congruentes com 5 ou 1 (módulo 8), as colunas encabeçadas por números congruentes com 3 ou 7 (mod 8) contêm o índice de seu negativo. (Sequência A185189 e A185268 em OEIS)

Por exemplo, módulo 32, o índice para 7 é 2 e 5 2 = 25 ≡ −7 (mod 32), mas a entrada para 17 é 4 e 5 4 = 625 ≡ 17 (mod 32).

Raízes e índices primitivos
(outras colunas são os índices de inteiros sob os respectivos títulos das colunas)
n raiz 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
3 2 1
5 2 1 3
7 3 2 1 5
9 2 1 * 5 4
11 2 1 8 4 7
13 6 5 8 9 7 11
16 5 * 3 1 2 1 3
17 10 10 11 7 9 13 12
19 10 17 5 2 12 6 13 8
23 10 8 20 15 21 3 12 17 5
25 2 1 7 * 5 16 19 13 18 11
27 2 1 * 5 16 13 8 15 12 11
29 10 11 27 18 20 23 2 7 15 24
31 17 12 13 20 4 29 23 1 22 21 27
32 5 * 3 1 2 5 7 4 7 6 3 0
37 5 11 34 1 28 6 13 5 25 21 15 27
41 6 26 15 22 39 3 31 33 9 36 7 28 32
43 28 39 17 5 7 6 40 16 29 20 25 32 35 18
47 10 30 18 17 38 27 3 42 29 39 43 5 24 25 37
49 10 2 13 41 * 16 9 31 35 32 24 7 38 27 36 23
53 26 25 9 31 38 46 28 42 41 39 6 45 22 33 30 8
59 10 25 32 34 44 45 28 14 22 27 4 7 41 2 13 53 28
61 10 47 42 14 23 45 20 49 22 39 25 13 33 18 41 40 51 17
64 5 * 3 1 10 5 15 12 7 14 11 8 9 14 13 12 5 1 3
67 12 29 9 39 7 61 23 8 26 20 22 43 44 19 63 64 3 54 5
71 62 58 18 14 33 43 27 7 38 5 4 13 30 55 44 17 59 29 37 11
73 5 8 6 1 33 55 59 21 62 46 35 11 64 4 51 31 53 5 58 50 44
79 29 50 71 34 19 70 74 9 10 52 1 76 23 21 47 55 7 17 75 54 33 4
81 11 25 * 35 22 1 38 15 12 5 7 14 24 29 10 13 45 53 4 20 33 48 52
83 50 3 52 81 24 72 67 4 59 16 36 32 60 38 49 69 13 20 34 53 17 43 47
89 30 72 87 18 7 4 65 82 53 31 29 57 77 67 59 34 10 45 19 32 26 68 46 27
97 10 86 2 11 53 82 83 19 27 79 47 26 41 71 44 60 14 65 32 51 25 20 42 91 18
n raiz 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

A tabela a seguir lista o módulo de raízes primitivas n para n ≤ 72:

n raízes primitivas módulo n pedido (OEIS: A000010) n raízes primitivas módulo n pedido (OEIS: A000010)
1 0 1 37 2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35 36
2 1 1 38 3, 13, 15, 21, 29, 33 18
3 2 2 39 24
4 3 2 40 16
5 2, 3 4 41 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35 40
6 5 2 42 12
7 3, 5 6 43 3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34 42
8 4 44 20
9 2, 5 6 45 24
10 3, 7 4 46 5, 7, 11, 15, 17, 19, 21, 33, 37, 43 22
11 2, 6, 7, 8 10 47 5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45 46
12 4 48 16
13 2, 6, 7, 11 12 49 3, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45, 47 42
14 3, 5 6 50 3, 13, 17, 23, 27, 33, 37, 47 20
15 8 51 32
16 8 52 24
17 3, 5, 6, 7, 10, 11, 12, 14 16 53 2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51 52
18 5, 11 6 54 5, 11, 23, 29, 41, 47 18
19 2, 3, 10, 13, 14, 15 18 55 40
20 8 56 24
21 12 57 36
22 7, 13, 17, 19 10 58 3, 11, 15, 19, 21, 27, 31, 37, 39, 43, 47, 55 28
23 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 22 59 2, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 56 58
24 8 60 16
25 2, 3, 8, 12, 13, 17, 22, 23 20 61 2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59 60
26 7, 11, 15, 19 12 62 3, 11, 13, 17, 21, 43, 53, 55 30
27 2, 5, 11, 14, 20, 23 18 63 36
28 12 64 32
29 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 28 65 48
30 8 66 20
31 3, 11, 12, 13, 17, 21, 22, 24 30 67 2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63 66
32 16 68 32
33 20 69 44
34 3, 5, 7, 11, 23, 27, 29, 31 16 70 24
35 24 71 7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69 70
36 12 72 24

A conjectura de Artin sobre as raízes primitivas afirma que um dado inteiro a que não é um quadrado perfeito nem −1 é um módulo da raiz primitiva com infinitos primos.

A sequência de menores raízes primitivas módulo n (que não é a mesma que a sequência de raízes primitivas na tabela de Gauss) são

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, . (sequência A046145 no OEIS)

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2, 3, 7, 6, 2, 2, . (sequência A001918 no OEIS)

As maiores raízes primitivas do módulo n são

0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0, . (sequência A046146 no OEIS)

1, 2, 3, 5, 8, 11, 14, 15, 21, 27, 24, 35, 35, 34, 45, 51, 56, 59, 63, 69, 68, 77, 80, 86, 92, 99, 101, 104, 103, 110, 118, 128, 134, 135, 147, 146, 152, 159, 165, 171, 176, 179, 189, 188, 195, 197, 207, 214, 224, 223, . (sequência A071894 no OEIS)

Número de raízes primitivas módulo n são

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, . (sequência A046144 no OEIS)

1, 1, 2, 2, 4, 4, 8, 6, 10, 12, 8, 12, 16, 12, 22, 24, 28, 16, 20, 24, 24, 24, 40, 40, 32, 40, 32, 52, 36, 48, 36, 48, 64, 44, 72, 40, 48, 54, 82, 84, 88, 48, 72, 64, 84, 60, 48, 72, 112, 72, 112, 96, 64, 100, 128, 130, 132, 72, 88, 96,. (sequência A008330 no OEIS)

Menor primo & gt n com raiz primitiva n são

2, 3, 5, 0, 7, 11, 11, 11, 0, 17, 13, 17, 19, 17, 19, 0, 23, 29, 23, 23, 23, 31, 47, 31, 0, 29, 29, 41, 41, 41, 41, 47, 37, 43, 41, 37, 0, 59, 47, 47, 47, 47, 59, 47, 47, 47, 67, 59, 53, 0, 53, . (sequência A023049 no OEIS)

Menor primo (não necessariamente excedendo n) com raiz primitiva n são

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, . (sequência A056619 no OEIS)

Fatos aritméticos Editar

Gauss provou [6] que para qualquer número primo p (com a única exceção de p = 3), o produto de suas raízes primitivas é congruente a 1 módulo p.

Ele também provou [7] que para qualquer número primo p, a soma de suas raízes primitivas é congruente com μ (p - 1) módulo p, onde μ é a função de Möbius.

Por exemplo,

p = 3, μ (2) = −1. A raiz primitiva é 2. p = 5, μ (4) = 0. As raízes primitivas são 2 e 3. p = 7, μ (6) = 1. As raízes primitivas são 3 e 5. p = 31, μ ( 30) = −1. As raízes primitivas são 3, 11, 12, 13, 17, 21, 22 e 24. Seu produto 970377408 ≡ 1 (mod 31) e sua soma 123 ≡ −1 (mod 31). 3 × 11 = 33 ≡ 2 12 × 13 = 156 ≡ 1 (−14) × (−10) = 140 ≡ 16 (−9) × (−7) = 63 ≡ 1, e 2 × 1 × 16 × 1 = 32 ≡ 1 (mod 31).

Nenhuma fórmula geral simples para calcular raízes primitivas módulo n é conhecida. [a] [b] No entanto, existem métodos para localizar uma raiz primitiva que são mais rápidos do que simplesmente tentar todos os candidatos. Se a ordem multiplicativa de um número m módulo n for igual a φ (n) (a ordem de Z < displaystyle mathbb > ×
n ), então é uma raiz primitiva. Na verdade, o inverso é verdadeiro: se m é uma raiz primitiva módulo n, então a ordem multiplicativa de m é φ (n). Podemos usar isso para testar um candidato m para ver se ele é primitivo.

usando um algoritmo rápido para exponenciação modular, como exponenciação por quadratura. Um número m para o qual esses resultados k são todos diferentes de 1 é uma raiz primitiva.

O número de raízes primitivas módulo n, se houver, é igual a [8]

Se g é uma raiz primitiva módulo p, então g também é uma raiz primitiva módulo todas as potências p k a menos que g p −1 ≡ 1 (mod p 2) nesse caso, g + p é. [10]

Se g é um módulo de raiz primitiva p k, então g ou g + p k (o que for ímpar) é um módulo de raiz primitiva 2 p k. [10]

Encontrar raízes primitivas módulo p também é equivalente a encontrar as raízes do polinômio (p - 1) st ciclotômico módulo p.

A raiz menos primitiva gp módulo p (no intervalo 1, 2,. p - 1) é geralmente pequeno.

Limites superiores Editar

Burgess (1962) provou [11] que para cada ε & gt 0 existe um C tal que g p ≤ C p 1 4 + ϵ. < displaystyle g_

leq C , p ^ << frac <1> <4>> + epsilon>

Edição de limites inferiores

Fridlander (1949) e Salié (1950) provaram [11] que existe uma constante positiva C tal que para um número infinito de primos gp & gt C log p.

Pode ser provado [11] de uma maneira elementar que para qualquer inteiro positivo M existem infinitos primos tais que M & lt gp & lt p - M.

Um módulo de raiz primitiva n é freqüentemente usado em criptografia, incluindo o esquema de troca de chaves Diffie – Hellman. Os difusores de som foram baseados em conceitos da teoria dos números, como raízes primitivas e resíduos quadráticos. [13] [14]

  1. ^ "Um dos problemas não resolvidos mais importantes na teoria dos campos finitos é projetar um algoritmo rápido para construir raízes primitivas. Von zur Gathen & amp Shparlinski 1998, pp. 15-24
  2. ^ "Não existe uma fórmula conveniente para calcular [a raiz menos primitiva]." Robbins 2006, p. 159
  1. ^ Stromquist, Walter. “O que são raízes primitivas?”. Matemática. Bryn Mawr College. Arquivado do original em 03/07/2017. Recuperado em 03/07/2017.
  2. ^
  3. Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.
  4. ^Raiz primitiva, Enciclopédia da Matemática.
  5. ^Vinogradov 2003, pp. 105-121, § VI Raízes e índices primitivos.
  6. ^Vinogradov 2003, p. 106
  7. ^Gauss e Clarke 1986, artes. Erro 80 harvnb: sem alvo: CITEREFGaussClarke1986 (ajuda).
  8. ^Gauss & amp Clarke 1986, art 81 harvnb error: no target: CITEREFGaussClarke1986 (ajuda).
  9. ^ (sequência A010554 no OEIS)
  10. ^
  11. Knuth, Donald E. (1998). Algoritmos Seminuméricos. The Art of Computer Programming. 2 (3ª ed.). Addison – Wesley. seção 4.5.4, página 391.
  12. ^ umab
  13. Cohen, Henri (1993). Um curso de teoria algébrica dos números computacionais. Berlim: Springer. p. 26. ISBN978-3-540-55640-4.
  14. ^ umabcd
  15. Ribenboim, Paulo (1996). O novo livro de registros de números primos. New York, NY: Springer. p. 24. ISBN978-0-387-94457-9.
  16. ^Bach & amp Shallit 1996, p. 254.
  17. ^
  18. Walker, R. (1990). A concepção e aplicação de elementos difusores acústicos modulares (PDF). Departamento de Pesquisa da BBC (Relatório). British Broadcasting Corporation . Página visitada em 25 de março de 2019.
  19. ^
  20. Feldman, Eliot (julho de 1995). “Uma grelha de reflexão que anula a reflexão especular: Um cone de silêncio”. J. Acoust. Soc. Sou. 98 (1): 623–634. Bibcode: 1995ASAJ. 98..623F. doi: 10.1121 / 1.413656.

Erro de citação: uma referência definida por lista chamada "Carella-2015" não é usada no conteúdo (consulte a página de ajuda).

  • Bach, Eric Shallit, Jeffrey (1996). Algoritmos Eficientes. Teoria Algorítmica dos Números. eu. Cambridge, MA: The MIT Press. ISBN978-0-262-02405-1.
  • Carella, N. A. (2015). "Least Prime Primitive Roots". Jornal Internacional de Matemática e Ciência da Computação. 10 (2): 185–194. arXiv: 1709.01172.

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.


2 respostas 2

Você provavelmente está familiarizado com o resultado que diz que se $ n $ tem uma raiz primitiva, então $ n $ tem $ varphi ( varphi (n)) $ raízes primitivas.

No caso $ q = 2p + 1 $, o número de raízes primitivas de $ q $ é, portanto, $ varphi (2p) $, que é $ p-1 $. Mas $ p-1 = frac<2> -1 $. Uma vez que existem $ frac<2> $ não-resíduos quadráticos de $ q $, e cada raiz primitiva é um não-resíduo, segue-se que todos os não-resíduos, exceto um, são uma raiz primitiva.

Como $ q $ tem a forma $ 4k + 3 $, sabemos que $ -1 $ é um não-resíduo. Mas $ -1 $ não é uma raiz primitiva de $ q $, pois $ q gt 3 $. Portanto, $ -1 $ é o único não-resíduo que não é uma raiz primitiva.


5: Raízes Primitivas e Resíduos Quadráticos

UNIVERSIDADE DE YALE
DEPARTAMENTO DE CIÊNCIA DA COMPUTADOR

CPSC 467a: criptografia e segurança de computador Notas 15 e # x00A0 (rev. & # X00A02)
Professor M. J. Fischer 29 de outubro de 2008

61 resíduos quadráticos, quadrados e raízes quadradas

Um inteiro a é chamado de resíduo quadrático (ou quadrado perfeito) módulo n se a & # x2261 b 2 (mod n) para algum inteiro b. Diz-se que tal b é a raiz quadrada de um módulo n. Nós deixamos

ser o conjunto de resíduos quadráticos em Z * n , e denotamos o conjunto de resíduos não quadráticos em Z * n por QNR n = Z * n - QR n .

62 Square Roots Módulo a Prime

Reivindicar & # x00A01 Para um p primo ímpar, todo a QR p tem exatamente duas raízes quadradas em Z * p , e exatamente 1/2 dos elementos de Z * p são resíduos quadráticos.

Por exemplo, considere p = 11. A tabela a seguir mostra todos os elementos de Z * 11 e seus quadrados.

Prova: agora comprovamos o Claim & # x00A01. Considere o mapeamento sq: Z * p & # x2192 QR p definido por b b 2 mod p. Mostramos que este é um mapeamento 2 para 1 de Z * p em QR p .

Deixe um QR p , e seja b 2 & # x2261 a (mod p) a raiz quadrada de a. Então - b também é uma raiz quadrada de a, e b & # x2044 & # x2261-b (mod p), pois p

& # x2223 2 b. Portanto, a tem pelo menos duas raízes quadradas distintas (mod n). Agora, seja c qualquer raiz quadrada de a.

Então p & # x2223 c 2 - b 2, então p & # x2223 (c - b) (c + b). Como p é primo, então p & # x2223 (c - b), caso em que c & # x2261 b (mod p), ou p & # x2223 (c + b), caso em que c & # x2261 - b (mod p). Portanto, c & # x2261 b (mod p). Como c era uma raiz quadrada arbitrária de a, segue-se que b são as únicas duas raízes quadradas de a. Portanto, sq () é uma função 2 para 1 e | QR p | = | Z * p | como desejado. __

Módulo de 63 raízes quadradas, o produto de dois primos

Reivindicação & # x00A02 Seja n = pq para p, q primos ímpares distintos. Então todo a QR n tem exatamente quatro raízes quadradas em Z * n , e exatamente 1/4 dos elementos de Z * n são resíduos quadráticos.

Prova: Considere o mapeamento sq: Z * n & # x2192 QR n definido por b b 2 mod n. Mostramos que este é um mapeamento 4 para 1 de Z * n em QR n .

Deixe um QR n e seja b 2 & # x2261 a (mod n) a raiz quadrada de a. Então também b 2 & # x2261 a (mod p) eb 2 & # x2261 a (mod q), então b é a raiz quadrada de a (mod p) e b é a raiz quadrada de a (mod q). Por outro lado, se b p é uma raiz quadrada de a (mod p) e b q é uma raiz quadrada de a (mod q), então pelo teorema do restante chinês, o número único b Z * n de modo que b & # x2261 b p (mod p) e b & # x2261 b q (mod q) é uma raiz quadrada de a (mod n). Como a tem duas raízes quadradas mod p e duas raízes quadradas mod q, segue-se que a tem quatro raízes quadradas mod n. Portanto, sq () é uma função 4 para 1 e | QR n | = | Z * n | como desejado. __

Critério de Euler 64

Há um teste simples devido a Euler para saber se um número está em QR p para p linha.

Reivindicação & # x00A03 (Critério de Euler): Um número inteiro a é um resíduo quadrático não trivial de 1 módulo p iff

Prova: Seja a & # x2261 b 2 (mod p) para algum b & # x2044 & # x2261 0 (mod p). Então

pelo teorema de Euler & # 8217s, conforme desejado.

Para a outra direção, suponha a (p - 1) & # x2215 2 & # x2261 1 (mod p). Claramente um & # x2044 & # x2261 0 (mod p). Mostramos que a é um resíduo quadrático encontrando uma raiz quadrada b módulo p.

Seja g uma raiz primitiva de p. Escolha k para que a & # x2261 g k (mod p) e deixe & # x2113 = (p - 1) k & # x2215 2. Então

Como g é uma raiz primitiva, g & # x2113 & # x2261 1 (mod p) implica que & # x2113 é um múltiplo de p - 1. Portanto, (p - 1) & # x2223 (p - 1) k & # x2215 2, a partir do qual concluímos que 2 | k e k & # x2215 2 é um número inteiro. Seja b = g k & # x2215 2. Então, b 2 & # x2261 g k & # x2261 a (mod p), então b é a raiz quadrada de um módulo p, conforme desejado. __

65 Encontrando Raízes Quadradas Módulo Primes Especiais

O critério de Euler nos permite testar a associação em QR p para o primo p, mas não nos diz como encontrar raízes quadradas. No caso de p & # x2261 3 (mod 4), há um algoritmo fácil para encontrar as raízes quadradas de qualquer membro de QR p .

Reivindicar & # x00A04 Let p & # x2261 3 (mod 4), a QR p . Então b = a (p +1) & # x2215 4 é uma raiz quadrada de a (mod p).

Prova: de acordo com as premissas da afirmação, p + 1 é divisível por 4, portanto (p + 1) & # x2215 4 é um número inteiro. Então

pelo Critério de Euler (Reivindicação & # x00A03). __

Algoritmo de 66 Shank & # 8217s para Encontrar Raízes Quadradas Módulo Primos Ímpares

Seja p um primo ímpar. Sejam s e t inteiros únicos, de modo que p - 1 = 2 s t e t seja ímpar. (Observe que s é simplesmente o número de 0 & # 8217s à direita na expansão binária de p - 1 e t é o que resta quando p - 1 é deslocado para a direita em s casas.) Como p é ímpar, p - 1 é par, então s & # x2265 1.

No caso especial em que s = 1, p - 1 = 2 t, então p = 2 t + 1. Escrevendo o número ímpar t como 2 & # x2113 + 1 para algum número inteiro & # x2113, temos p = 2 (2 & # x2113 + 1) + 1 = 4 & # x2113 + 3, então p & # x2261 3 (mod 4). Mas este é exatamente o especial que consideramos na Seção & # x00A065.

Apresentamos agora um algoritmo que trabalha para encontrar raízes quadradas de resíduos quadráticos módulo qualquer primo ímpar p. O algoritmo & # x00A066.1, devido a D. & # X00A0Shanks 2, tem uma forte semelhança com o algoritmo & # x00A056.1 para fatorar o módulo RSA dados os expoentes de criptografia e descriptografia.

Seja p, s, t como acima. Assuma um /> QR p é um resíduo quadrático e u /> QNR p é um não-resíduo quadrático. (Podemos encontrar facilmente u escolhendo elementos aleatórios de Z * p e aplicando o Critério de Euler.) O objetivo é encontrar x tal que x 2 & # x2261 a (mod p).

Entrada: Odd primo p, resíduo quadrático a QR p .

Saída: A raiz quadrada de a (mod p).

1. Deixe s, t satisfazer p = 2 s t e t ímpar.

2. Deixa você QNR p .

8. seja m o menor número inteiro com b 2 m & # x2261 1 (mod p)


Figura & # x00A066.1: Algoritmo de Shank & # 8217s para encontrar a raiz quadrada de a (mod n).

A congruência x 2 & # x2261 ab (mod p) é facilmente mostrada como uma invariante de loop. É claramente verdadeiro inicialmente, uma vez que x 2 & # x2261 a t +1 eb & # x2261 a t (mod p). Cada vez no loop, a permanece inalterado, b é multiplicado por t 2 (linhas & # x00A010 e & # x00A011) e x é multiplicado por t (linha & # x00A012), portanto, o invariante permanece verdadeiro independentemente do valor de t. Se o programa terminar, temos b & # x2261 1 (mod p), então x 2 & # x2261 a, e x é a raiz quadrada de a (mod p).

Para ver por que ele termina após no máximo s iterações do loop, olhamos para as ordens 3 de bez (mod p) no início de cada iteração do loop (antes da linha & # x00A08) e mostramos que ord (b) & # x003C ord (z) = 2 k.

Na primeira iteração, k = s ez & # x2261 u t (mod p). Argumentamos que ord (z) = 2 s. Claramente

então ord (z) & # x2223 2 s. Pelo Critério de Euler, uma vez que u é um não-resíduo, temos

Portanto, ord (z) = 2 s. Usando um raciocínio semelhante, uma vez que a é um resíduo quadrático, b 2 s - 1 & # x2261 1 (mod p), então ord (b) & # x2223 2 s - 1. Segue-se que ord (b) & # x003C ord (z) = 2 s = 2 k.

Agora, em cada iteração, a linha & # x00A08 define m = ord (b) e a linha & # x00A09 define t = z 2 k - m - 1 mod p, então

A linha & # x00A010 define z = t 2, então ord (z) = ord (t) & # x2215 2 = 2 m. Após a linha & # x00A011, ord (b) & # x003C 2 m. Isso porque o valor antigo de b e o novo valor de z têm ordem 2 m. Portanto, ambos os números elevados à potência 2 m - 1 são - 1 (mod p), então seu produto (o novo valor de b) elevado à mesma potência é (- 1) 2 & # x2261 1. A linha & # x00A013 define k = m em preparação para a próxima iteração, e o invariante de loop ord (b) & # x003C ord (z) = 2 k é mantido. Além disso, ord (b) é reduzido a cada iteração, de modo que o loop deve terminar após no máximo s iterações.

67 QR Probabilistic Cryptosystem

Seja n = pq, p, q primos ímpares distintos. Podemos dividir os números em Z * n em quatro classes, dependendo de sua adesão ao QR p e QR q . 4 Let Q n 11 sejam aqueles números que são resíduos quadráticos mod tanto p quanto q sejam Q n 10 sejam aqueles números que são resíduos quadráticos mod p, mas não mod q seja Q n 01 sejam aqueles números que são resíduos quadráticos mod q, mas não mod p e sejam Q n 00 são aqueles números que não são resíduos quadráticos mod p nem mod q. Sob essas definições, Q n 11 = QR n e Q n 00 e # x222A Q n 01 e # x222A Q n 10 = QNR n . Fato dado a /> Q n 00 e # x222A Q n 11, não há algoritmo conhecido viável para determinar se um /> QR n isso dá a resposta correta significativamente mais da metade das vezes.

O criptosistema Goldwasser-Micali é baseado neste fato. A chave pública consiste em um par e = (n, y), onde n = pq para números primos ímpares distintos p, q e y Q n 00 A chave privada consiste em p. O espaço da mensagem é = < 0 , 1 >.

Para criptografar m , Alice escolhe um aleatório QR n . Ela faz isso escolhendo um membro aleatório de Z * n e quadrando-o. Se m = 0, então c = a mod n. Se m = 1, então c = ay mod n. O texto cifrado é c.

É facilmente mostrado que se m = 0, então c Q n 11, e se m = 1, então c Q n 00 Também se pode mostrar que cada elemento de Q n 11 é igualmente provável de ser escolhido como o texto cifrado c no caso m = 0, e cada elemento de Q n 00 é igualmente provável de ser escolhido como o texto cifrado c no caso m = 1. O problema de Eve para determinar se c criptografa 0 ou 1 é o mesmo que o problema de distinguir entre membros em Q n 00 e Q n 11, que pelo fato acima se acredita ser difícil. Qualquer pessoa que conheça a chave privada p, no entanto, pode usar o Critério de Euler para determinar rapidamente se c é ou não um resíduo quadrático mod p e, portanto, se c Q n 11 ou c Q n 00, determinando assim m.


Subseção 10.5.1 Encontrando uma raiz superior

Aqui está uma maneira de resolver o primeiro. Primeiro encontramos um módulo raiz primitivo (19 ). Obviamente, poderíamos apenas perguntar a Sage, ou usar o critério da última vez com tentativa e erro em um passado não muito distante, o verso de cada texto de teoria dos números tinha uma tabela de raízes primitivas!

Agora o que vamos fazer é tentar representar Ambas lados de [x ^ 4 equiv 13 text (19) ] como potências daquela raiz primitiva!

A parte fácil é representar (x ^ 4 ) nós apenas dizemos que (x equiv 2 ^ i ) para alguns (ainda desconhecido) (i ), então [x ^ 4 equiv left ( 2 ^ i right) ^ 4 equiv 2 ^ <4i> . ] A parte mais difícil é descobrir que potência de (2 ) dá (13 ). Novamente, não há atalho, embora os livros no passado tivessem tabelas enormes dessas coisas.

Assim, apenas substituindo as raízes primitivas em (x ^ 4 ) e (13 ), podemos dizer que [x ^ 4 equiv 13 text (19) ] torna-se [2 ^ <4i> equiv 2 ^ <5> text (19) . ]

Como teríamos resolvido isso no pré-cálculo? Você resolveria desta forma, com equações (não congruências): [2 ^ <4i> = 2 ^ <5> Rightarrow 4i = 5 Rightarrow i = 5/4 . ] Tentaremos fazer algo muito semelhante aqui.

O que é muito importante é que esta congruência é, em certo sentido, realmente não é mais uma congruência em ( mathbb_ <19> ). Para ser mais preciso, tudo à vista está realmente em (U_ <19> ), um grupo cíclico de ordem ( phi (19) = 18 ). Mas um grupo cíclico de ordem (18 ) seria o mesmo que pensar o módulo dezoito! Portanto, podemos retirar os expoentes, assim como no pré-cálculo, mas fazer as coisas mod ( (18 )): [4i equiv 5 text (18) . ]

Infelizmente, isso não tem solução. Mas descobrimos isso sem tirar cada quarta potência que existe! Na verdade, fazer isso confirma nosso resultado:

Vamos tentar o mesmo módulo de congruência (17 ) - isto é, podemos resolver [x ^ 4 equiv 13 text (17) ? ] Aqui, uma raiz primitiva é (3 ) , e descobrimos que (3 ^ 4 equiv 13 ), então podemos tentar. Isso dá [3 ^ <4i> equiv 3 ^ 4 text (17) Rightarrow 4i equiv 4 text (16) ,, ] que definitivamente tem soluções - na verdade, existem quatro soluções ( (1,5,9,13 )) para a congruência reduzida [i equiv 1 text (4) ], portanto, existem quatro soluções ( (3 ^ 1,3 ^ 5,3 ^ 9,3 ^ <13> )) à congruência original. Vamos verificar isso:

Você pode até vê-lo funcionando para coisas mais complicadas. Se tentarmos resolver (x ^ 6 equiv 8 ) mod (49), precisaremos de uma raiz primitiva de 49 3 trabalhos. Posso descobrir qual potência (3 ^ i ) de (3 ) produz (8 ):

Então escrevemos (x = 3 ^ i ) para alguns ainda desconhecidos (i ) e obtemos [3 ^ <6i> equiv 3 ^ <36> text (49) , ] que nos dá [6i equiv 36 text ( phi (49) = 42) ] e isso se reduz a [i equiv 6 text (7) . ] Então (i = 6,13,20,27,34,41 ) todos funcionam, o que significa (de nossa pequena informação acima) que (x = 3 ^ equiv 43,10,16,6,39,33 ) tudo deve funcionar.


Teoria dos Números: em contexto e interativa

O que fez a teoria dos resíduos quadráticos / raízes quadradas funcionar melhor no final foram algumas inovações importantes do matemático francês Adrien-Marie Legendre Gauss, em particular, que fizeram grande uso delas.

Observação histórica 16.4.1. Adrien-Marie Legendre.

Legendre foi o sucessor de Lagrange em Paris. Como muitos matemáticos do século XVIII, Legendre trabalhou em muitas áreas, incluindo teoria das funções e física matemática. Notavelmente, como o aumento da profissionalização dos estudos de matemática superior surgiu nos estudos de engenharia franceses pós-revolucionários (uma historiadora do desenvolvimento da matemática que Judith Grabiner argumenta que levou à rigorização do cálculo), ele escreveu um livro didático de geometria amplamente utilizado.

Embora abordar o tema historicamente possa ser benéfico, uma vez que temos a vantagem de ter desenvolvido o básico de grupos e raízes primitivas, poderemos simplificar muito a exposição de resíduos quadráticos (um tanto anacronicamente) usando esses conceitos.

Subseção 16.4.1 Resíduos quadráticos formam um grupo

Definição 16.4.2.

Considere o conjunto de todos os resíduos quadráticos diferentes de zero módulo algum primo (p text <.> ) Chamamos isso de (Q_p text <.> )

Essa terminologia sugere que tenho uma prova em meu bolso para o seguinte teorema.

Teorema 16.4.3.

O conjunto de resíduos quadráticos diferentes de zero (Q_p ) módulo a primo (p ) é realmente um grupo, e é mesmo um subgrupo do grupo de unidades (U_p text <.> )

Prova .

Prosseguiremos mostrando os axiomas de grupo válidos na multiplicação. Visto que excluímos zero e (p ) é primo, (Q_p ) é um subconjunto de (U_p ) essencialmente por definição, o que implicará que também é um subgrupo de (U_p ).

Vejamos os três axiomas principais.

É claro que (1 in Q_p text <,> ) desde (1 equiv 1 ^ 2 text <.> ) Portanto, há uma identidade.

Em seguida, se (a ) e (b ) estiverem em (Q_p ) (com (a equiv s ^ 2 ) e (b equiv t ^ 2 )), então ( ab ) também é um resíduo quadrático (uma vez que ((st) ^ 2 equiv s ^ 2 t ^ 2 equiv ab )).

Resta verificar se este conjunto tem inversos sob multiplicação.

Para mostrar este último ponto, suponha que (a equiv s ^ 2 in Q_p text <,> ) e considere (s ^ <-1> ) como um elemento de (U_p text <.> ) Então

Então por definição de inversos

o que significa que se (a em Q_p ) então (a ^ <-1> em Q_p ) também.

Observação 16.4.4.

Para aqueles com algum background algébrico adicional, parece que (Q_p ) é na verdade um de (U_p ) também, mas não vamos nos aprofundar mais nisso aqui.

Subseção 16.4.2 Resíduos quadráticos conectam-se a raízes primitivas

Você pode estar se perguntando como esta parte de (U_p ) se conecta à coisa mais importante que vimos até agora sobre (U_p text <.> ) Lembre-se de que (U_p ) era cíclico, que tinha um gerador cujos poderes nos deram todos os módulos de unidades (p text <.> ) Chamamos tal elemento de de (p ) (lembre-se do Capítulo 10).

Portanto, vamos comparar os poderes da raiz primitiva e os resíduos quadráticos. Não deve ser muito difícil ... se você não está computando isso com o Sage, experimente manualmente com um módulo ainda menor, como sete ou onze.

Observe o padrão de quais elementos de (U_ <19> ) (como potências da raiz primitiva) são resíduos quadráticos! Isso exemplifica um fato importante.

Fato 16.4.5.

Para módulo primo ímpar (p text <,> ) os resíduos quadráticos são precisamente os até poderes de uma raiz primitiva (g text <.> )

Prova .

Certainly (g^<2n>=left(g^n ight)^2 ext<,>) so the even powers of (g) are QRs.

Now we need the other set inclusion. Suppose that (ain Q_p) and (a=s^2 ext<.>) Then first note that (s) and (a) are themselves still powers of (g) (by definition of (g)). So let (s=g^n) and (a=g^m) for some (n,m ext<.>) Then we have the implication

This is only possible if (m) is even since (p-1) and (2n) are even.

Example 16.4.6 .

This is a very strong statement, because it does not depend upon the primitive root! For example, if (p=11 ext<,>) one can verify both (2) and (8) are primitive roots modulo eleven then they are clearly nonresidues, and moreover are odd powers of each other:

This fact will turn out to be a fantastically useful theoretical way to find (Q_p ext<.>) It will show up in lots of proofy settings. Here is a first example, a very nice result about when a composite number is a QR.

Proposition 16.4.7 .

If (n=ab) is a factorization (not necessarily nontrivial) of (n ext<,>) then (n) is a QR of (p) precisely when either both (a) and (b) are QRs of (p) or both (a) and (b) are não QRs of (p ext<.>)

Proof .

Modulo (p ext<,>) write (aequiv g^i) and (bequiv g^j) for some (i,j ext<.>) Then (n=abequiv g^ ext<,>) and (i+j) is even when (i) and (j) have the same parity. Because of Fact 16.4.5, this is exactly the same thing as the conclusion of the proposition.

Hence if one of (a,b) is a QR and the other one isn't, neither is (n=ab ext<.>)

Example 16.4.8 .

Let's assume that we have the pattern observed in Question 16.3.4 and try to decide whether (21) is a QR (mod (23)).

Our first step is to try to make (21) a product of two numbers we already know something about. Since (21equiv -2) (mod (23)), we can look at (-1) and (2) separately. Then recall that (-1) is not a QR (since (23equiv 3) (mod (4))) but (2) is, from our explorations. So we would conjecture (21) is not a QR either.

We can use the same trick for other numbers congruent to (-2) modulo (p ext<.>) For instance, I can immediately decide that (-2equiv 9) is a QR (mod (11)) by the fact that neither (-1) nor (2) is a QR modulo (11 ext<.>)

We will soon revisit this idea in Proposition 17.1.1.

There is yet another way to view the tension between primitive roots and quadratic residues. Before moving on to the next interactive graphic, try to answer the following question.

Question 16.4.9 .

Do you see why a quadratic residue automatically can't be a primitive root? (This follows from results earlier in this chapter see Exercise 16.8.10.)

Now try our familiar graphic again, this time concentrating on which rows correspond to primitive roots and which ones to quadratic residues.

The second column (labeled 1) contains all the residues, and by definition the quadratic residues are the colors located in the third column (labeled 2 as they are squares). See how that column is symmetric about the middle of the rows, with two of each of the QR colors appearing. Further, these are the same colors as the ones appearing in every other column in rows with a primitive root (the rows with every color represented) naturally, the order may be quite different. Finally, the second column's color in each row that has every color (including black) nunca shows up in the third column (the one for squares) this corresponds to the fact that a primitive root can't be a quadratic residue.

Try it out interactively until the connection between the known facts and the graphical pattern seems plausible.

These observations may not seem as interesting, but they will pay off in the next section we will obtain a crucial criterion for computing quadratic residues by observing a similar pattern!


Example 2

Does the quadratic congruence $x^2 equiv 341 pmod <17>$ have solutions?

We can determine if this quadratic congruence has solutions by evaluating the Legendre symbol $(341/17)$ . By (A), we know this Legendre symbol is defined since 17 is an odd prime and $17 mid 341$ . For evaluating this Legendre symbol, we are going to first use (B) to reduce 341. Note that we could have used this in example 1 too! $341 equiv 1 pmod <17>$ . Hence it follows that:

And since 1 is a square, then $left ( frac<1> <7> ight ) = 1$ . Hence it follows that the Legendre symbol $(341/17) = 1$ . So the quadratic congruence $x^2 equiv 341 pmod <17>$ has solutions. In fact, we can find them rather easily:

So x is 1 (mod 17) or -1 (mod 17). -1 is not in least residue, so instead our other solution is 16 (mod 17). Hence our solutions are x = 1 and x = 16.


2 Bound for large ω ( p − 1 )

For brevity, we merely state some necessary results from [4] . For k a positive integer, let

The last displayed equation in [4, p. 5] implies the following criterion, the satisfaction of which guarantees the existence of two consecutive QNRNPs modulo p :

As in [4] we bound the sums in ( 2 ) by noting that for ω ( p − 1 ) ≥ 2 we have ∑ 2 k ν = 1 ( ω ( p − 1 ) ν ) ≤ ω ( p − 1 ) 2 k . We now seek to bound θ k ( p ) . We have 3 3 3 We have corrected a slight misprint in [4] : their sum is over ν ≥ 2 k instead of ν ≥ 2 k + 1 .

θ k ( p ) = − 1 / 2 + ∑ ν ≥ 2 k + 1 ∑ d | p − 1 ω ( d ) = ν μ ( d ) d − ∑ d | p − 1 d > 1 μ ( d ) d = 1 2 − ϕ ( p − 1 ) p − 1 + ∑ ν ≥ 2 k + 1 ∑ d | p − 1 ω ( d ) = ν μ ( d ) d . (3)
∣ ∣ ∣ ∑ ν ≥ 2 k + 1 ∑ d | p − 1 ω ( d ) = ν μ ( d ) d ∣ ∣ ∣ ≤ ∑ ν ≥ 2 k + 1 ∑ d | p − 1 ω ( d ) = ν d squarefree 1 d ≤ ∑ ν ≥ 2 k + 1 1 ν ! P ν , (4)

since for ω ( p − 1 ) = n we have that p ≥ 2 ⋅ 3 ⋅ 5 ⋯ q ω ( p − 1 ) + 1 . To estimate ( 5 ) we use the following results

ω ( n ) ≤ 1.385 log n log log n ( n ≥ 3 ) , ∑ p ≤ x 1 p ≤ log log x + 0.262 + 1 log 2 x ( x ≥ 2 ) , p n ≤ n ( log n + log log n ) ( n ≥ 6 ) , (6)

which are respectively [6, Thm 10] and [7, (3.20) and (3.13)] . We also use the inequality ν ! ≥ ( ν / e ) ν , which is valid for all ν ≥ 1 . Although sharper versions of these inequalities are available, the present ones are sufficient for our purposes. For any k ≥ e P we have

Therefore taking k = max < [ e P ] + 1 , log ( 2 / ϵ ) / ( 2 log 2 ) >we ensure that the sum in ( 7 ) is at most ϵ / 2 . This shows, from ( 3 ), and from the assumption that ϕ ( p − 1 ) / ( p − 1 ) ≤ 1 2 − ϵ that ϵ 2 ≤ θ k ( p ) ≤ 1 . Therefore, our criterion in ( 2 ) becomes

We now insert our bounds for ( 6 ). These bound ω ( p − 1 ) , P , and hence k . For ϵ = 1 / 4 , a quick computer check verifies Theorem 1 for all p with ω ( p − 1 ) ≥ 48 . Before considering these cases in the next section, we briefly dispense with the case ω ( p − 1 ) = 1 .

When ω ( p − 1 ) = 1 the bound for θ k ( p ) in ( 3 ) reduces to θ k ( p ) = 1 2 − ϕ ( p − 1 ) / ( p − 1 ) ≥ ϵ . Taking ϵ = 1 4 and inserting this into ( 2 ) proves the existence of two consecutive QNRNPs provided that p > 1600 . It is easy to check that there are no p < 1600 satisfying both ϕ ( p − 1 ) ≤ ( p − 1 ) / 4 and ω ( p − 1 ) = 1 .


Quadratic Residues

Let (a in mathbb_n). We say (a) is a quadratic residue if there exists some (x) such that (x^2 = a). Otherwise (a) is a quadratic nonresidue.

Efficiently distinguishing a quadratic residue from a nonresidue modulo (N = p q) for primes (p, q) is an open problem. This is exploited by several cryptosystems, such as Goldwassser-Micali encryption, or Cocks identity-based encryption. More general variants of this problem underlie other cryptosystems such as Paillier encryption.

Let (p) be an odd prime, as the case (p = 2) is trivial. Let (g) be a generator of (mathbb_p^*). Any (a in mathbb_p^*) can be written as (g^k) for some (k in [0..p-2]).

Say (k) is even. Write (k = 2m). Then ((g^m)^2 = a), so (a) is a quadratic residue. Exactly half of ([0..p-2]) is even (since (p) is odd), hence at least half of the elements of (mathbb_p^*) are quadratic residues.

Suppose we have (b^2 = a). Then ((-b)^2 = a) as well, and since (b e -b) (since (p > 2)) every quadratic residue has at least two square roots (in fact, we know from studying polynomials there can be at most two), thus at most half the elements of (mathbb_p^*) are quadratic residues. (Otherwise there are more square roots than elements!)

Thus exactly half of (mathbb_p^*) are quadratic residues, and they are the even powers of (g).

Given (a = g^k), consider the effect of exponentiating by ((p-1)/2). If (k) is odd, say (k = 2m + 1), we get

The square of (g^<(p-1)/2>) is (g^ = 1), so (g^<(p-1)/2>) is (1) or (-1). But (g) has order (p-1) ((g) is a generator) thus we must have (g^ <(p-1)/2>= -1).

If (k) is even, say (k = 2m), then (a^ <(p-1)/2>= g^ <(p-1)m>= 1).

In other words, we have proved Euler’s Criterion, which states (a) is a quadratic residue if and only if (a^ <(p-1)/2>= 1), and (a) is a quadratic nonresidue if and only if (a^ <(p-1)/2>= -1).

Exemplo: We have (-1) is a quadratic residue in (mathbb_p) if and only if (p = 1 pmod <4>).


Assista o vídeo: Raiz primitiva mod p (Novembro 2021).