[정보보호] 페르마의 소정리 ( Fermat's Little Theorem )

[version 1]

조건: p가 소수이고 a가 하나의 정수로서 p는 a를 나누지 못한다. 

 

이 페르마의 리틀 정리는 지수계산을 쉽게 하는걸 도와준다. 

예를 들어 p=11, a=6으로 정하면 6^10 mod 11 = 1이다. 

증명

집합 A를 {1, 2, ..., p-1} 이라고 하자. 

집합 A에 a를 곱한 {a, 2a, ..., (p-1)a} 집합을 집합 B라고 하자. 

조건에 따라 p는 a를 나누지 못한다. 

따라서 집합 B에다가 mod p를 취해주면 집합 A와 같아진다. 

 

 

모듈러의 성질인, 

(A * B) mod C = (A mod C * B mod C) mod C임을 이용하자!

 

A, B에 있는 원소들을 각각 곱한다. 

1 * 2 * ... * (p-1) = (a mod p) * (2a mod p) * ... * (((p-1)*a) mod p)

양변에 mod p를 취해준다. 

 

(1 * 2 * ... * (p-1)) mod p = ((a mod p) * (2a mod p) * ... * (((p-1)*a) mod p)) mod p

 = (a* 2a * ... (p-1)*a) mod p

 = (a^(p-1) * 1 * 2 * ... * (p-1)) mod p

 

양변에서 1*2*...(p-1)을 지우면 1 = a^(p-1) mod p이다. 

[version 2]

곱셈역 구하기

첫번째 버전에다가 양변에 a^(-1) mod p 곱해주고, mod p 하면 된다. 

의의

이 정리는 꽤 쩌는 정리인데, 엄청 큰 수에다가 mod p를 했더니 1인걸 구할 수 있다! 엄청 큰 수를 계산하지 않아도 된다. 

또한 이 정리를 이용하면, 모듈로 값이 소수인 경우 곱에 관한 역원을 빠르게 구할수 있다. 

만약 p가 소수이고 a가 정수로서 p로 나누어지지 않는 수라면, a^(-1) mod p = a^(p-2) mod p 이다.

a^(-1) mod p는 p에 대한 a의 곱셈역이다. 곱셈역 포스팅을 참조해주세요.

이를 사용하면 extended euclidean algorithm을 안쓰고도 문제를 풀 수 있다.  mod p인 경우만 되긴 하지만,,,ㅠ

 

예시

Euler's Theorem #1

오일러의 첫번째 정리는, 페르마의 정리의 일반화된 버전이다. 오일러 정리에서 n이 소수인걸로 한정하면 페르마의 정리가 된다. 

a^(pi(n)) mod n = 1

 

pi(n) = n보다 작고 n과 서로소인 수의 집합의 개수

 

Euler's Theorem #2

If n = p * q and a < n, then a ^(k* phi(n) +1) mod n = a.