[정보보안] Primality Testing

1. Deterministic Algorithm

2. Probabilistic Algorithm

3. Recommended Primality Test

 

Probabilistic Algorithm은 prime은 무조건 prime으로 판단하는데 composite을 prime으로 판단할 수도 있다. 

이때 Fermat Test를 쓴다. 

 

 

1) Fermet Test

 

2) Square Root Test

 

3) Miller-Rabin Test

 

4) 현대의 방식