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 """ 

36 Generates random prime number from range [2 ** (kbits - 1); 2 ** (kbist)]. 

37 Uses Miller-Rabin primality test. 

38 

39 Parameters 

40 ---------- 

41 kbits : int 

42 number of bits the prime number should have 

43 seed : int | None, optional 

44 seed for random number generator, by default None 

45 

46 Returns 

47 ------- 

48 int 

49 prime number 

50 """ 

51 a = 2 ** (kbits - 1) 

52 b = 2**kbits 

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