General - Mathematics

Greatest Common Divisor

"The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b).

Now calculate gcd(a,b) for a = 66528, b = 52920"

Lets make a simple implementation of Euclid's algorithm. All though it is always easier to use the math.gcd() function.

#!/usr/bin/env python3
def gcd(a, b):
    while b != 0:
        t = b
        b = a % b
        a = t

    return a

def main():
    a = 66528
    b = 52920
    print(gcd(a, b))

if __name__ == "__main__":
    main()

Extended GCD

"Let a and b be positive integers. The extended Euclidean algorithm is an efficient way to find integers u,v such that a * u + b * v = gcd(a,b)

Using the two primes p = 26513, q = 32321, find the integers u,v such that p * u + q * v = gcd(p,q)"

We can make a simple implementation like this:

#!/usr/bin/env python3

def extended_euclidean_algorithm(p, q):
    if q == 0:
        return (p, 1, 0)
    else:
        gcd, u, v = extended_euclidean_algorithm(q, p % q)
        return (gcd, v, u - (p // q) * v)

def main():
    p = 26513
    q = 32321
    gcd, u, v = extended_euclidean_algorithm(p, q)
    print("gcd(", p, ",", q, ") = ", gcd)
    print("u = ", u)
    print("v = ", v)

if __name__ == "__main__":
    main()

Or if we want a all the imidate steps of the calculation, we can use print them as a table like this:

from tabulate import tabulate

def extended_euclidean_algorithm(a, b):
    rounds = []
    ri = [a, b]
    qi = []
    si = []
    ti = []
    i = 0

    # First round
    rounds.append(i)
    qi.append('-')
    si.append(1)
    ti.append(0)
    i += 1

    while True:
        # Second round
        if i == 1:
            rounds.append(i)
            qi.append(a//b)
            si.append(0)
            ti.append(1)
        else:
            rounds.append(i)
            ri.append(b)
            qi.append(a//b)
            si.append(si[i-2] - qi[i - 1] * si[i-1])
            ti.append(ti[i-2] - qi[i - 1] * ti[i-1])

        i += 1
        tmp = a
        a = b
        b = tmp % b
        if b == 0:
            break

    headers = ["i", "r_i", "q_i", "s_i", "t_i"]
    table_data = {"i": rounds, "r_i": ri, "q_i": qi, "s_i": si, "t_i": ti}
    return tabulate(table_data, headers=headers)


def main():
    a = 26513
    b = 32321

    print(f"The extended Euclidean algorithm table for a={a} and b={b} is:")
    print(extended_euclidean_algorithm(a, b))

if __name__ == "__main__":
    main()

Modular Arithmetic 1

"Calculate the following integers:

11 ≡ x mod 6

8146798528947 ≡ y mod 17

The solution is the smaller of the two integers."

The first one is easy. 11 mod 6 = 5

The second one is not something to be calculated without help. So lets write a script to help us.

#!/usr/bin/env python3
print(min(11 % 6, 8146798528947 % 17))

Modular Arithmetic 2

"A finite field Fp is the set of integers {0,1,...,p-1}, and under both addition and multiplication there is an inverse element b for every element a in the set, such that

a + b = 0 and a * b = 1.

Lets say we pick p = 17. Calculate 317 mod 17. Now do the same but with 517 mod 17. What would you expect to get for 716 mod 17? Try calculating that. This interesting fact is known as Fermat's little theorem. We'll be needing this (and its generalisations) when we look at RSA cryptography. Now take the prime p = 65537. Calculate 27324678765465536 mod 65537. Did you need a calculator?"

Fermat's little theorem states that if the exponent is p - 1 then x is 1.

So here we simply get 1.

Modular Inverting

"As we've seen, we can work within a finite field Fp, adding and multiplying elements, and always obtain another element of the field. For all elements g in the field, there exists a unique integer d such that g * d ≡ 1 mod p. This is the multiplicative inverse of g. Example: 7 * 8 = 56 ≡ 1 mod 11 What is the inverse element: 3 * d ≡ 1 mod 13?"

With Fermat's little theorem

We know that:
a^(p-1) ≡ 1 mod p
Therefore:
a^(p-1) * a^(-1) ≡ a^(-1) mod p
a^(p-2) * a * a^(-1) ≡ a^(-1) mod p
a^(p-2) ≡ a^(-1) mod p 
<=>
a^(p-2) % p = a^(-1)

#!/usr/bin/env python3
a = 3
p = 13
print(pow(a,p-2) % p)