TEORIA DOS NÚMEROS E CRIPTOGRAFIA - 2003/04
António Machiavelo

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).

Descrevemos, com mais detalhe que na aula anterior, a Lei de Reciprocidade Quadrática, e mostramos um exemplo do seu uso para determinar se um número tem ou não uma raiz quadrada mod p.
Descrevemos um protocolo para «lançar uma moeda ao ar» via internet, usam propriedades básicas do símbolo de Legendre.

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.