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 = pkm
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 , for each prime number q R, the integer part of lnn/lnq.
We randomly take a number a, 1 < a < n – 1, then calculate
Exclusive to subscribers. 97% yet to be discovered!
Already subscribed? Log in!
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
Exclusive to subscribers. 97% yet to be discovered!
Already subscribed? Log in!
Article included in this offer
"Mathematics"
(
168 articles
)
Updated and enriched with articles validated by our scientific committees
A set of exclusive tools to complement the resources
