from random import randint#使用randint需要加上这句
def growbin(w): #w是设定的二进制位数
list = [1]
for i in range(w-2):
list.append(randint(0,1))
list.append(1)
s2 = [str(_) for _ in list] #['1','1','1'] list
s3 = ''.join(s2) #111 str
b = 1
for i in range(len(s3)-1):
b <<= 1
b = b+int(s3[i+1])
d = int(b)
return d
#print(growbin(1024))
"""
def qmod(x,n,p): #x^n%p递归写法,1024位就溢出了
if n==0:
return 1
res = qmod((x*x)%p,n>>1,p)
if n&1 !=0:
res = (res*x)%p
return res
"""
def qmod(x,n,p):
res=1
while n!=0:
if n%2==0:
n=n//2
x=(x*x)%p
elif n%2!=0:
n=n-1
res=(res*x)%p
return res
def MillerRabin(p):
m = p-1
k = a = b = 0
a = randint(2,m)
while m//2*2 ==m:
tmp = qmod(a,m,p)
if tmp==1:
#k+=1
m//=2
else:
if tmp==p-1:
return 1
else:
return 0
b = qmod(a,m,p)
if b==1:
return 1
elif b==p-1:
return 1
else:
return 0
def testMillerRabin(p, k): # k为测试次数，p为待测奇数
while k > 0:
if not MillerRabin(p):
return False
k = k - 1
return True
def create(): # 产生素数
while 1:
d = growbin(1024)
for i in range(50): # 伪素数附近50个奇数都没有真素数的话，重新再产生一个伪素数
u = testMillerRabin(d+2*(i), 5)
if u:
b = d + 2*(i)
break
else:
continue
if u:
return b
else:
continue
for _ in range(10):#十轮测试，不一定就生成10个
print(create())
