Segunda 15/12:

Introduzimos a noção de pseudoprimo forte de base a: um número composto e ímpar, n, tal que, se s e t são tais que n-1 = 2^s * t, com t ímpar, então a^t = 1 (mod n) ou a^(2^i*t) = -1 (mod n), para algum 0 =< i =< s-1.
Um número a para o qual n não é um pseudoprimo forte de base a diz-se uma testemunha para n (é uma testemunha de que n é composto...).

Mencionamos um resultado de Bach, de 1985, segundo o qual a Hipótese Extendida de Riemann (ERH em inglês...) implica a existência de uma testemunha, para todo o número natural ímpar n, que é menor que 2 log²(n). Descrevemos, em traços gerais, a Hipótese de Riemann (um dos «Problemas do Milénio», ver também esta página) , o que são caracteres de Dirichlet e a Hipótese Extendida de Riemann (ver página da Wikipedia, onde o nome "Extended" aparece trocado com o de "Generalized", parecendo haver alguma confusão entre os dois na literatura sobre o assunto...).

Descrevemos o Teste de Primalidade (condicional, por depender da ERH) de Miller (os detalhes não ficaram claros - ver sumário da aula seguinte).

Introduzimos a noção de resíduo quadrático módulo um primo p (um número não nulo que é um quadrado mod p); demos alguns exemplos e observamos que existem tantos resíduos quadráticos quanto resíduos não-quadráticos mod p. Introduzimos o símbolo de Legendre, explicamos as suas principais propriedades e descrevemos a Lei de Reciprocidade Quadrática.

Quinta 18/12:

Começamos por descrever com algum detalhe o teste de primalidade (condicional) de Miller, com o objectivo de clarificar o que na aula anterior tinha ficado confuso:

INPUT: n, um ímpar.
OUTPUT: 0 (=> n composto) ; 1 (=> n primo ou ERH é falsa).

• calcular s, t tais que n-1 = 2^s * t, com t ímpar.
• w := min {[2 log(n)^2, n-2]}
• r :=1:

for a from 2 to w do
  r' := 0:
  if a^t <> 1 mod n then
      for i from 0 to s-1 do
        if (a^t)^(2^i) = -1 mod n then r':=1: break: fi:
      od:
    else r':=1:
  fi:
  if r' = 0 then r :=0: break: fi:
od:
• return r;

Introduzimos o símbolo de Jacobi, descrevemos as suas propriedades básicas e a Lei de Reciprocidade para este símbolo, que generaliza a Lei de Reciprocidade para o símbolo de Legendre. Mostramos como o símbolo de Jacobi é usado para acelerar o cálculo do símbolo de Legendre, que observamos ter básicamente a mesma ordem de complexidade que o algoritmo de Euclides.

TPC:
No que se segue, (. /.) representa o símbolo de Jacobi.
1) Calcular (com lápis e papel apenas...): (-1 / 7919) ; (2 / 107) ; (105 / 127); (1987 / 7919).
2) Explicar porque é que se tiver (a / m) = 1, isso não implica que a seja um quadrado mod m, quando m é composto. Dar exemplos de números a e m tais que (a / m) = 1 e a não é um quadrado mod m.