Français
4. Algorithmic number theory
4.1 Factoring
We present Pollard's p – 1 algorithm. We aim to give the idea implemented in this algorithm rather than the details.
Let n be the number to be factorized. Let p be a prime factor of n : n = p k m
where m is prime to p and assume that all prime factors of p – 1 are less than a small bound R. Let us denote by
The Ultimate Scientific and Technical Reference
This article is included in
Mathematics
This offer includes:
Knowledge Base
Updated and enriched with articles validated by our scientific committees
Services
A set of exclusive tools to complement the resources
Practical Path
Operational and didactic, to guarantee the acquisition of transversal skills
Doc & Quiz
Interactive articles with quizzes, for constructive reading
Algorithmic number theory
Conclusion
References
- - La lecture de cet article suppose du lecteur une certaine familiarité avec les structures algébriques (en particulier finies, c'est-à-dire avec un nombre fini d'éléments) telles que groupes, anneaux, corps. Nous avons essayé de redonner l'essentiel de ce qui est nécessaire au début. Un traitement plus complet est à rechercher dans
The Ultimate Scientific and Technical Reference
