Números Inteiros e Criptografia RSA

EX. Máximo divisor comum e probabilidade de coprimalidade

Escreva um programa que, tendo como entrada dois inteiros a e b, determine o máximo divisor comum mdc(a, b).

Em seguida, adapte o seu programa para gerar aleatoriamente pares de inteiros a e b e calcular mdc(a, b) de cada par. O programa deve ter como entrada o número total de pares que se deseja testar e, como saída, o quociente

Esse quociente fornece uma medida da probabilidade de que um par de inteiros escolhido aleatoriamente seja coprimo. Será necessário deixar o programa testar um número muito grande de pares para obter uma boa aproximação dessa probabilidade.

Execute o programa dez vezes para cada valor escolhido como entrada. Construa uma tabela com esses valores, usando como entradas, pelo menos, 10, 100, 1 000, 10 000 e 100 000.

EX. 11 Números altamente compostos

Seja n um inteiro positivo e d(n) o número de divisores positivos de n. Dizemos que n é altamente composto se d(m) < d(n) para todo m < n.

Escreva um programa que, tendo como entrada um número inteiro r, determine todos os números altamente compostos menores que r. Use o programa para fazer uma lista dos números altamente compostos menores que 5 000.

Observe as fatorações dos números altamente compostos da sua lista: que propriedades desses números você deduz da observação dessa lista?

EX. 12 Fatoração pelo algoritmo de Fermat

Escreva um programa que implemente o algoritmo de Fermat para achar dois fatores de um número inteiro positivo que seja menor que 2³².

Este exercício é o primeiro de uma sequência que termina com o exercício 8 do capítulo 11.

EX. 12* Primos da forma 4n+1 versus 4n+3

Já vimos que um primo ímpar ou é da forma 4n + 1 ou da forma 4n + 3. Além disso, sabemos pelo exercício 7 que há infinitos primos da forma 4n + 3. Também é verdade que há uma infinidade de primos da forma 4n + 1, mas a demonstração é mais difícil; veja [Hardy e Wright 1994, Cap. II, seção 2.3].

O objetivo deste exercício é estudar experimentalmente a frequência relativa de cada um desses dois tipos de primos. Seja x um número real positivo. Denotaremos por π₁(x) o número de primos positivos da forma 4n + 1 que são menores ou iguais a x, e por π₃(x) o número correspondente de primos da forma 4n + 3.

Escreva um programa, baseado no Crivo de Eratóstenes, que, tendo como entrada um inteiro positivo x, determine π₁(x) e π₃(x). Tabele π₁(x), π₃(x) e π₁(x)/π₃(x) para os valores de x de 100 em 100, entre 0 e 10⁵.

Sabe-se que lim_x→∞ π₁(x)/π₃(x) = 1. Os valores da sua tabela condizem com esse resultado?

EX. 13 O menor x para o qual π₁(x) > π₃(x)

Adapte o programa elaborado no exercício anterior para determinar o menor valor inteiro de x para o qual π₁(x) > π₃(x).

EX. Potenciação modular

Escreva um programa que implemente o algoritmo para calcular a^k módulo n descrito na seção 2 do apêndice. O algoritmo deverá ter como entrada a, k e n, onde a é um inteiro qualquer e k e n são inteiros positivos. A saída deverá ser a forma reduzida de a^k módulo n.

EX. 14 Inverso em Z_p

Seja p um número primo e a um inteiro que não é divisível por p. Mostre que o inverso de ā em Z_p é ā^p−2.

EX. 16 Inverso modular e a equação ax ≡ b (mod p)

Use o exercício 14 para escrever um programa que, tendo como entrada a e p, calcule o inverso de a módulo p. Por segurança, faça o seu programa verificar primeiro que p realmente não divide a.

Use isso para escrever um outro programa que determine a solução de ax ≡ b (mod p), dadas as entradas a, b e p.

EX. 17 Raízes quadradas módulo p = 4k + 3

Seja p = 4k + 3 um primo positivo. Escreva um programa que, tendo por entrada p e um inteiro positivo a, calcule as duas soluções de x² ≡ a (mod p).

Observe que sabemos, do exercício 15, que se essa equação tem solução b, então b ≡ a^k+1 (mod p). Assim, o programa deve calcular a forma reduzida de a^k+1 módulo p e, em seguida, verificar se, de fato, esta é uma solução da equação dada. A saída será constituída pelas soluções da equação, ou por uma mensagem indicando que a equação dada não tem solução.

Este exercício é o segundo de uma sequência que termina com o exercício 8 do capítulo 11.

EX. 18 Primos que satisfazem a^p−1 ≡ 1 (mod p²)

Vários problemas da teoria de números (como o último teorema de Fermat) requerem primos p que satisfaçam a congruência

a^p−1 ≡ 1 (mod p²)

para algum inteiro a. Escreva um programa que, tendo por entrada dois inteiros positivos a > 1 e r, determine os primos p que satisfazem a congruência acima e tais que a + 1 < p < r. Observe que o programa terá que aplicar o crivo de Eratóstenes para achar os primos menores ou iguais a r; esses primos serão então testados na congruência acima.

EX. 8 Pseudoprimos para as bases 2 e 3

Escreva um programa que, tendo como entrada um inteiro positivo r, determine todos os números entre 1 e r que são pseudoprimos para as bases 2 e 3. Lembre-se de que um tal pseudoprimo n é um número ímpar e composto que satisfaz as equações

2ⁿ⁻¹ ≡ 1 (mod n) e 3ⁿ⁻¹ ≡ 1 (mod n).

Portanto, o programa só precisa testar os números ímpares e, além dessas congruências, tem que verificar se os números obtidos são primos ou não. Uma maneira de fazer isso é programar o Crivo de Eratóstenes de modo a conservar a lista dos ímpares compostos, em vez dos primos, e depois testar as congruências.

Aplique o programa com r = 10⁵. Quantos e quais foram os pseudoprimos obtidos? Quantos destes são números de Carmichael?

EX. 9 Números de Carmichael com d fatores primos

O objetivo deste exercício é a elaboração de um programa para determinar todos os números de Carmichael que são produtos de d primos, todos menores que 10³.

O principal problema é que, mesmo para valores relativamente pequenos de d, alguns dos números de Carmichael obtidos podem ser bem grandes. Isso torna difícil verificar que p − 1 divide n − 1 quando p é um fator primo de n. Mas é fácil contornar esse problema usando congruências.

Digamos que o programa gerou o número n = p₁p₂ ⋯ p_d. Precisamos saber se n − 1 é ou não divisível por p₁ − 1, por exemplo. Para isso basta calcular a forma reduzida de n módulo p₁ − 1. Como n aparece fatorado, você pode multiplicar os fatores um de cada vez e ir reduzindo módulo p₁ − 1 a cada produto, de modo a manter o resultado pequeno. Como os fatores são menores que 10³, isso vai ser muito rápido de executar.

Aplique o seu programa para d = 1, …, 8. Quais os números de Carmichael obtidos em cada caso? Não é necessário multiplicar os fatores para obter o número; basta que o programa liste os fatores.

EX. 10 Menor pseudoprimo forte para uma dada base

Escreva um programa para determinar o menor pseudoprimo forte para uma dada base. Será necessário implementar o teste de Miller, de modo que a entrada seja um inteiro positivo b > 1. O programa deve aplicar o teste de Miller na base b aos ímpares compostos, até achar o primeiro número para o qual o teste é inconclusivo. Uma maneira de fazer isso é programar o Crivo de Eratóstenes de maneira a conservar a lista dos ímpares compostos, em vez dos primos, e depois testar as congruências.

Aplique o teste para as bases 2, 3, 5 e 7. Quais os resultados obtidos?

EX. 11 Pseudoprimos da forma p² para a base 2

O objetivo deste exercício é a elaboração de um programa para determinar pseudoprimos para a base 2 da forma p², onde p é um primo. O programa deve ter como entrada um número inteiro positivo r. Em seguida, será usado o crivo de Eratóstenes para encontrar os primos p ≤ r. Finalmente, o programa vai testar quais os valores de p para os quais p² é um pseudoprimo para a base 2.

EX. 10 Solução de x² ≡ a (mod pq)

Sejam p e q primos distintos e n = pq. Suponhamos que ambos os primos deixam resto 3 na divisão por 4. Escreva um programa que, tendo como entrada p, q e a, calcule uma solução de x² ≡ a (mod n).

Combinar as soluções módulo p e módulo q para obter uma solução módulo n requer o Teorema Chinês dos Restos. A restrição imposta aos primos facilita a solução das equações x² ≡ a (mod p) e x² ≡ a (mod q); veja o exercício 17 do capítulo 5.

Este exercício é o terceiro de uma sequência que termina com o exercício 8 do capítulo 11.

EX. 20 Pseudoprimos p² — versão melhorada

Escreva um programa, baseado no exercício 18, para determinar os pseudoprimos para a base 2 da forma p², onde p é um primo menor ou igual a r > 0. Isso nos dá uma versão melhorada do programa proposto no exercício 11 do capítulo 6.

EX. 21 Cálculo de φ(k) e a equação φ(k) = φ(k+1)

Escreva um programa que, tendo por entrada um inteiro k > 0, determine φ(k). O programa vai consistir, essencialmente, de um algoritmo para fatorar k completamente.

Adapte o programa de modo que encontre todos os valores de k menores que 10⁵ tais que φ(k) = φ(k + 1).

EX. 22 Totientes

Dizemos que um inteiro k > 0 é um totiente se a equação φ(n) = k admite alguma solução. Escreva um programa que implemente o algoritmo descrito no exercício 7. Quais os números menores que 10⁵ que você consegue verificar que são totientes usando esse algoritmo?

EX. 9 Fatores de números de Mersenne pelo método de Fermat

Programe o método de Fermat para achar fatores de um número de Mersenne. O programa deve ter como entrada um primo p > 0 e, como saída, o menor fator primo de M(p) = 2^p − 1, ou uma mensagem indicando que M(p) é primo.

O programa vai consistir, basicamente, de uma implementação do algoritmo apresentado na seção 2 do apêndice para calcular 2ⁿ módulo q, onde q é da forma q = r · 2p + 1, com 0 < r ≤ (2^p/2 − 1)/2p. Se a forma reduzida de 2^p módulo q for 1, então q é fator de M(p); se nenhum tal q for encontrado, então M(p) é primo.

Observe que não vale a pena testar se q é primo antes de verificar se é fator de M(p), porque isso só tornaria o programa mais lento.

Use este programa para determinar quais os primos p, entre 2 e 257, para os quais M(p) é primo; cf. Cap. 3, seção 2.

EX. 10 Fatores de números de Fermat

Programe o algoritmo apresentado na seção 3. O algoritmo deve ter como entrada o primo p e deve procurar o valor de m (se existir) para o qual p divide F(m). Observe que, escrevendo p na forma p = k · 2ⁿ + 1, temos que m < n, o que nos dá um limite além do qual não adianta continuar a busca.

Use este programa para achar o número de Fermat que é divisível por 37 · 2¹⁶ + 1 e o que é divisível por 11 131 · 2¹² + 1.

Observe que não seria possível determinar esses fatores usando um PC se precisássemos determinar todos os algarismos dos números de Fermat correspondentes.

EX. 10 Teste de Pepin

Programe o teste de Pepin. A entrada deve ser o expoente n ≥ 0; a saída deve ser uma mensagem indicando se F(n) é primo ou composto. Observe que o programa vai consistir, essencialmente, de uma implementação do algoritmo para o cálculo de potências apresentado na seção 2 do apêndice.

Qual o maior número de Fermat que você consegue testar com o seu programa?

EX. 11 Teste de primalidade via (n−1)! módulo n

Escreva um programa que implemente o teste de primalidade descrito no exercício 6. O programa vai consistir, essencialmente, de um algoritmo para calcular a forma reduzida de (n − 1)! módulo n.

Se você tentar calcular (n − 1)! e só depois reduzi-lo módulo n, o programa vai ficar limitado a valores muito pequenos de n. Para evitar isso, efetue as reduções módulo n à medida que for multiplicando os números entre 2 e n − 1.

Aplique o programa ao maior primo menor que 10^k, quando k = 1, …, 6. Quanto tempo o programa leva para verificar que cada um desses números é primo? Tente descobrir uma regra que permita relacionar (aproximadamente) o tempo decorrido ao valor de k. Use essa regra para calcular quanto tempo o programa possivelmente levaria para verificar que um número de […]