Comment #2 on issue 3809 by prasoon9...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Well, we are using the Rabin-Miller Strong Pseudoprime Test
(http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html) right
now which is probabilistic in nature.
The AKS primality testing algorithm is a deterministic algorithm. If we
want to go with a deterministic algorithm anyway, we should in fact use
Lenstra and Pomerance (http://www.math.dartmouth.edu/~carlp/aks041411.pdf)
which is an improvement over the AKS algorithm.
Mathematica seems to use another probabilistic algorithm as well though
(http://mathworld.wolfram.com/LucasPseudoprime.html) so perhaps we should
implement that as well.
In fact, I believe that we should come up with a mix to use these
algorithms for appropriate cases. There should be a cross-over point where
the deterministic version works better compared to the probabilistic one.
So we can use that to use either a one or the other version depending on
the crossover point.
Perhaps someone with more knowledge in number theory can give more insights?
The code isprime(int("1808010808"*1560 + "1")) should return within a
couple of minutes.
It seems it does on PyPy (<18 minutes according to one of the comments).
--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings
--
You received this message because you are subscribed to the Google Groups
"sympy-issues" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sympy-issues+unsubscr...@googlegroups.com.
To post to this group, send email to sympy-issues@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy-issues?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
