라떼는말이야

※ 본 게시글은 모듈러 연산에 대해서 알고 있다는 전제하에 진행한다. 페르마의 작은 정리 (Fermat's little theorem) 페르마의 작은 정리에서 암호기술에 많이 응용되는 분야는 유한체에서의 역원 계산이다. 즉, 정수 a의 역원을 계산하는 방법으로 활용된다. 위 정의를 살짝 변형하면 다음과 같이 표현할 수 있다. 위 식을 잘 보면 a의 곱셈에 대한 역원을 생각해 볼 수 있다. 그 식은 다음과 같다. a의 역원은 a ^ (p-2) mod p이다. 이처럼 나타낼 수 있는 상황은 p가 소수일 경우에만 가능하다. 예제 1 위의 예제에서 3의 201 제곱에서 201은 10 x 20 +1로 표현할 수 있다. (3^10)^20 x 3에서 3^10은 mod11을 취했을 때 페르마의 작은 정리에 의해서 1이..