Cet article présente des algorithmes en arithmétique : diviseurs et factorisation, tests de primalité, algorithmes de factorisation, l’équation de Pell-Fermat.

Son plan est le suivant :
– Diviseurs et multiples
– Le crible d’Eratosthène (Nicomaque de Gérase, L’Introduction Arithmétique, IIe siècle)
– Critères de divisibilité (Pascal, Des caractères de divisibilité des nombres déduits de la somme de leurs chiffres, 1665)
– Calcul des résidus quadratiques (Legendre, Théorie des nombres, 1798 Test de primalité)
– La réciproque du théorème de Fermat (Lucas, Théorie des nombres, 1891 ; Lehmer, Tests for primality by the converse of Fermat’s theorem, 1927)
– Le test de Lucas (Lucas : Théorie des fonctions numériques simplement périodiques, 1878)
– Le test de Pépin Algorithmes de factorisation
– Factorisation par différence de deux carrés (Lettre de Fermat à Mersenne, 1643)
– Factorisation par les résidus quadratiques (Gauss, Recherches arithmétiques, 1801)
– Factorisation par les fractions continues (Lehmer et Powers, On factoring large numbers, 1931 L’équation de Pell-Fermat)
– Les Arithmétiques de Diophante (Diophante, Les six livres d’arithmétique, vers 250)
– Le résultat de Lagrange (Lagrange, Solution d’un problème d’arithmétique, 1766-1769)