Primos de Mersenne (e outros primos muito grandes)

Carlos Gustavo T. A. Moreira, Nicolau C. Saldanha

• Contents
• Introdu��o
• Divisibilidade e congru�ncias
  • Divis�o euclidiana e o teorema fundamental da aritm�tica
  • Congru�ncias
  • A fun��o de Euler e o pequeno teorema de Fermat
  • A fun��o de M�bius
  • Bases
  • Sobre a distribui��o dos n�meros primos
  • Outros resultados e conjecturas sobre primos
• Corpos finitos e reciprocidade quadr�tica
  • Corpos e polin�mios
  • Ordens e ra�zes primitivas
  • Ra�zes primitivas em
  • A lei da reciprocidade quadr�tica
  • Extens�es quadr�ticas de corpos finitos
• Primos de Mersenne e testes de primalidade
  • F�rmulas para primos e testes de primalidade
  • Testes baseados em fatora��es de n-1
  • Primos de Mersenne
  • Testes baseados em fatora��es de n+1
• Aspectos computacionais
  • Primeiras tentativas
  • Alguns programas usando a biblioteca gmp
  • O algoritmo de multiplica��o de Karatsuba
  • Multiplica��o de polin�mios usando FFT
  • Multiplica��o de inteiros usando FFT
  • A complexidade das opera��es aritm�ticas
  • Tabelas
• Refer�ncias
• About this document ...