Modular Inverting

1. intro

2. code 및 분석

2.1.  code

N/A

 

2.2. 분석

역함수다!

 

우리는 유한체가 더하거나 곱해도 항상 Fp 유한체의 다른 요소임을 알 수 있었다.

유한체의 모든 요소 g는 g * d ≡ 1 (mod p)를 만족하는 d를 가진다.

이를 g의 곱셈역라고 한다.

예를 들어

7 * 8 = 56 ≡ 1 (mod 11)

이다.

그렇다면 3 * d ≡ 1 (mod 13)

을 만족하는 곱셈역는 무엇인가?

페르마의 소정리가 어떻게 곱셈역을 구하는데 도움이 되는지 생각해보자.

 

3. exploit

3.1. 페르마의 소정리 활용

페르마의 소정리는 앞서 공부한 것과 같이 p가 소수면

a^(p - 1) mod p = 1

이는 곧

a^(p - 1) mod p = 1 mod p

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

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

a^(p - 2) % p = a ^(-1)

이 되기에 a^(p - 2) % p가 곧 a의 역원이다.

이를 위에 적용하면

3^11 % 13

이 되고 a^(-1) = 9가 된다.

 

3.2. 베주 방정식 및 확장 유클리드 호제법 활용.

3 * d ≡ 1 (mod 13)를 베주 방정식 형태로 변형하면

3s + 13t = 1

가 된다.

앞서 작성한 코드에 넣어보면

┌──(kali㉿kali)-[~/Downloads]
└─$ python solve.py 
3
13
9 -2
-4 1

가 되며,

3 * 9 + 13 * (-2) = 1

또는

3 * (-4) + 13 * 1 = 1

이 된다.

그러므로 정답은 9 또는 -4인데, 일반적으로 양수를 사용하기에 9가 된다.