Comment #23 on issue 3809 by [email protected]: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Well, AFAIK, for the cases in the _mr_safe function (that is for if n <
10000000000000000), we can just test for certain primes and know _for sure_
whether n is prime or not. So there using primes as witnesses is justified.
Beyond that, we are using a list of 46 different primes to test for n not
composite. The overall probability that n is not prime will then be
(1/4)**46 which is good enough. As to your question, no, I do not think
that we need to have only primes to test for n > 10000000000000000. From
reading the algorithm on the internet, I think we should be able to take
any composite numbers as witness to the primality. Though why only primes
were used, I don't know.
I think it's quite clear
(http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Algorithm_and_running_time)
that we can use composites.
Also, I do not know whether it will make much of a difference to not use
primes. We are doing pow(base, t, n) (line 58) where `base` is the number
in question. Unless pow can work better for composite bases compared to
prime bases, I think that it would be immaterial whether it is prime or
composite.
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sympy-issues?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
