[RSA] 페르마의 작은 정리와 오일러 정리

※ 본 게시글은 모듈러 연산에 대해서 알고 있다는 전제하에 진행한다.

페르마의 작은 정리 (Fermat's little theorem)

페르마의 작은 정리에서 암호기술에 많이 응용되는 분야는 유한체에서의 역원 계산이다. 즉, 정수 a의 역원을 계산하는 방법으로 활용된다.

위 정의를 살짝 변형하면 다음과 같이 표현할 수 있다.

페르마 소정리 변형

위 식을 잘 보면 a의 곱셈에 대한 역원을 생각해 볼 수 있다. 그 식은 다음과 같다. a의 역원은 a ^ (p-2) mod p이다.

페르마 소정리 역원

이처럼 나타낼 수 있는 상황은 p가 소수일 경우에만 가능하다.

 

예제 1

예제 1

위의 예제에서 3의 201 제곱에서 201은 10 x 20 +1로 표현할 수 있다.

(3^10)^20 x 3에서 3^10은 mod11을 취했을 때 페르마의 작은 정리에 의해서 1이 된다. ( ∵ 11은 소수 )

1에 20 제곱을 하고 3을 곱하면 3이 된다.

 

 

예제 2

p = 7이고, a = 2일 때,  a의 역원 계산

위의 역원 계산하는 식에 대입하여 나온 결과이다.

32 mod 7 = 4이므로 a의 역원은 4가 된다.

 

 

 

오일러의 정리 (Euler theorem)

오일러의 정리는 정수 모듈러에 대해 페르마의 소정리의 일반화. 즉, 모듈러가 소수일 필요가 없는 경우가 오일러의 정리이다.

오일러의 정리

 

은 오일러 파이 함수(Euler's phi function)이다.

정수 m보다 작거나 같은 집합에서 정수 m과 서로소인 정수의 수를 정의한다.

소수는 1과 자기 자신만을 공약수로 가진다. 즉, 오일러 파이 함수에 소수 p가 들어가면 p-1이 출력된다.

오일러의 정리 중 m에 소수인 p를 넣으면 페르마의 작은 정리와 완전히 동일한 식이 완성된다. 이로 인해 페르마의 소정리가 오일러 정리의 특별한 경우라는 것을 알 수 있다.

 

참고로 RSA의 phi(N)도 오일러 파이 함수를 뜻한다. phi(N)을 계산하는 방법은 (p-1) x (q-1)인데,

이는 phi(N) = phi(p) x phi(q) ( p, q는 소수 )로 정리되므로 phi(N)을 (p-1) x (q-1)로 정의하는 것이다.