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

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

Some of the things that might go into a PEP, or into the PEP-creation process:

- Arguments for:

  (a) a new imath module, versus
  (b) new functions in math, versus
  (c) a 3rd party package on PyPI.

- A handful of plausible use-cases.

- Comparisons with what other languages provide.

- Discussion of how to handle existing integer math functions (gcd, factorial, isqrt, comb, perm, ...). If we had an imath module, users would probably expect to find many of these in that imath rather than in math. Do we re-export these functions in imath? If so, do we live with the duplication indefinitely, or aim for eventual deprecation and removal of the math module functions? Over what time period would such deprecation happen? Or do we leave everything where it is and simply add a "see also" documentation note to the imath documentation directing users to those math module functions?

- Outline of the minimal coherent set of things that we want to implement.
  - Q: do we want "primes_below / small_primes" _and_ a lazy prime generator, or just one? Which one?
  - Q: do we need nextprime and prevprime?
  - Q: do we want a deterministic prime test in addition to a probable prime test (however slow that may be)?
  - Q: do we need random prime (or probable prime) generation?

- Proposed APIs for each of those things (mostly straightforward, but not entirely so). There are lots of potentially contentious details here, like how to handle factorization of non-positive integers, the format for the factorization output (pairs of (prime, exponent)? repeated primes? guaranteed sorted?), etc.; we've already discussed the fun involved in probabilistic prime testing.

- The inevitable bikeshedding on names. factorize? factorise? factor? factorint? nextprime? next_prime?

I'd also like to have set out some kind of coherent set of goals / design decisions for the module that will help us make decisions in the future about whether a particular proposed shiny new thing should be included or not, whether it belongs in math or in imath, and that for new things in imath would help guide the API for that new thing. Are we aiming for a basic set of building blocks, or something more complete? Are we thinking about security concerns (adversarial attacks on probabilistic prime testing), or are those out of scope?

Algorithmic details (as opposed to API) should mostly be out of scope for the PEP, but there'll be plenty to discuss if/when we get to implementation stage. (For factorization, I think we'll need to say _something_, so that users can have reasonable expectations about what size of composite can be factorised in a reasonable amount of time.)

----------

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