> For the complete documentation index, see [llms.txt](https://security.andreasbreum.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://security.andreasbreum.com/cryptology/cryptohack/course-modular-arithmetic/general-mathematics.md).

# 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.

{% code overflow="wrap" lineNumbers="true" %}

```python
#!/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()
```

{% endcode %}

## Extended GCD

*"Let `a` and `b` be positive integers.*\
\
*The extended Euclidean algorithm is an efficient way to find integers `u,v` such that*\
\
\&#xNAN;*`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:

{% code overflow="wrap" lineNumbers="true" %}

```python
#!/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()
```

{% endcode %}

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

{% code overflow="wrap" lineNumbers="true" %}

```python
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()
```

{% endcode %}

## 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.

{% code lineNumbers="true" %}

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

{% endcode %}

## 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)
```

{% code lineNumbers="true" %}

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

{% endcode %}