Contents

• Contents
• 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 ${\mathbb{Z} }/(n)$
  • 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