[issue40028] Math module method to find prime factors for non-negative int n

[paul rubin]

paul rubin <phr-pythonbugs at nightsong.com> added the comment:

I don't think the interface needs much bikeshedding, as long as the implementer chooses something reasonable.  E.g. factor(30) gives the list [2,3,5].  Implementation is harder if you want to handle numbers of non-trivial size.  Neal Koblitz's book "A Course in Number Theory and Cryptogoraphy" has good coverage of factoring algorithms.  To factor numbers up to 2**64, Pollard's rho method is simple to code and has always worked for me, but I don't know if there are specific numbers in that range that could give it trouble.  For bigger numbers you need fancier algorithms and eventually fancy hardware and long computing runs.  Part of a design discussion would include trying to decide the scope of such a module.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue40028>
_______________________________________