generate radndom prime number in python code example
Example: how to generate prime numbers in a bit range python
def miller_rabin(n, k):
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for _ in range(k):
a = random.randrange(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
"""
a function that uses miller rabin's primality test to genarate a prime number in a certain number of bits length
in other words you give it a number of bits and you will get a prime number with that number of bits
"""
def genprimeBits(k):
x = ""
k = int(k)
for y in range(k):
x = x + "1"
y = "1"
for z in range(k-1):
y = y + "0"
x = int(x,2)
y = int(y,2)
p = 0
while True:
p = random.randrange(y,x)
if miller_rabin(p,40):
break
return p