[InformationSecurityTheory] 9. Mathmatics of Cryptography

Primes

Asymmetric-key cryptography uses primes extensively.

The topic of primes is a large part or any book on number theory. This section discusses only a few concepts and facts to pave the way for Chapter 10.

 

Definition

- A primeis divisible only by itself and 1.

Q. What is smallest prime?

A. The smallest prime is 2, which is divisible by 2 (itself) and 1.

 

 

Cardinality of Primes

 

 Infinite Number of Primes

There is an infinite number of primes.

- 증명 : 소수의 수가 유한으로 가정할때, 소수들의 집합 ${2,3,\cdots, p}$ 들을 다곱하여 $N$ 으로 표현.

$N+1>p$ 이므로 $N+1$ 은 소수가 아니고, 소수가 아닌수는 소수의 곱으로 나타낼 수 있다.

곱으로 나타낼 수 있는 소수중하나를 $q$ 라고할때, $N+1$은 $q$ 의 배수, $N$ 도 $q$의 배수이다.

$N+1-N$도 $q$ 의 배수이므로, 1 은 $q$ 의 배수이다.

따라서 $q=1$ 그런데 1은 소수가 아니고, 모순이발생한다.

즉 소수는 무한개이다.

 

- $\pi (x) $ : number of prime numbers $\leq n$

Checking for Primeness

- Given a number n, how can we determine if n is a prime?

- divisible by all primes less than $\sqrt{n}$

 

Euler's Phi-Funtion

- $\phi (n) $ : Euler's phi-function

- $\phi (n)$ : number of positive integers that are both smaller than n and relatively prime to n.

- $\phi (1) = 0$

- $\phi (p) = p-1$ if $p$ is a prime

- $\phi (mn) = \phi (m) \phi(n)$ if $m$ and $n$ are relatively prime

- $\phi(p^e) = p^e - p^{e-1}$ if $p$ is a prime ( $e$ : 양의 정수)

- $\phi (n)$ 계산

  > if $n$ can be factored as

     $n = p_1^e_1 \times p_2^e_2 \times \cdots \times p_k^e_k$ ( $p_1 < p_2 < \cdots < p_k $ : primes ) 

  > then we combine the third and the fourth rule to find

     $\phi(n) = \phi (p_1^e_1 \times \cdots \times p_k^e_k) = \phi (p_1^e_1) \times \cdots \times \phi (p_k^e_k)$

  > $\phi(n) = (p_1^e_1 - p_1^{e_1-1} \times \cdots \times (p_k^e_k - p_k^{e_k-1})$

Fermat's Little Theorem

- First Version

  > If p is a prime and a is an integer such that p does not divide a then $a^{p-1} \textrm{MOD} p = 1$

- 증명

- Second Version

  > If p is a prime and a is an integer then $a^p \textrm{MOd} p = a \textrm{MOD} p$

  > If p does not divide a : first version 의 양변에 a 를 곱하고 mod p 하면, second version

  > If p divides a : $a \textrm{mod} p = 0 = a^p \textrm{mod} p = 0$

 

- Multiplicative Inverses

  > If p is a prime and $ 0 < a < p$, then $a^{-1} \textrm{mod} p = a^{p-2} \textrm{mod} p$

  > 양변에 $a^{-1} \textrm{mod} p$ 곱하고 mod p 하면 성립.

 

 

Euler's Theorem

- If a and n are relatively prime, then, $a^{\phi (n)} \textrm{mod} n = 1$

- n 이 소수이면 : Fermat's Little Theorem

 

 

Mersenne Primes

- a Number in the form $M_p = 2^p - 1$, p prime, is called a Mersenne number and may or may not be a prime.