Coverage for src/pqlattice/integer/_primality.py: 82%

1import logging 

2import random 

3from collections.abc import Callable 

4 

5from . import _modring as mr # type: ignore 

6from . import _primes as primes 

7 

8logger = logging.getLogger(__name__) 

9 

10 

11def fermat_primality_test(p: int, s: int, int_gen: Callable[[int, int], int] | None = None) -> bool: 

12 if p <= 1: 

13 return False 

14 

15 if int_gen is None: 

16 int_gen = lambda a, b: random.randint(a, b - 1) 

17 

18 for _ in range(s): 

19 a = int_gen(2, p - 2) 

20 if mr.modpow(a, p - 1, p) == 1: 

21 return False 

22 return True 

23 

24 

25def miller_rabin_primality_test(n: int, s: int, int_gen: Callable[[int, int], int] | None = None) -> bool: 

26 if int_gen is None: 

27 int_gen = lambda a, b: random.randint(a, b) 

28 

29 # n - 1 = r * 2 ** u 

30 u = 0 

31 r = n - 1 

32 while r % 2 == 0: 

33 u += 1 

34 r //= 2 

35 

36 # assert n - 1 == r * 2 ** u, f"{n - 1=}, {r=}, {u=}, {2**u=}, {r * 2 ** u=}" 

37 

38 for _ in range(s): 

39 a = int_gen(2, n - 2) 

40 z = mr.modpow(a, r, n) 

41 for _ in range(u): 

42 y = mr.mod(z * z, n) 

43 if y == 1 and z != 1 and z != n - 1: 

44 # composite 

45 return False 

46 z = y 

47 if z != 1: 

48 # composite 

49 return False 

50 

51 # likely prime 

52 return True 

53 

54 

55def is_prime(p: int) -> bool: 

56 """_summary_ 

57 

58 Parameters 

59 ---------- 

60 p : int 

61 _description_ 

62 

63 Returns 

64 ------- 

65 bool 

66 _description_ 

67 """ 

68 if p <= 1: 

69 return False 

70 

71 for prime in primes.SMALL_PRIMES: 

72 if p == prime: 

73 return True 

74 

75 if p % prime == 0: 

76 return False 

77 

78 return miller_rabin_primality_test(p, 20)