Greatest Common Divisor (GCD)

To find $GCD(a, b)$, one could use Euclidean Algorithm# using the theorem $GCD(a, b) = GCD(b, a \mod b); a > b$ to find the largest #Divisor that could divide both $a$ and $b$. If the GCD between the two numbers is 1, then we could say that $a$ and $b$ are relatively prime to each other and a multiplicative inverse# could be found. There are several rules to know:

$$ \begin{align} GCD(a, 0) &= a\\ GCD(a, 1) &= 1\\ \end{align} $$

Links to this page

TAC3121 Chapter 2: Finite Fields and Computational Number Theory

Greatest Common Divisor (GCD)
Rivest-Shamir-Adleman (RSA)

Select $e$ such that $1 < e < \phi (n)$ and $GCD(e, \phi (n)) = 1$ according to Greatest Common Divisor (GCD)#.

Note: $e$ is usually relatively small or $65537_{10}$ which is $10000000000000001_2$ for easy computation by Square-and-Multiply Algorithm#. That being said, $e$ can’t be either 1 or 2. The former means no encryption is done on $M$ as $M^e = M^1 = M$. The latter will not work due ($d$ not exist) to the nature of Greatest Common Divisor (GCD)# since $GCD(2, \phi(n))$ will always be 2 as $\phi(n) = (p - 1) (q - 1)$ where $p$ and $q$ are primes results in even number. However, if $e$ is too small, it is vulnerable to mathematical attack using Chinese Remainder Theorem (CRT)#.
Prime Factorisation

It is one of the method to determine the Greatest Common Divisor (GCD) by finding the product of common prime factors.
Modular Arithmetic

If $(a \cdot b) = (a \cdot c) \mod n$, then $b = c \mod n$ if and only if $a$ is relatively prime# to $n$.
Field

In Modular Arithmetic#, the find the multiplicative inverse of a number $a$ is by the equation, where $a$ is relatively prime to $n$:
Fermat’s Theorem

$GCD(a, p) = 1$ (Greatest Common Divisor (GCD)#).
Euler’s Theorem

$GCD(a, n) = 1$, meaning $a$ is relatively prime# to $n$
Euler Totient Function

Euler Totient Function $\phi(n)$ is defined as number of elements in reduced set of residues. Reduced set of residues is the numbers in a Set of residues $Z_n = \{0, 1, \ldots, n-1\}$ which are relatively prime# to $n$. There are several rules on computing Euler Totient Function:
Euclidean Algorithm

Euclidean Algorithm is used to find the #Greatest Common Divisor (GCD) between the number $a$ and $b$, typically denoted as $EUCLID(a, n)$. It uses the modulo nature# of two numbers, where $a = qn + b$, $b$ as the remainder of $a \mod n$, following the steps:

#math