大素数的生成算法验证
郝伟 2022/06/24

• 简介
• 输出
• 源代码

简介

生成1024位的大素数的生成算法。

输出

…
1024 bit prime is:
161597389454119846040844295762016440901152205096496815100669539003114282897647310227855945279208505572483227781657391334098337320607749325433257709656139061098173376537708296916107118054400614170759263672363294529891003645964237374886942278876428155573516373357615930942317993234662741215675736259443494894731

源代码

# How to generate Large Prime numbers for RSA Algorithm
# https://www.geeksforgeeks.org/how-to-generate-large-prime-numbers-for-rsa-algorithm/

# Large Prime Generation for RSA, Pre generated primes according to
# [1] Miller Rabin Primlity Test, https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/
# 

import random, math

def isPrime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

small_primes = []
for i in range(2, 1024):
    if isPrime(i):
        small_primes.append(i)

# why 349? because 349*3=1047 > 1024
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 
                61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 
                131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
                197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
                271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349]

def is_prime(n):
    for divisor in small_primes:
        if pc % divisor == 0 and divisor**2 <= pc:
            return False
        else: return True

def getLowLevelPrime(n):
    '''Generate a prime candidate divisible by first primes'''
    while True:
        # Obtain a random number and test divisibility by pre-generated primes
        pc = random.randrange(2 ** (n - 1) + 1, 2 ** n - 1)
        for divisor in small_primes:
            if pc % divisor == 0 and divisor**2 <= pc:
                break
        else: return pc

def isMillerRabinPassed(mrc):
    '''Run 20 iterations of Rabin Miller Primality test'''
    maxDivisionsByTwo = 0
    ec = mrc-1
    while ec % 2 == 0:
        ec >>= 1
        maxDivisionsByTwo += 1
    assert(2**maxDivisionsByTwo * ec == mrc-1)
    def trialComposite(round_tester):
        if pow(round_tester, ec, mrc) == 1:
            return False
        for i in range(maxDivisionsByTwo):
            if pow(round_tester, 2**i * ec, mrc) == mrc-1:
                return False
        return True
    # Set number of trials here
    numberOfRabinTrials = 100
    for i in range(numberOfRabinTrials):
        round_tester = random.randrange(2, mrc)
        if trialComposite(round_tester):
            return False
    return True

while True:
    print('.', end='')
    n = 1024
    prime_candidate = getLowLevelPrime(n)
    if isMillerRabinPassed(prime_candidate):
        print(f"\n{n} bit prime is: \n{prime_candidate}")
        break