Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(Mercury: minor format edit. Oz: added the language.) |
(→Python: Proved correct up to large N: Reword, and mention that this uses an old paper and we know better results.) |
||
| Line 2,643: | Line 2,643: | ||
===Python: Proved correct up to large N=== |
===Python: Proved correct up to large N=== |
||
This versions will give correct answers for <code>n</code> less than 341550071728321 and then reverting to the probabilistic form of the first solution. By selecting |
This versions will give correct answers for <code>n</code> less than 341550071728321 and then reverting to the probabilistic form of the first solution. By selecting [http://primes.utm.edu/prove/prove2_3.html predetermined values] for the <code>a</code> values to use instead of random values, the results can be shown to be deterministically correct below certain thresholds. |
||
<br>For 341550071728321 and beyond, I have followed the pattern in choosing <code>a</code> from the set of prime numbers. |
<br>For 341550071728321 and beyond, I have followed the pattern in choosing <code>a</code> from the set of prime numbers.<br>While this uses the best sets known in 1993, there are [http://miller-rabin.appspot.com/ better sets known], and at most 7 are needed for 64-bit numbers. |
||
<lang python>def _try_composite(a, d, n, s): |
<lang python>def _try_composite(a, d, n, s): |
||