Ir ao conteúdo principal

Exercícios 7.4 Exercícios Adicionais: Primalidade e Fatoração

No criptossistema RSA é importante ser capaz de encontrar números primos grandes com facilidade. Da mesma forma, este criptosistema deixa de ser seguro se somos capazes de fatorar um número inteiro que seja o produto de dois números primos grandes. As soluções teóricas de ambos problemas são bastante simples. Para saber se um número \(n\) é primo ou para fatorar \(n\text{,}\) podemos usar tentativas de divisão. Simplesmente dividimos \(n\) entre \(d = 2, 3, \ldots, \sqrt{n}\text{.}\) Dessa forma obteremos uma fatoração ou \(n\) será primo sem nenhum \(d\) dividindo \(n\text{.}\) O problema é que tais cálculos tomam muito tempo se \(n\) é muito grande.

1.

Um algoritmo melhor para fatorar inteiros positivos ímpares é o .

  1. Seja \(n= ab\) um número ímpar composto. Demonstre que \(n\) pode ser escrito como a diferença de dois quadrados perfeitos:

    \begin{equation*} n = x^2 - y^2 = (x - y)(x + y). \end{equation*}

    Portanto, um inteiro positivo ímpar pode ser factorado se e somente se podemos encontrar inteiros \(x\) e \(y\) tais que \(n = x^2 - y^2\text{.}\)

  2. Escreva um programa para implementar o seguinte algoritmo de fatoração baseado na observação da parte (a). A expressão ceiling(sqrt(n)) se refere ao menor inteiro que é maior ou igual a raiz quadrada de \(n\text{.}\) Escreva outro programa que use tentativas de divisão e compare a velocidade dos dois algoritmos. Qual deles é mais rápido e por quê?

x := ceiling(sqrt(n))
y := 1

1 : while x^2 - y^2 > n do
	y := y + 1

if x^2 - y^2 < n then
	x := x + 1
	y := 1
	goto 1
else if x^2 - y^2 = 0 then
	a := x - y
	b := x + y
	write n = a * b
Listagem 7.4.1. algoritmo en pseudo-código

2. Verificação de Primalidade.

Lembre do Pequno Teorema de Fermat do Capítulo 6. Seja \(p\) um primo com \(\gcd(a, p) = 1\text{.}\) Então \(a^{p-1} \equiv 1 \pmod{p}\text{.}\) Podemos usar o Pequeno Teorema de Fermat como um exame para primos. Por exemplo, 15 não pode ser primo pois

\begin{equation*} 2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}. \end{equation*}

Mas, 17 é potencialmente um primo pois

\begin{equation*} 2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}. \end{equation*}

Dizemos que um número composto impar \(n\) é um pseudoprimo se

\begin{equation*} 2^{n-1} \equiv 1 \pmod{n}. \end{equation*}

Quais dos seguintes números são primos e quais são pseudoprimos?

  1. 342

  2. 811

  3. 601

  4. 561

  5. 771

  6. 631

3.

Seja \(n\) um número ímpar composto e \(b\) um inteiro positivo tal que \(\gcd(b, n) = 1\text{.}\) Se \(b^{n-1} \equiv 1 \pmod{n}\text{,}\) então \(n\) é um pseudoprimo na base \(b\text{.}\) Mostre que 341 é um pseudoprimo na base 2 mas não é um pseudoprimo na base 3.

4.

Escreve um programa para determinar todos os primos menores que 2000 usando tentativas de divisão. Escreva um segundo programa que determine todos os números menores que 2000 que sejam primos ou pseudoprimos. Compare a velocidade dos programas. Quantos pseudoprimos menores que 2000 existem?

Existem números compostos que são pseudoprimos para todas as bases que são relativamente primos. Esses números se chamam números de Carmichael. O primeiro número de Carmichael é o \(561 = 3 \cdot 11 \cdot 17\text{.}\) Em 1992, Alford, Granville e Pomerance demostraram que existem infinitos números de Carmichael [4]. Todavia, os números de Carmichael são muito escassos. Existem somente \(2163\) números de Carmichael menores que \(25 \times 10^9\text{.}\) Para testes de primalidade mais sofisticados, veja [1], [6], ou [7].