Quinta 4/12:

Demonstramos o seguinte resultado: dado um número real a, toda a fracção irreditível a/b que satisfaça a desigualdade |a - a/b| < 1/ (2b²) é uma das convergentes de a.
Usando este facto, provamos o seguinte teorema de M. J. Wiener (1990): Seja N = p q, com q < p < 2q, e seja N, e, d uma cifra RSA. Se d < 1/3 N^{1/4}, então consegue-se determinar d em tempo O (log N).

Exercício #5 (a entregar até às 24:00 de 5/01/2004, de preferência por correio electrónico num ficheiro chamado TNCex5Nome.mws (ou .pdf), onde Nome deve ser o primeiro nome do aluno/a)
Sabendo que não foram tomadas as devidas precauções contra o ataque de Wiener, factorizar o número:

N:= 6341267647464250881745679057299014913560630196329010636154081186524315476488887876818485
16676766037068805199738822368924900915874229216261960339930157678989442695745632769821977358
00716012204589780203791593994897092703704366104046430366388968030965021190171363173229475316
701753301711538966870046711758973777,

usado numa cifra RSA com:

e:= 1778628832029775539715151060814584875704182505354883646709913518548148993532605634516231
8268973816755296273642559679170165942945752765865191649760335152597694775047267706123263580
6136437121101211555592349389201454560069489787839017462669515090322402198264390915777572322
71260681477457418317763127761827668001.

Obs.: N tem 1023 bits; e tem 1021 bits.

Quinta 11/12:

Pseudoprimos de Fermat de base a: números compostos n tais que a^(n-1) = 1 mod n.
Exemplo: 341 = 11 * 31 é um pseudoprimo de Fermat de base 2, mas não o é para a base 3.

Mencionamos o seguinte resultado:
Teorema (P. Erdos, 1950): Para todo a >= 2, o número de pseudoprimos de Fermat de base a que são =< x é o( pi(x) ), quando x -> infinito.
[f = o(g) quando x ->infinito significa: f(x) / g(x) -> 0 quando x -> infinito ; pi(x) denota o números de primos =< x].

Provamos que, para todo a > 1, há uma infinidade de primos de Fermat de base a.
[Explicitamente: se p é um primo ímpar que não divide a² - 1, então n:= (a^{2p} - 1) / (a² - 1) é um pseudoprimo de Fermat de base a].

Números de Carmichael: números compostos n tais que a^n = a mod n, para todos os inteiros a. (Obs: a definição varia um pouco na literatura, variação essa relacionada com as duas formas equivalentes do "Pequeno" Teorema de Fermat...)
Exemplo: 561 = 3 * 11 * 17 é o menor número de Carmichael.
Observação: Não se difícil mostrar que t é tal que 6t +1, 12 t + 1 e 18 t + 1 são todos primos, então o seu produto é um número de Carmichael, mas não se sabe se existe uma infinidade de tais números t.

Seja C(x):= # {números de Carmichael =< x}. Em 1956, P. Erdos, usando um raciocínio heurístico, argumentou que se deve ter, para todo e, C(x) > x^{1-e}, para x  suficientemente grande (dependendo de e), o que mostra (se for verdade) que os números de Carmichael não são tão raros quanto se poderia esperar...
Em 1994, Alford, Granville and Pomerance provaram que há uma infinidade de números de Carmichael. Mais especificamente provaram que C(x) > x^{2 / 7}, para x suficientemente grande (na opinião de Pomerance tal deve acontecer a partir do 96º número de Carmichael: 8719309...).
Mencionamos a seguinte conjectura de P. Erdos e Pomerance: C(x) = x^{1-(1 + o(1)) ln ln ln(x) / ln ln(x)}.

Finalmente vimos o resultado seguinte:
Seja p um primo ímpar, p - 1 = 2^s*t, com t ímpar e a um número não divisível por p.
Então: a^t = 1 (mod p) ou a^(2^i*t) = -1 (mod p), para algum 0 =< i =< s-1.