[InformationSecurityTheory] 10. Primality Testing

Deterministic Algorithms

 

Probabilistic algorithms 

- Fermat Test

  > If n is a prime then $a^{n-1} \textrm{mod} n=1$ for all $1 < a < n$.

  > If $a^{n-1} \textrm{mod} n \neq 1$ for some a, $1<a<n$ then n is a composite

  > If $a^{n-1} \textrm{mod} n =1$ for some a, $1<a<n$, then n may be a prime.

  > "composite" 라 판단하면 확실히 composite

  > "Prime" 라 판단하면, n 은 아마도 prime.

 

Square Root Test

- $\sqrt{1} \textrm{mod} n = {x|x^2 \textrm{mod} n = 1, 1 \leq n \leq n -1 }$

- If n is a prime, then $\sqrt{1} \textrm{mod} n = {1, n-1}$

- If $\sqrt{1} \textrm{mod} n \neq {1, n-1}$, then n is composite.

 

Miller-Rabin Test

- Fermat test + Square Root test

 

- Choose an integer a such that $2 \leq a \leq n-2$ and calculatest $a^{n-1} \textrm{mod} n$.

- $n-1 = m \times 2^k$ 형태로 쓴다.

- $a^{n-1} \textrm{mod} n$ 계산을 한꺼번에 하지않고 여러 스텝으로 하면서, 과정에서 prime / composite 를 판단한다.

- 확률적으로 a 가 prime 이고 제대로 판단할 확률은 1/4 이고 a 를 랜덤하게 10 번 선택해서 확률을 더 올린다.

 

 

Recommended Primality Test

 

Factorization

- Any positive integer n can be written uniquely in a prime factorization form. $p_1, p_2, \cdots, p_k$ are primes, are $e_1, e_2, \cdots ,e_k$ are positive integers.

$ n = p_1^e_1 \times p_2^e_2 \times \cdots \times p_k^e_k$

 

 

Exponentiation and Logarithm

Fast Exponentiation

- given $a,x,n$

- calcuate $y = a^x \textrm{mod} n$