from random import randrange, getrandbits
def is_prime(n, k=128):
""" Test if a number is prime
Args:
n -- int -- the number to test
k -- int -- the number of tests to do
return True if n is prime
"""
# Test if n is not even.
# But care, 2 is prime !
if n == 2 or n == 3:
return True
if n <= 1 or n % 2 == 0:
return False
# find r and s
s = 0
r = n - 1
while r & 1 == 0:
s += 1
r //= 2
# do k tests
for _ in range(k):
a = randrange(2, n - 1)
x = pow(a, r, n)
if x != 1 and x != n - 1:
j = 1
while j < s and x != n - 1:
x = pow(x, 2, n)
if x == 1:
return False
j += 1
if x != n - 1:
return False
return True
def generate_prime_candidate(length):
""" Generate an odd integer randomly
Args:
length -- int -- the length of the number to generate, in bits
return a integer
"""
# generate random bits
p = getrandbits(length)
# apply a mask to set MSB and LSB to 1
p |= (1 << length - 1) | 1
return p
def generate_prime_number(length=1024):
""" Generate a prime
Args:
length -- int -- length of the prime to generate, in bits
return a prime
"""
p = 4
# keep generating while the primality test fail
while not is_prime(p, 128):
p = generate_prime_candidate(length)
return p
print(generate_prime_number(2048))
2048-Bit-Hauptbeispiel:
20948172001047358695787926888543743007121894047281908178348238095923963654562944507571635573909599330750753908673791853434139259413498165407600798568046507417382554220603146857898880242139067942230420218948994690003175384321032039386546524503466171675149316582304280062366747568422231701323955309340021375493571986613299600962261395718838935046659674806867659406735896778288176596852814927057082033184374768674561673765820787184619224336304267299492915726404455278589609784860501087313584245593398727512979161685117567902676990934207293923153569022277053938151385766936395777706415035184876785227611987928216386762133
Recommended Posts