Open fjarri opened 1 year ago
Another strange moment is the following line in miller_rabin()
:
for _ in 1..trials - 1 {
trials
here is such that candidate = odd_number * 2^trials
(or at least it should be in a MR test; miller_rabin()
sets it to at least 5, which obscures the bug). But with the limit set this way, test
only goes up to odd_number * 2^(trials-1)
, so one check is skipped. As a result some of the strong pseudoprimes from https://oeis.org/A001262 are classified as primes (the first one being 3277, if force setting of trials
to 5 is removed).
The decomposition function for MR,
rewrite()
reads:It seems that it should be
while d.is_even()
instead (otherwise it always returnstrials = 0
, and perhaps that's whymiller_rabin()
sets trials to at least 5), but if I make that changeis_prime_tests()
fails. The strange thing is that those tests fail because the MR test fails, but the Lucas test still passes - but that may be an effect of #16? I am not sure how those test numbers were obtained, perhaps you can shed some light on it.