#!/usr/bin/env python3
import sys
from random import randrange, SystemRandom
# from secrets import SystemRandom
from psutil import cpu_count
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,
k=192,
def_list=[],
min_s=0,
totient_coprimes=[65537],
stop=[False]
):
""" 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[0] = True
return False
if n <= 1 or n % 2 == 0:
stop[0] = True
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[0] = True
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[0] = True
return False
"""
Next, check against known primes.
"""
for dp in def_list:
if stop[0]:
return False
if dp >= n:
return True
if n % dp == 0:
stop[0] = True
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[0]:
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[0] = True
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[0] = True
return False
j += 1
if x != n - 1:
stop[0] = True
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(16384)
cores = cpu_count(logical=False)
pool = Pool(processes=cores)
# keep generating while the primality test fail
while True:
nums=[]
inputs=[]
for i in range(512):
p += 4
if p >= length_v:
p -= length_v >> 1
p2 = p >> 1
nums.append(p)
inputs.append((p, 192, def_list, min_s, [], [False]))
inputs.append((p2, 192, def_list, min_s, [], [False]))
inputs.reverse() #assuming smallest results are prefered
nums.reverse() #same here
async_result = pool.starmap_async(is_prime,inputs, chunksize=4)
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=False) == None:
print("Could not read number of physical CPU cores!")
return False
input1 = 512
if 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)
if __name__ == '__main__':
main()