(num: int)
| 4 | |
| 5 | |
| 6 | def rabin_miller(num: int) -> bool: |
| 7 | s = num - 1 |
| 8 | t = 0 |
| 9 | |
| 10 | while s % 2 == 0: |
| 11 | s = s // 2 |
| 12 | t += 1 |
| 13 | |
| 14 | for _ in range(5): |
| 15 | a = random.randrange(2, num - 1) |
| 16 | v = pow(a, s, num) |
| 17 | if v != 1: |
| 18 | i = 0 |
| 19 | while v != (num - 1): |
| 20 | if i == t - 1: |
| 21 | return False |
| 22 | else: |
| 23 | i = i + 1 |
| 24 | v = (v**2) % num |
| 25 | return True |
| 26 | |
| 27 | |
| 28 | def is_prime_low_num(num: int) -> bool: |