| Subject: | test_for_primality is broken (all MR-tests, and >32-bit inputs) |
In test_for_primality, you need parens around the '$q & 1' in the while loop. Otherwise $k is getting set incorrectly, and the M-R tests are wrong. See the example 252601 = 41*61*101, which is reported as a prime even though it is not a strong pseudoprime to bases 3,5,7,11,13, or 17. This is due to $k being set incorrectly.
You may know, but since you're using fixed bases, the "with probability" if with respect to random inputs. Given a composite that passes those bases (e.g. 341550071728321) it will incorrectly report "is prime" 100% of the time.
Additionally, this needs something to either die with inputs larger than 32-bits, or a fix. 4294971377 is a prime, but the module reports it as composite (this is just one of many examples).
Also broken in v1.1.