문제
우리는 유한체가 더하거나 곱해도 항상 Fp 유한체의 다른 요소임을 알 수 있었다.
유한체의 모든 요소 g는 g * d ≡ 1 (mod p)를 만족하는 d를 가진다.
이를 g의 곱셈역라고 한다.
예를 들어
7 * 8 = 56 ≡ 1 (mod 11)
이다.
그렇다면 3 * d ≡ 1 (mod 13)
을 만족하는 곱셈역는 무엇인가?
페르마의 소정리가 어떻게 곱셈역을 구하는데 도움이 되는지 생각해보자.
풀이
페르마의 소정리를 활용하여 풀이했습니다.
페르마의 소정리
a^(p-1) ≡ 1 (mod p)
이 문제에서는 3의 곱셈 역원을 구해야 합니다. 이제부터 3을 a라고 작성하겠습니다.
a의 역원은 a^(-1)입니다. a의 역원을 구하는 식을 전개해보면 아래와 같습니다.
a^(p-1) ≡ 1 (mod p)
a^(p-2) ≡ a^(-1) (mod p)
양쪽에 a^(-1)을 곱해주면 위 식과 같이 a^(p-2) % p = a^(-1) 이라는 식으로 역원을 구하는 식을 세울 수 있습니다.
1
2
3
4
5
6
>>> a = 3
>>> p = 13
>>> a**(p-2)%p
9
>>> pow(a, p-2, p)
9