Introduction to Number Theory

tags: math, cryptography

Prime Numbers

prime numbers are essential in cryptography, they are the essence of cryptography due to their properties. Any number can be written as multiplication of prime numbers. $12=2^2\ast 3$ We create a large prime number by multiplying the prime factors together, leading to a large prime number that is hard to be factorized by the crypt-analyst.

GCD of two numbers can be calculated from their prime number decomposition.

Example

And it is clear why it works, 300 has 2 and 3 its factors the same is 18, so the greatest factors they share are $2\ast 3$

Fermat’s Theorem

$a^{p-1}\equiv 1(modp)$ Where $a$ is a positive integer relatively prime to $p$ and $p$ is a prime number.

NOTE: multiplying a relative prime number to p by another relative prime number to p will also give you a number relative prime to p.

Proof of Fermat

Alt. Fermat’s Theorem

If p is prime and a is any positive integer $a^p=a(modp)$ If a is relatively prime to p then proving this is easy, just follow Fermat’s and multiply the last step by a. If a a positive integer then both terms $modp$ equals 0, there is no other answer.

Euler’s Formula and Euler’s Totient function

Euler’s Totient function is defined as $\varphi (n)$ and it gives the number of numbers that are less than $n$ and relatively prime to it, if $n$ is prime then totient function will give $n-1$ and it is clear why.

Now if $p$ and $q$ are two prime numbers and $n=p\ast q$ then $\varphi (n)=\varphi (p)\ast \varphi (q)$. Proof: $q-1$ and $p-1$ are the number of number in the sets of number that are not relatively prime to n. (it looks like p and q are the private keys)

Euler Theorem states that: $a^{\varphi (n)}=1(modn)$

NOTE: a must be relatively prime to n

The proof for it is nearly the same as Fermat’s proof: And S is a permutation of R, since a is relatively prime to n X is relatively prime to n so their multiplication will always give a number relatively prime to n.

Alt Euler’s Theorem

$a^{\varphi (n)+1}=a(modn)$ To prove it, just the same as we said with Alt. Fermat Theorem

Chinese Remainder Theorem

The theorem says that we re-construct integers in a range from their residues modulo the factorization of a number, let’s say we have the number 10, we can factorize it to two relatively prime number 2 and 5, i.e $10=2\ast 5$. Now we have a range of numbers from 0 to 9: $Z_{10}=\{0,1,2,3,4,5,6,7,8,9\}$ Let’s say we want to do operations on 9, we can transform 9 to a set of residues: $(9mod2,9mod5)=(1,4)$ We can do any operations on these numbers and reconstruct them back by the following formula: $A=(\sum a_i{c}_i)modM$ where $A$ is the integer 9 and $a_i$ are the residues $c_i$ is the selector, $c_i=M_i\ast M_i^{-1}$ without doing the mod and $M_i=M/m_i$, proving the reconstruction: $A=(1\ast 5\ast 5+4\ast 2\ast 8)mod10=9$ $c_i$ is called the selector because if I want to get $a_i$, $c_i$ will select and cancel the other because the other can be divisible by $m_1$, also look here. The benefit of CRT is that it allows the simplification of large number operation.

Discrete Exponent and Logarithm

If we have an integer $a$ and the exponentiation of a by numbers from 1 to $\varphi (n)$ the answer will be a repeating sequence of numbers, if the period of that sequence is $\varphi (n)$ then $a$ is a primitive root of $n$.

According to the book the first exponent that gets to one is the period. We can deduce that: $a^{m}modn=a^{m+\varphi (n)}modn$

The discrete logarithm is hard to calculate, because there is no other way than brute-forcing.

Discrete logarithm only exist if $a$ is a primitive root because if the period is smaller than $\varphi (n)$ then some solutions wont exist.