Fermat's little theorem

Fermat’s Little Theorem

For prime $p$, and $a \not\equiv 0 \pmod{p}$

$a^{p-1} \equiv 1 \pmod{p}$

 

즉, a를 p-1번 곱한 값은 p로 나누면 항상 나머지가 1이다.

 

[예시]

p = 5, a = 2

$2^4 = 16$

16 mod 5 = 1

 

p가 소수면 1부터 p-1까지의 수는 모두 p와 서로소이다.

그래서 곱해도 0이 되지 않는다.

 

집합 {1, 2, ..., p-1}을 생각한다.

각 원소에 a를 곱하고 p로 나눈 나머지를 보면 값이 사라지지 않는다.

순서만 바뀐 같은 집합이 된다.

그래서 전체 곱도 같아야 한다.

 

1 x 2 x ... x (p-1)

= $a^{p-1}$ x (1 x 2 x ... x (p-1)) (mod p)

 

공통 부분을 약분하면

$a^{p-1} \equiv 1 \pmod{p}$

 

다음 식도 많이 사용된다.

$a^p \equiv a \pmod{p}$

 

 

Euler 정리와의 관계

Fermat's little theorem은 Euler's Theorem의 특수한 경우이다.

 

Euler's Theorem

$a^{φ(n)} \equiv \pmod{n}$

 

p가 소수면, $ φ(n) = p-1 $

→ Fermat's little theorem이 된다.

 

 

암호학에서의 실제 사용

RSA에서 모듈러 거듭제곱을 빠르게 계산할 때 사용된다.

큰 수를 직접 계산하지 않고 mod 연산으로 줄인다.

 

$7^{100} \pmod{13}$

 

13은 prime

$7^{12} \equiv 1 \pmod{13}$

 

→ $7^{100} = (7^{12})^{8} \times 7^4 = 7^4 \pmod{13} $

 

 

소수 판별에의 활용

Fermat's little theorem은 소수 판별 테스트의 기초다.

 

임의의 a에 대해서

$a^{p-1} \pmod{p} \neq 1$이면 p는 합성수이다.

 

단, 항상 소수라고 보장되지는 않는다.

 

 

Carmichael Number

합성수인데도 Fermat's little theorem을 만족하는 수가 있다.

 

예) 561 = 3 x 11 x 17

 

이런 수 때문에 실제 암호 시스템에서는 Miller-Rabim 테스트를 사용한다.