Segunda 5/01:

Sequências (ou sucessões) de recorrência linear ( de 2ª ordem ou binárias): polinómio associado e fórmula «fechada» no caso de este ser separável (= ter raízes distintas). Exemplos: sequência de Fibonacci (fn+1 = fn + fn-1 ; f0:= 0 , f1:= 1) e sequência de Lucas (Ln+1 = Ln + Ln-1 ; L0:= 2 ,  L1:= 1) .
Teorema I: p primo e (p , 10)=1 ===> p | fp - (5 / p), onde (. /.) é o símbolo de Legendre.
Pseudoprimos de Fibonacci (n composto e primo com 10 tal que n | fn - (5 / n)).

Observação: não se conhece nenhum número n = +/- 2 (mod 5) que seja simultaneamente um pseudoprimo de Fibonacci e um pseudoprimo de Fermat de base 2 (i.e. n tal que n | fn+1 e 2^{n-1} = 1 (mod n)). Pomerance, Selfridge e Wagstaff oferecem $620 pelo 1º exemplo ($20 + $500 + $100, respectivamente), assim como por uma prova que tal número não existe (mas agora as respectivas contribuições são: $500 + $20 + $100...) [Candrall&Pomerance, p. 156].

Seja f(x) = x^2 - a x + b, com a e b inteiros  tais que D = a^2 - 4b não é um quadrado, e sejam r e s as duas raízes distintas de f(x). As sequências (Un)n e (Vn)n definidas por  Un:= (r^n - s^n) / (r - s) e Vn:= r^n + s^n satisfazem ambas a relação de recorrência Wn+1 = a Wn - b Wn-1 , tendo-se U0 = 0 e U1 = 1, V0 = 2 e V1 = a.
Teorema II(que generaliza o anterior): p primo e (p , 2bD)=1 == => p | Up - (D / p), onde (. /.) é o símbolo de Legendre.
Pseudoprimos de Lucas relativamente a x^2 - a x + b (n composto e primo com 2bD tal que n | Un - (D / n)).

Teste de Lucas. As relações: Un = (2 Vn+1 - a Vn) / D e Vm+n =VmVn - b^j * Vm-n  (0=< n=< m) e como verificar «eficientemente» a condição n | Un - (D / n) (apenas  foi descrito o caso b = 1).

TPC:
1) Demonstrar a relação Un = (2 Vn+1 - a Vn) / D.
2) Completar a demonstração do teorema II (na aula só fizemos uma das 'metades').

Quinta 8/01:

Fizemos uma breve menção ao algoritmo de primalidade APR (com somas de Gauss) e ao algoritmo polinomial de primalidade AKS.
Método de factorização de Fermat. Exemplos.
Conceito de número B-suave (onde B é um número real positivo): número cujos factores primos são todos menores ou iguais a B.
Descrição das principais ideias por detrás do método de factorização conhecido pelo nome de «Crivo Quadrático» (não houve tempo para descrever em detalhe a parte do «crivo»... para uma descrição um pouco mais detalhada, mas não com todos os detalhes, ver o seguinte artigo de Eric Landquist).

(Não estou completamente satisfeito com os "sites" acima escolhidos...são razoáveis, mas gostava de melhor)

TPC:
1) Implementar de um modo eficiente, numa cálculadora gráfica, o método de factorização de Fermat e brincar com o programa.
2) Para B = 100, quantos resíduos B-suaves é necessário (no máximo) para, usando o método do Crivo Quadrático, obter uma dependência linear que permita encontrar uma solução de x^2 = y^2 (mod n) ?