Demonstração da seguinte observação, útil para encontrar raízes primitivas módulo um número primo:
g é uma raiz primitiva modulo o número primo p sse g^((p-1)/q) =/= 1 (mod p) para todo o divisor primo q de p-1.
(ver o  fim do seguinte ficheiro Maple para uma implementação desta observação).
A complexidade do algoritmo de Euclides [para calcular (a,b), sendo b=<a, o número de divisões com resto é O(log b)].
A exponenciação modular e a sua complexidade: a^e mod N pode ser calculado usando apenas O(log e) multiplicações, usando o seguinte algoritmo
INPUT: a, e, N
OUTPUT: a^e mod N
1) x:=a; y:=1; s:=e;
2) enquanto s=/=0, fazer
       b:= s mod 2
          se b=1, então y:=y*x mod N
        x:= x*x mod N
      s:= [s / 2]
3) RETURN y.

(b percorre os bits de e...
s guarda os sucessivos 'quocientes' da decomposição de e em somas de potências de 2...
x guarda as sucessivas potências de a da forma ((a^2)^2)^2...
y guarda os produtos das potências relevantes de a da forma ((a^2)^2)^2...)

Sugestão: implementar este algoritmo numa calculadora (por exemplo, a instrução "b:=s mod 2" pode ser implementada numa TI como: S-iPart(S/2)*2 STO-> S), e observar a velocidade (fenomenal!) com que calcula 367^23651 mod 98587 (por exemplo...; Obs: se N² ultrapassar o número de dígitos significativos com que a máquina opera, os resultados podem ser muito(!) errados por acumulação de aproximações...)

Exercício #3  (a entregar até às 24:00 de 20/11/2003, de preferência por correio electrónico):

Dar exemplo (com justificação) de:

• um número primo com 512 bits, aleatoriamente escolhido (enviar breve descrição do procedimento seguido para o encontrar).

• um número primo com 64 bits, aleatoriamente escolhido, juntamente com uma das suas raízes primitivas.

Quinta 13/11:

Demonstração do seguinte facto: a congruência ax = b (mod m) tem solução sse(a,m) | b; e se tiver solução, então tem (a,m) soluções distintas módulo m.
O Teorema Chinês dos Restos (TCR): versão construtiva e versão abstracta.  Relação entre o TCR e o cálculo de phi(n).