Arbitrary bit number prime creation Python code RSA


from random import randrange, getrandbits
def is_prime(n, k=128):
    """ Test if a number is prime
        Args:
            n -- int -- the number to test
            k -- int -- the number of tests to do
        return True if n is prime
    """
    # Test if n is not even.
    # But care, 2 is prime !
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    # find r and s
    s = 0
    r = n - 1
    while r & 1 == 0:
        s += 1
        r //= 2
    # do k tests
    for _ in range(k):
        a = randrange(2, n - 1)
        x = pow(a, r, n)
        if x != 1 and x != n - 1:
            j = 1
            while j < s and x != n - 1:
                x = pow(x, 2, n)
                if x == 1:
                    return False
                j += 1
            if x != n - 1:
                return False
    return True
def generate_prime_candidate(length):
    """ Generate an odd integer randomly
        Args:
            length -- int -- the length of the number to generate, in bits
        return a integer
    """
    # generate random bits
    p = getrandbits(length)
    # apply a mask to set MSB and LSB to 1
    p |= (1 << length - 1) | 1
    return p
def generate_prime_number(length=1024):
    """ Generate a prime
        Args:
            length -- int -- length of the prime to generate, in          bits
        return a prime
    """
    p = 4
    # keep generating while the primality test fail
    while not is_prime(p, 128):
        p = generate_prime_candidate(length)
    return p
print(generate_prime_number(2048))

2048-bit prime number example:

20948172001047358695787926888543743007121894047281908178348238095923963654562944507571635573909599330750753908673791853434139259413498165407600798568046507417382554220603146857898880242139067942230420218948994690003175384321032039386546524503466171675149316582304280062366747568422231701323955309340021375493571986613299600962261395718838935046659674806867659406735896778288176596852814927057082033184374768674561673765820787184619224336304267299492915726404455278589609784860501087313584245593398727512979161685117567902676990934207293923153569022277053938151385766936395777706415035184876785227611987928216386762133

Recommended Posts

Arbitrary bit number prime creation Python code RSA
Prime number 2 in Python
Infinite prime number generator in Python3
Prime number generation program by Python
Prime number
Project Euler # 7 "1000 1st prime number" in Python
Prime number enumeration and primality test in Python
Judge whether it is a prime number [Python]
python character code
[Python] Algorithm-aware code
PYTHON2.7 64bit version
I made a prime number generation program in Python
Try touching the micro: bit with VS Code + Python
I made a prime number generation program in Python 2