3.2 Integer Arithmetic

Prime Factorization

Theorem

Every natural number can be uniquely expressed by multiplying prime numbers together.

$n=p_1\cdot p_2\cdot p_3\cdot ...\cdot p_k$

Integer factorization problem

It is difficult to factorize large integers, which means there is no efficient algorithm that solves this problem yet. However, computing the product of a given set of prime numbers is fast. Based on this observation, we can create a one-way function, which is an invertible function that is easy to compute in one direction but hard to compute in the other direction. This one-way function is a foundational element of the RSA encryption algorithm.

Definition | One-way function

A one-way function is a function that is easy to compute for every input but hard to invert given the image of a random input.

Extended Euclidean Algorithm

Extended euclidean algorithm is used to calculate the greatest common divisor (GCD) of integers. This algorithm computes GCD of two natural numbers $a$ and $b\in N$ and also finds two integers $s,t\in Z$, such that the following relationship holds: $gcd(a,b)=s\cdot a+t\cdot b$ The following pseudocode illustrates how the Extended Euclidean Algorithm works:

Pseudocode

Proof

The correctness of the Extended Euclidean Algorithm can be proven by using mathematical induction. Initially, we set the base conditions of the algorithm as follows:

$$\begin{array}{r}{s}_0=0,s_1=1\\ t_0=1,t_1=0\\ r_0=a,r_1=b\end{array}$$

Assume the statement we want to prove holds for $i>1$, which is: $a\cdot s_i+b\cdot t_i=r_i$ For the case of $i+1$, the following holds:

$$\begin{array}{rl}a\cdot s_{i+1}+b\cdot t_{i+1}& =a\cdot (s_{i-1}-s_i\cdot q_i)+b\cdot (t_{i-1}-t_i\cdot q_i)\\ & =(a\cdot s_{i-1}+b\cdot s_{i-1})+(a\cdot s_i+b\cdot t_i)\cdot q_i\\ & =r_{i-1}+r_i\cdot q_i\\ & =r_{i+1}\end{array}$$

Therefore, when $r_{i+1}=0$, $r_i$ is the gcd of $a$ and $b$.