Coverage for src\pqlattice\random\_prime.py: 96%

1import math 

2import random 

3 

4from ..integer._primality import is_prime 

5 

6 

7def _randprime(a: int, b: int, seed: int | None = None) -> int: 

8 def ilog(n: int, base: float = math.e) -> int: 

9 return int((n.bit_length() - 1) / math.log2(base)) 

10 

11 try: 

12 approx_number_of_primes_to_a = 0 if a == 0 else a // ilog(a) 

13 approx_number_of_primes_to_b = 0 if b == 0 else b // ilog(b) 

14 approx_number_of_primes = approx_number_of_primes_to_b - approx_number_of_primes_to_a 

15 prime_proba = approx_number_of_primes / (b - a) 

16 number_of_samples = int(math.log(0.001) / math.log(1 - prime_proba)) + 1 

17 except ZeroDivisionError: 

18 number_of_samples = b - a 

19 

20 if b - a < 1000: 

21 number_of_samples = b - a 

22 

23 random.seed(seed) 

24 for i in range(number_of_samples): 

25 prime_candidate = random.randint(a, b) 

26 if is_prime(prime_candidate): 

27 return prime_candidate 

28 if is_prime(a + i): 

29 return a + i 

30 

31 raise ValueError(f"Couldn't find a prime number in interval [{a}, {b})") 

32 

33 

34def randprime(kbits: int, seed: int | None = None) -> int: 

35 """_summary_ 

36 

37 Parameters 

38 ---------- 

39 kbits : int 

40 _description_ 

41 seed : int | None, optional 

42 _description_, by default None 

43 

44 Returns 

45 ------- 

46 int 

47 _description_ 

48 """ 

49 a = 2 ** (kbits - 1) 

50 b = 2**kbits 

51 return _randprime(a, b, seed=seed)