Anonymous user
Miller–Rabin primality test: Difference between revisions
→Python: Proved correct up to large N: Reword, and mention that this uses an old paper and we know better results.
(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:
===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
<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):
| |||