Deterministic Miller-Rabin algorithm for primes ~< 3.32e24. Uses numerical analysis results to return whether or not the passed number is prime. If the passed number is above the upper limit, and allow_probable is True, then a return value of True indicates that n is probably prime.
(n: int, allow_probable: bool = False)
| 4 | |
| 5 | |
| 6 | def miller_rabin(n: int, allow_probable: bool = False) -> bool: |
| 7 | """Deterministic Miller-Rabin algorithm for primes ~< 3.32e24. |
| 8 | |
| 9 | Uses numerical analysis results to return whether or not the passed number |
| 10 | is prime. If the passed number is above the upper limit, and |
| 11 | allow_probable is True, then a return value of True indicates that n is |
| 12 | probably prime. This test does not allow False negatives- a return value |
| 13 | of False is ALWAYS composite. |
| 14 | |
| 15 | Parameters |
| 16 | ---------- |
| 17 | n : int |
| 18 | The integer to be tested. Since we usually care if a number is prime, |
| 19 | n < 2 returns False instead of raising a ValueError. |
| 20 | allow_probable: bool, default False |
| 21 | Whether or not to test n above the upper bound of the deterministic test. |
| 22 | |
| 23 | Raises |
| 24 | ------ |
| 25 | ValueError |
| 26 | |
| 27 | Reference |
| 28 | --------- |
| 29 | https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test |
| 30 | """ |
| 31 | if n == 2: |
| 32 | return True |
| 33 | if not n % 2 or n < 2: |
| 34 | return False |
| 35 | if n > 5 and n % 10 not in (1, 3, 7, 9): # can quickly check last digit |
| 36 | return False |
| 37 | if n > 3_317_044_064_679_887_385_961_981 and not allow_probable: |
| 38 | raise ValueError( |
| 39 | "Warning: upper bound of deterministic test is exceeded. " |
| 40 | "Pass allow_probable=True to allow probabilistic test. " |
| 41 | "A return value of True indicates a probable prime." |
| 42 | ) |
| 43 | # array bounds provided by analysis |
| 44 | bounds = [ |
| 45 | 2_047, |
| 46 | 1_373_653, |
| 47 | 25_326_001, |
| 48 | 3_215_031_751, |
| 49 | 2_152_302_898_747, |
| 50 | 3_474_749_660_383, |
| 51 | 341_550_071_728_321, |
| 52 | 1, |
| 53 | 3_825_123_056_546_413_051, |
| 54 | 1, |
| 55 | 1, |
| 56 | 318_665_857_834_031_151_167_461, |
| 57 | 3_317_044_064_679_887_385_961_981, |
| 58 | ] |
| 59 | |
| 60 | primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41] |
| 61 | for idx, _p in enumerate(bounds, 1): |
| 62 | if n < _p: |
| 63 | # then we have our last prime to check |
no outgoing calls