misc_crypto.py

import math, random, sys

def gcd(a, b, verbose=False):
    if a < b:
        a, b = b, a
    #initialization m -> μ, l = λ, m_1 means μ₋₁ (\u03BC\u208b\u2081)
    #i = 0
    r_1 = a
    r0 = b
    l_1 = 1
    m_1 = 0
    l0 = 0
    m0 = 1
    #computation
    while(a * l0 + b * m0 == r0):
        q = r_1 // r0
        if(verbose):
            print(f'r_1 = {r_1}, r0 = {r0}')
            print(f'l_1 = {l_1}, l0 = {l0}')
            print(f'm_1 = {m_1}, m0 = {m0}')
            print(f'q = {q}\n----------')
        l_tmp = l0
        l0 = l_1 - q * l0
        l_1 = l_tmp
        m_tmp = m0
        m0 = m_1 - q * m0
        m_1 = m_tmp
        r_tmp = r0
        r0 = r_1 % r0
        if r0 == 0:
            return (l_1, m_1, a * l_1 + b * m_1)
        r_1 = r_tmp

def bin_pow_n(a, z, n):
    res = 1
    while(z):
        if (z & 1):
            res = (res * a) % n
        a *= a % n
        z >>= 1
    return res

def miller_rabin_test(n, k = 7):
    """use Rabin-Miller algorithm to return True (n is probably prime)
    or False (n is definitely composite)"""
    if n < 6:  # assuming n >= 0 in all cases... shortcut small cases here
        return [False, False, True, True, False, True][n]
    elif n & 1 == 0:  # should be faster than n % 2
        return False
    else:
        s, d = 0, n - 1
        while d & 1 == 0:
            s, d = s + 1, d >> 1
              # Use random.randint(2, n-2) for very large numbers
        for a in random.sample(range(2, min(n - 2, 999999999999999999)), min(n - 4, k)):
            x = bin_pow_n(a, d, n)
            if x != 1 and x + 1 != n:
                for r in range(1, s):
                    x = bin_pow_n(x, 2, n)
                    if x == 1:
                        return False  # composite for sure
                    elif x == n - 1:
                        a = 0  # so we know loop didn't continue to end
                        break  # could be strong liar, try another a
                if a:
                    return False  # composite if we reached end of this loop
        return True  # probably prime if reached end of outer loop

def miller_rabin(n, k=7):

    # Implementation uses the Miller-Rabin Primality Test
    # The optimal number of rounds for this test is 40
    # See http://stackoverflow.com/questions/6325576/how-many-iterations-of-rabin-miller-should-i-use-for-cryptographic-safe-primes
    # for justification

    # If number is even, it's a composite number
    if n == 1:
        return False

    if n == 2 or n == 3:
        return True

    if n & 1 == 0:
        return False

    r, s = 0, n - 1
    while s & 1 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = bin_pow_n(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = bin_pow_n(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True