prime.py (1619B)
1 #Embedded file name: C:\BuildAgent\work\20d73f1b24eed06e\eve\release\V24.01\packages\rsa\prime.py 2 from __future__ import print_function 3 __all__ = ['getprime', 'are_relatively_prime'] 4 import rsa.randnum 5 6 def gcd(p, q): 7 while q != 0: 8 if p < q: 9 p, q = q, p 10 p, q = q, p % q 11 12 return p 13 14 15 def jacobi(a, b): 16 if a == 0: 17 return 0 18 result = 1 19 while a > 1: 20 if a & 1: 21 if (a - 1) * (b - 1) >> 2 & 1: 22 result = -result 23 a, b = b % a, a 24 else: 25 if b * b - 1 >> 3 & 1: 26 result = -result 27 a >>= 1 28 29 if a == 0: 30 return 0 31 return result 32 33 34 def jacobi_witness(x, n): 35 j = jacobi(x, n) % n 36 f = pow(x, n >> 1, n) 37 if j == f: 38 return False 39 return True 40 41 42 def randomized_primality_testing(n, k): 43 for _ in range(k): 44 x = rsa.randnum.randint(n - 1) 45 if jacobi_witness(x, n): 46 return False 47 48 return True 49 50 51 def is_prime(number): 52 return randomized_primality_testing(number, 6) 53 54 55 def getprime(nbits): 56 while True: 57 integer = rsa.randnum.read_random_int(nbits) 58 integer |= 1 59 if is_prime(integer): 60 return integer 61 62 63 def are_relatively_prime(a, b): 64 d = gcd(a, b) 65 return d == 1 66 67 68 if __name__ == '__main__': 69 print('Running doctests 1000x or until failure') 70 import doctest 71 for count in range(1000): 72 failures, tests = doctest.testmod() 73 if failures: 74 break 75 if count and count % 100 == 0: 76 print('%i times' % count) 77 78 print('Doctests done')