블록체인의 기초(1)

페르마의 소정리

암호학의 기초수학원리로 사용되며 소수 p에서의 유한체 (F_p) 안에서 성립하는 성질.

정의

• p : Prime Number (소수) => 1보다 큰 자연수중 1과 자신만을 약수로 갖는 수
• n 과 P는 서로소 관계 (둘 사이에 1이외의 공약수가 없는 상태)

유한체의 곱셈

정수 0 ~ p 까지의 원소로 구성되는 유한체(Field) 를 아래와 같이 표현하고 유한체에서 곱셈군의 성질을 확인해 보자.

소수19 유한체의 서로소집합 {1, 3, 7, 13, 18} 을 소수 19의 유한체 원소들과 (0~18) 각각 순서대로 곱한뒤 19로 나눈 나머지 (Modulo)를 표현하면

prime = 19 # 소수 19
for k in [1, 3, 7, 13, 18]: # 소수 19의 유한체
    print(sorted([k*i % prime for i in range(prime)]))

# 결과
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

결과는 19의 유한체 (0~19) 와 동일한 집합이 된다.
모듈로연산(%) 으로 인해 소수 P의 유한체 F_p 안에서 0과 서로소 원소 k를 곱한 값은 항상 F_p 안에 머무른다는 것을 확인했다.

페르마의 소정리 증명

이제 유한체 F₁₉ 에 페르마의 소정리식을 적용해 확인해보자.

for i in [7, 11, 17, 31]: # 소수 p의 집합
    print([ (j**(i-1)) % i for j in range (1, i)])  # 소수 P 의 

# 결과
# [1, 1, 1, 1, 1, 1]
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

0과 소수p자신을 제외한 유한체 F_p = {1,2,…,p-1}의 모든 원소 n에대해

모든 결과값은 1이된다.
0은 어떤 수를 곱해도 1이 나오지 않기 때문에(역원이 없다) 제외하고 p가 소수이기 때문에 0을 제외한 유한체의 원소 {1, 2, 3, …p-1} 가 모두 곱셈 역원을 가지는 유한체 구조가 성립한다. (당연히 p mod p는 0 이기 때문에 p자신또한 제외된다)

• 역원 : 곱셈연산으로 1, 덧셈연산으로 0이 나오는 수

또 다른 방법으로 증명해보자.
아래식의 좌항은 유한체 F_p이고 우항은 0이 아닌 임의의 원소n을 유한체의 모든 원소에 각각 곱한 집합이다.

이 식을 다시 정리하면

다시 축약하면 ( n! 은 팩토리얼(factorial)로 5! = 5⋅4⋅3⋅2⋅1 = 120와 같이 계산 )

최종적으로 (p-1)! 로 약분하면 페르마의 소정리 식이 된다.

페르마의 소정리를 이용한 나눗셈의 연산

나눗셈은 곱셈의 역연산으로 아래와 같이 치환할 수 있다.

페르마의 소정리에 따르면

따라서 아래와 같이 치환할 수 있다.

최종적으로 b의 역원과 b^{(p - 2)} 는 같다.

모듈러연산에서 곱셈의 역원을 구하는 위의 방법을 사용하면 음의 지수를 양의 지수로 바꿀 수 있다.

페르마의 소정리를 이용해 나눗셈을 곱셈연산으로 치환해보자.