论坛 › Python交流 › 随机生成一个大质数

tryhi 发表于 2021-10-6 17:48:25

随机生成一个大质数

import random


def fast_power(a, b, n):
    result = 1
    tmp = a
    while b > 0:
      if b & 1 == 1:
            result = (result * tmp) % n
      tmp = (tmp * tmp) % n
      b = b >> 1
    return result


def testMillerRabin(n, iter_num=8):
    """检验一个数是否为质数，参数1为整数，参数2为检验次数，一般不低于5"""
    if n == 2:
      return True
    if n & 1 == 0 or n < 2:
      return False
    # n-1 = (2^s)m
    m, s = n - 1, 0
    while m & 1 == 0:
      m = m >> 1
      s += 1
    # M-R test
    for _ in range(iter_num):
      b = fast_power(random.randint(2, n - 1), m, n)
      if b == 1 or b == n - 1:
            continue
      for __ in range(s - 1):
            # print(__, b)
            b = fast_power(b, 2, n)
            # print(__, b)
            if b == n - 1:
                # print("xxx",b)
                break
      else:
            return False
    return True


def pro(n, m):
    while 1:
      d = random.randint(n, m)
      if d % 2 == 0: d += 1
      if d in :return d
      for i in range(50):# 伪素数附近50个奇数都没有真素数的话，重新再产生一个伪素数
            d6 = d % 6
            if d6 != 1 and d6 != 5: continue# 如果不是6的倍数加减1，则跳过
            u = testMillerRabin(d + 2 * i, 5)
            if u:
                return d + 2 * i




ra = pro(2 ** 1023, 2 ** 1025)
print("生成的质数为：", ra)
print("对质数的检验结果为：", testMillerRabin(ra, 8))


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

查看完整版本: 随机生成一个大质数