You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
It appears the Miller-Rabin test implemented in bigi always chooses the base from the set of primes < 1000, however it is possible to construct a composite that appears prime relative to any fixed set of witnesses, and the paper https://math.dartmouth.edu/~carlp/PDF/reliable.pdf has a proof that there exist integers with no small witnesses at all.
The best fix is probably to choose the witnesses randomly from the range [2,n) which avoids the problem entirely.
The text was updated successfully, but these errors were encountered:
It appears the Miller-Rabin test implemented in bigi always chooses the base from the set of primes < 1000, however it is possible to construct a composite that appears prime relative to any fixed set of witnesses, and the paper https://math.dartmouth.edu/~carlp/PDF/reliable.pdf has a proof that there exist integers with no small witnesses at all.
The best fix is probably to choose the witnesses randomly from the range
[2,n)
which avoids the problem entirely.The text was updated successfully, but these errors were encountered: