Skip Menu |


Report information
The Basics
Id: 102076
Status: resolved
Priority: 0/
Queue: Algorithm-BitVector

Owner: Nobody in particular
Requestors: DANAJ [...]

Bug Information
Severity: Normal
Broken in: 1.0
Fixed in: 1.22

Subject: test_for_primality is broken (all MR-tests, and >32-bit inputs)
Download (untitled) / with headers
text/plain 773b
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.


Please report any issues with to