GCD(Greatest Common Divisor)

Euclidean Algorithm is based on the principle that the greatest common divisor of two numbers doesn't change if the larger number is replaced by its difference with the smaller one.

def gcd(a, b):
    while b != 0:
        t = b
        b = a % b
        a = t
    return a

Community Implementation (gmpy2) 

from gmpy2 import *

print(gcd(15, 35))
5

Extended GCD

The Extended Euclidean Algorithm provide a efficient way to find integers \(u, v\) such that:

\begin{align} a \cdot u + b \cdot v &= gcd(a, b) \\ &= gcd(b, a \bmod b) \tag{Euclidean algorithm apply} \\ &= b \cdot u_1 + (a \bmod b) \cdot v_1 \tag{Extened GCD apply} \\ &= b \cdot u_1 + (a - (a \div b) \cdot b) \cdot v_1 \\ &= a \cdot v_1 + b \cdot (u_1 - (a \div b) \cdot v_1) \\ &\Downarrow \\ u &= v_1 \\ v &= u_1 - (a \div b) \cdot v_1 \\ \end{align} 
def ext_gcd(a, b):
  if b == 0:
    return 1, 0
  else:
    u, v = ext_gcd(b, a % b)
    return v, u - (a // b) * v

Community Implementation (gmpy2) 

from gmpy2 import *

print(gcdext(15, 35))           # return a 3-element tuple (g, u, v) such that g = gcd(a, b) = a*u + b*v
(mpz(5), mpz(-2), mpz(1))

Fermat's Little Theorem

Fermat's Little Theore states that if \(p\) is a prime that:

\begin{align} & \forall a \in \mathbb{Z}, (a^p - a) \bmod p = 0 \\ & \text{if } a \text{ is not divisible by } p, \text{then:} \\ & a^{p-1} \equiv 1 \pmod p \\ & \text{else: } \\ & a^{p-1} \equiv 0 \pmod p \end{align}

TODO Application

Quadratic Residue

The definition like this: let's work on modulo \(p\), and we take two integers \(x, a\), which satisfied that \(x^2 \equiv a \pmod p\) then \(x\) is square root of \(a\)

Discriminant

we can see that \(\forall a \in \mathbb{F}_p\) not every element has a square root. So we say that an integer \(a\) is Quadratic Residue if there exist an \(x\) that \(x^2 \equiv a \pmod p\) else not.

Property

  • Quadratic Residue * Quadratic Residue = Quadratic Residue
  • Quadratic Residue * Quadratic Non-Residue = Quadratic Non-Residue
  • Quadratic Non-Residue * Quadratic Non-Residue = Quadratic Residue

Just replace Quadratic Residue as 1 and Quadratic Non-Residue as -1 will help remember it.

Legendre Symbol

Legendre_symbol gives a efficient way to determine whether an integer is Quadratic Residue modulo an odd prime \(p\)

\(a/p = a^{p-1/2} \bmod p\) :

  • 1 if \(a\) is Quadratic Residue and \(a \not\equiv 0 \pmod p\)
  • -1 if \(a\) is Quadratic Non-Residue
  • 0 if \(a \equiv 0 \pmod p\)

Tonelli-Shanks Algorithm

As now, we have efficient way to determine whether an integer is Quadratic Residue or not. but how we find the square root fastly too? for All prime divisor, the answer is Tonelli-Shanks algorithm.

sympy implementation 

from sympy import sqrt_mod

a = 11
p = 43
print(sqrt_mod(a, p))
21

Chinese Remainder Theorem

The CRT provide an unique solution to a set of linear congruence's equations if their moduli are coprime.

This means that given a set of arbitrary integers \(a_i\) and pairwise coprime integers \(n_i\) with following equations hold:

\begin{align} x &\equiv a_1 \pmod {n_1} \\ x &\equiv a_2 \pmod {n_2} \\ x &\equiv a_3 \pmod {n_3} \\ &\dots \\ x &\equiv a_n \pmod {n_n} \\ \end{align} 
from functools import reduce

moduli = [5, 11, 17]
remainder = [2, 3, 5]

N = reduce(lambda x, y: x * y, moduli)

m = [N // m for m in moduli]
# when exponent is negative, this function use extend Euclidean algorithm to find the inverse modular
mi = [pow(m[i], -1, moduli[i]) for i in range(len(moduli))]

x = sum(a * mi[i] * m[i] for i, a in enumerate(remainder))

print(f"solution: {x % N}")