|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.