#!/usr/bin/env python3 import sys from random import randrange, SystemRandom # from secrets import SystemRandom from psutil import cpu_count from multiprocessing import Array from multiprocessing.pool import Pool # For Python 2, maxsize should be replaced by maxint , # As is the case further below... # However, multi-threaded functioning seems impaired under Python 2.7 . # Python 3.4 recommended as minimum version. def sift_primes(primes_list, pc): """Append entery to primes list, if not divisible by any existing entry. Args: primes_list -- list -- Existing Primes pc -- int -- Prime Candidate return True if pc was added """ for dp in primes_list: if pc % dp == 0: return False primes_list.append(pc) return True def smallprimes(max = 65535): """Compute a list of known primes.""" primes_list = [2, 3] i = 5 while i <= max: sift_primes(primes_list, i) i += 2 return primes_list def is_prime( n, stop, k=192, def_list=[], min_s=0, totient_coprimes=[65537] ): """ Test if a number is prime Args: n -- int -- the number to test k -- int -- the number of combined tests def_list -- int list -- definite known primes, if any, gapless and in ascending order Must start from 2 or 3 min_s -- int -- See below... totient_coprimes -- int list -- What the totient must not be divisible by, which is odd return True if n is prime, and n-1 is divisible by 2^min_s And as long as the probability of non-primeness is extremely small Hence, False could result when n is actually prime This probability can be reduced by setting (min_s = 2), thereby also saving time Setting (min_s > 2) or (min_s = 1) has no known benefits Setting (min_s = -1) will reduce the security, and guarantee that False is only returned, when n is not prime (Not recommended for cryptography) """ # Test if n is not even. # Prevent some error-loops. if min_s < 1 and n == 2: return True if min_s < 2 and n == 3: return True if n == 3: stop_threads[stop] = 1 return False if n <= 1 or n % 2 == 0: stop_threads[stop] = 1 return False """ First, make sure that the tentative prime - 1 will be coprime with a Public-Key Exponent. """ for dp in totient_coprimes: if dp <= 2: continue if ( (min_s > 1) and ((1 << min_s) % dp == 0) ): continue if (n - 1) % dp == 0: stop_threads[stop] = 1 return False # find r and s s = 0 r = n - 1 while r & 1 == 0: s += 1 r //= 2 """ A radical safeguard: Reject if s < 2 Even though n could be prime, Just because the available test would be no stronger than the Fermat Test. """ if min_s > 0 and s < min_s: stop_threads[stop] = 1 return False """ Next, check against known primes. """ for dp in def_list: if stop_threads[stop] == 1: return False if dp >= n: return True if n % dp == 0: stop_threads[stop] = 1 return False if len(def_list) > 0: highest_known_prime = def_list[len(def_list) - 1] highest_known_prime *= highest_known_prime if n < highest_known_prime: return True """ Additional safeguard: If a^r mod n == 1 ... The probability turned out to be 1 / (2^s) . If this probability is exceeded greatly, reject n. """ odd_ones = 0 # max_oo = (3 * k) // (1 << (s + 1)) # do k tests n1 = (1 << 32) - 1 for _ in range(k): if stop_threads[stop] == 1: return False # Fermat Test will no longer be performed... # Proceed with (modified) Miller-Rabin Test. a = randrange(2, n - 1) # Because the randrange function is weak, # double the density of witnesses it will generate... if a > n1 + 1: a -= randrange(0, n1) x = pow(a, r, n) if min_s != -1 and x == 1: odd_ones += 1 if odd_ones == k: stop_threads[stop] = 1 return False if x != 1 and x != n - 1: j = 1 while j < s and x != n - 1: x = pow(x, 2, n) if x == 1: stop_threads[stop] = 1 return False j += 1 if x != n - 1: stop_threads[stop] = 1 return False return True def generate_prime_candidate(length, rng, min_s=0): """ Generate an odd integer randomly Args: length -- int -- the length of the number to generate, in bits Minimum: min_s + 1 rng -- object -- System Random Number Generator min_s -- int -- Power of 2, which (prime - 1) must be divisible by return an integer """ # Find chunk size of SystemRandom # For Python 2, maxsize should be replaced by maxint . maxint_v = 2 maxint_s = 1 while maxint_v < sys.maxsize: maxint_s += 1 maxint_v = maxint_v << 1 maxint_v -= 1 # Create min_s related mask min_s_mask = 0 i = 1 while i < min_s: min_s_mask |= 1 << i i += 1 # generate random bits p = 0 remainder = length % maxint_s for _ in range((length + maxint_s - 1) // maxint_s): p = p << maxint_s p += rng.randint(0, maxint_v) if remainder > 0: p = p >> (maxint_s - remainder) """ If the primeness test was merely to fail, because (p - 1) was divisible by 2^min_s Then, as many requests for the system random number generator would be wasted. Therefore, the cause of such failures can be eliminated, before testing for primeness. """ # Apply min_s_mask if min_s > 1: p |= 1 << max(length - 1, min_s) p -= 1 << min_s p |= min_s_mask p += 2 # apply a mask to set MSB and LSB to 1 p |= (1 << length - 1) | 1 return p def gen_prim_root(mod, t2): """Generate Primitive Root of prime number Args: mod -- int -- assumed prime t2 -- int -- Totient / 2, assumed to be prime as well return Primitve Root for use as generator """ m = 1 while True: m += 1 if pow(m, 2, mod) == 1: continue if pow(m, t2, mod) == 1: continue return m def generate_strong_prime(length=1024): """ Generate a prime Args: length -- int -- length of the prime to generate, in bits return a strong prime """ if length < 3: return 7 length_v = 1 << length rng = SystemRandom() # Disable strictness min_s = 0 p = generate_prime_candidate(length, rng, min_s) | 3 def_list = smallprimes(4096) cores = cpu_count(logical=False) if cores == None or cores < 2: cores = 2 pool = Pool(processes=cores) # keep generating while the primality test fail while True: nums = [] inputs = [] for i in range(256): stop_threads[i] = 0 for i in range(256): p += 4 if p >= length_v: p -= length_v >> 1 p2 = p >> 1 nums.append(p) inputs.append((p, i, 192, def_list, 0, [])) inputs.append((p2, i, 192, def_list, min_s, [])) inputs.reverse() #assuming smallest results are preferred nums.reverse() #same here async_result = pool.starmap_async(is_prime, inputs, chunksize=1) results = async_result.get() while len(results)!=0: res1=results.pop() res2=results.pop() res3=nums.pop() if res1 and res2: return res3 def main(): """Main function for executable.""" input = sys.argv if cpu_count(logical=True) == None: print("Could not read number of logical CPU cores!") return False input1 = 512 if cpu_count(logical=False) == None or cpu_count(logical=False) < 2: input1 = 256 if len(input) > 1: input1 = int(input[1]) n = generate_strong_prime(input1) g = gen_prim_root(n, (n - 1) >> 1) print(n) print(g) return True if __name__ == '__main__': stop_threads = Array('i', 256) main()