随机生成一个大质数

tryhi

1. import random
   
2. 
   
3. 
   
4. def fast_power(a, b, n):
   
5.     result = 1
   
6.     tmp = a
   
7.     while b > 0:
   
8.         if b & 1 == 1:
   
9.             result = (result * tmp) % n
   
10.         tmp = (tmp * tmp) % n
    
11.         b = b >> 1
    
12.     return result
    
13. 
    
14. 
    
15. def testMillerRabin(n, iter_num=8):
    
16.     """检验一个数是否为质数，参数1为整数，参数2为检验次数，一般不低于5"""
    
17.     if n == 2:
    
18.         return True
    
19.     if n & 1 == 0 or n < 2:
    
20.         return False
    
21.     # n-1 = (2^s)m
    
22.     m, s = n - 1, 0
    
23.     while m & 1 == 0:
    
24.         m = m >> 1
    
25.         s += 1
    
26.     # M-R test
    
27.     for _ in range(iter_num):
    
28.         b = fast_power(random.randint(2, n - 1), m, n)
    
29.         if b == 1 or b == n - 1:
    
30.             continue
    
31.         for __ in range(s - 1):
    
32.             # print(__, b)
    
33.             b = fast_power(b, 2, n)
    
34.             # print(__, b)
    
35.             if b == n - 1:
    
36.                 # print("xxx",b)
    
37.                 break
    
38.         else:
    
39.             return False
    
40.     return True
    
41. 
    
42. 
    
43. def pro(n, m):
    
44.     while 1:
    
45.         d = random.randint(n, m)
    
46.         if d % 2 == 0: d += 1
    
47.         if d in [2,3,5,7,11,13]:return d
    
48.         for i in range(50):  # 伪素数附近50个奇数都没有真素数的话，重新再产生一个伪素数
    
49.             d6 = d % 6
    
50.             if d6 != 1 and d6 != 5: continue  # 如果不是6的倍数加减1，则跳过
    
51.             u = testMillerRabin(d + 2 * i, 5)
    
52.             if u:
    
53.                 return d + 2 * i
    
54. 
    
55. 
    
56. 
    
57. 
    
58. ra = pro(2 ** 1023, 2 ** 1025)
    
59. print("生成的质数为：", ra)
    
60. print("对质数的检验结果为：", testMillerRabin(ra, 8))

复制代码

生成的质数为： 165642865589367291753144458650768183278332548522028487791596939640348023684042023851331565191716285510932368772690219194796681339904005320345063457632125052309558645336982330245838237490843678865014664211039823856305981897993435581155010814865055573859784255321889274048239167417659167583100404569601766950057
对质数的检验结果为： True