Comment #43 on issue 3809 by dana.jac...@gmail.com: isprime can be faster
http://code.google.com/p/sympy/issues/detail?id=3809
Case,
Yes, the dev version works (and does the strong test, yay). Trying to
verify with Feistma's database, I found this segfaults:
is_strong_selfridge_prp("2047"). I can obviously wrap in int, but segfault
seems harsh. Regardless:
is_strong_selfridge_prp indicates composite for all 31.9M spsp2s below
2^64 (as expected and desired).
I looked at MPIR 2.6.0 last month (FLINT uses basically identical code),
and it does some really oddball things. I'm personally dubious about it
being actually BPSW. It does a mix of PSP and SPSP. The Lucas test it
uses has more pseudoprimes than the Lucas-Selfridge tests. For example
number of pseudoprimes under 1e9: 943 extra strong Lucas, 1415 strong
Lucas-Selfridge, 5485 Lucas-Selfridge, 8533 MPIR n_is_pseudoprime_lucas.
This doesn't preclude it from being a good test -- what is important is
that it be disjoint from the other test -- but it doesn't seem promising
given that there doesn't seem to be any reason to do it that way.
All that said, I just ran the Fibonacci/Lucas test against Feitsma's
database, and it has no counterexamples with standard or strong base 2
pseudoprimes under 2^64. Since MPIR 2.6.0 only uses it below 2^64 this is
good enough. For use above 2^64, with 6x the number of pseudoprimes as the
strong Lucas-Selfridge test, there should be a compelling reason to use the
non-standard method, which I just don't see.
David Cleaver's code could be optimized some, but it looks ok, it's easy to
read, and I believe it is used by factordb's Primo validator so gets a lot
of use. I'm not sure it really needs to be replaced unless you need.
You can look at my code here:
https://github.com/danaj/Math-Prime-Util-GMP/blob/master/gmp_main.c which
has all three Lucas tests.
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
