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

Mark Dickinson added the comment: [Rémi Lapeyre] > In the end, if some core devs think that putting together the various > discussions for an imath module in a coherent PEP [...] I can't answer for other core devs. My *guess* is that there's a reasonable chance that a well-written PEP for

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

Steven D'Aprano added the comment: On Fri, May 22, 2020 at 10:23:06AM +, Rémi Lapeyre wrote: > As you said the PEP would have to explain why not just use sympy and > honestly I don't have a very good argument there for now. Because sympy is a beast. It's an excellent beast, but its an

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

Rémi Lapeyre added the comment: Hi Mark Dickinson, I was waiting for everyone to have a chance to comment on this issue and read their reply before answering. It seems to me that there some core developers are mildly in favor of a new imath module and it's has been proposed on the bug

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

Mark Dickinson added the comment: It seems we don't have a champion (someone willing to write a PEP) for this issue. I'm going to close. And if or when we do have such a champion, it probably makes more sense to re-open #37132, which is specifically about adding `imath`, or make a new

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

Change by Mark Dickinson : -- versions: +Python 3.10 -Python 3.9 ___ Python tracker ___ ___ Python-bugs-list mailing list

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

Mark Dickinson added the comment: @Rémi Lapeyre (since you requested re-opening of the issue :-) Are you interested in putting together a PEP for this? -- ___ Python tracker

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

Christian Heimes added the comment: > I don't think the interface needs much bikeshedding, as long as the > implementer chooses something reasonable. Bikeshedding works more like "build it and they will come". It's going to happen especially when the interface looks easy. --

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

paul rubin 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

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

STINNER Victor added the comment: I suggest to implement this idea on PyPI first and only later propose it for inclusion in the stdlib (as a new module, or into an existing module). Bikeshedding on names, debate on the appropriate trade-off between correctness and speed, how many

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

paul rubin added the comment: I'm the one always asking for more stuff in the stdlib, but above some simplistic approaches this seems out of scope. Doing it usefully above say 2**32 requires fancy algorithms. Better to use some external package that implements that stuff. --

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

Dennis Sweeney added the comment: For some more ideas for features or APIs, you could look at: https://docs.sympy.org/latest/modules/ntheory.html or http://doc.sagemath.org/html/en/reference/rings_standard/sage/arith/misc.html for an absolute upper bound. If there's to be a minimal number

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

Mark Dickinson 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

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

Change by Christian Heimes : -- stage: resolved -> ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

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

Christian Heimes added the comment: It seems we agree that prime functions only appear to be easy until you realize that they are far from trivial. :) +1 to require a PEP. I'm happy to give my feedback on crypto and security-related part of the feature. OpenSSL now uses 64 MR rounds for

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

Steven D'Aprano added the comment: Speaking of OpenSSL, a few years ago this paper came out about OpenSSL's vulnerability to adversarial composites. Quote: "As examples of our findings, weare able to construct 2048-bit composites that are declared prime with probability 1/16 byOpenSSL’s

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

Mark Dickinson added the comment: Reopening as requested. Adding a new module to the standard library is a fairly big change. I don't think we can do that through just this issue and PR. I think we're going to need a PEP sooner or later. (In any case, a PEP is standard procedure for a new

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

Mark Dickinson added the comment: Here's the relevant part of the dev. guide: https://devguide.python.org/stdlibchanges/#proposal-process The PEP would also need a core dev sponsor. -- ___ Python tracker

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

Christian Heimes added the comment: I'm still not convinced that it's a good idea to add a general prime factor function to Python's standard library. IMO the feature is better suited for an external math library or crypto library. If we are going to add a prime factor function, then we

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

Steven D'Aprano added the comment: Miller-Rabin is known to be deterministic for all N < 2**64 too. To be pedantic, M-R is known to be deterministic if you check every value up to sqrt(N), or possibly 2*log(N) if the generalized Riemann hypothesis is true. The question is whether there is a

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

Rémi Lapeyre added the comment: I can't mark the issue as open thought, can someone do this? -- ___ Python tracker ___ ___

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

Rémi Lapeyre added the comment: >> Regardless, how can we best move forward with this idea? > Provide a pull request. Hi, I looked into what scientific programs where doing. Most of them uses a form of the Baillie–PSW primality test which is a probabilistic primality test that's never wrong

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

Change by Rémi Lapeyre : -- nosy: +remi.lapeyre nosy_count: 7.0 -> 8.0 pull_requests: +19232 pull_request: https://github.com/python/cpython/pull/19918 ___ Python tracker ___

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

Ross Rhodes added the comment: Unable to dedicate time to this issue under the change of circumstances. Happy for someone else to re-open this if they take an interest in picking up this work. -- resolution: -> postponed stage: needs patch -> resolved status: open -> closed

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

Tim Peters added the comment: Jonathan, _almost_ no factoring algorithms have any use for a table of primes. Brute force trial division can use one, but that's about it. A table of primes _is_ useful for implementing functions related to pi(x) = the number of primes <= x, and the bigger

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

Raymond Hettinger added the comment: I would just call gnu's gfactor for this task. -- nosy: +rhettinger ___ Python tracker ___

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

Jonathan Fine added the comment: A pre-computed table of primes might be better. Of course, how long should the table be. There's an infinity of primes. Consider >>> 2**32 4294967296 This number is approximately 4 * (10**9). According to https://en.wikipedia.org/wiki/Prime_number_theorem,

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

Ross Rhodes added the comment: Hi Steven, I agree, your set of proposed methods seem sensible to me. I'm happy to start with an implementation of at least some of those methods and open for review, taking this one step at a time for easier review and regular feedback. > Another question:

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

Steven D'Aprano added the comment: Ross: "implement this logic for a limited range of non-negative n, imposing an upper limit (suggestions welcome) to make sure all provided input can be safely processed. We can then build from there to support larger n going forward if the demand is out

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

Steven D'Aprano added the comment: I don't know... To my mind, if we are going to support working with primes, the minimum API is: - is_prime(n) - next_prime(n) - prev_prime(n) - factorise(n) - generate_primes(start=0) (I trust the names are self-explanatory.) There are various other

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

Ross Rhodes added the comment: Hi Serhiy, > Provide a pull request. Apologies, by "this idea" I should clarify I meant the "imath" module proposal. On this particular enhancement, yes, I'm happy to work on and later provide a pull request. --

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

Serhiy Storchaka added the comment: > Regardless, how can we best move forward with this idea? Provide a pull request. -- ___ Python tracker ___

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

Ross Rhodes added the comment: Hi Serhiy, Thanks for sharing your thread. I support this proposal, and would be happy to help where time permits if we can gather sufficient support. I inadvertently posted my support twice on your thread with no obvious means of deleting the duplicate post,

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

Serhiy Storchaka added the comment: > Are there any open discussions or threads following the proposed “imath” > module? https://mail.python.org/archives/list/python-id...@python.org/message/YYJ5YJBJNCVXQWK5K3WSVNMPUSV56LOR/ Issue37132. -- nosy: +serhiy.storchaka

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

Ross Rhodes added the comment: Hi Tim, Are there any open discussions or threads following the proposed “imath” module? I’m a relatively new entrant to the Python community, so if there’s any ongoing discussion on that front I’d be happy to read further. I think as a first step it would be

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

Tim Peters added the comment: Good idea, but yet another that really belongs in an `imath` module (which doesn't yet exist). How ambitious should it be? Sympy supplies a `factorint()` function for this, which uses 4 approaches under the covers: perfect power, trial division, Pollard rho,

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

Change by Mark Dickinson : -- nosy: +mark.dickinson ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

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

New submission from Ross Rhodes : Hello, Thoughts on a new function in the math module to find prime factors for non-negative integer, n? After a brief search, I haven't found previous enhancement tickets raised for this proposal, and I am not aware of any built-in method within either