'Euclid 호제법'을 이용한 역원 구하기

'Euclid 호제법'은 두 수에 대한 최대공약수를 구하기 위해 사용하는 알고리즘 입니다.

 

해당 알고리즘을 이용하여 곱셈에 대한 역원 값을 구할 수 있습니다.

 

먼저 호제법을 시작할 때 두 수가 역원이 존재하는지를 확인해야 합니다.

 

'3 mod 26' 을 계산한다고 가정하여 진행 합니다.

 

[26 * x + 7 * y = 1]의 형태를 만들어야 합니다.

 

26 = 7 * 3 + 5

7 = 5 * 1 + 2

5 = 2 * 2 +1

 

- 두 수가 역원이 존재 하는지 점검합니다. 식의 마지막 부분이 1이 나올 때 까지 진행하고

  만약 마지막까지 진행 하였을때 1이 아닌 수가 나오면 역원이 존재하지 않는 수 입니다.

 

5 = 7 - 5 * 1 * 2 + 1             <<<<            7 - 5 * 1 = 2

 

- 두 수의 역원이 존재합니다. 처음 과정을 시작합니다. 2는 '7 - 5 * 1'의 형태로 바꿔줄 수 있으므로 바꿔줍니다. 'Euclid 호제법'을 이용한 곱셈에 대한 역원을 구하는 알고리즘의 핵심은 처음 mod 연산에 있던 두 수 [26 , 7]을 마지막 연산까지 남겨둬야 하는게 핵심입니다.

 

5 = (7 - 5) * 2 + 1

 

- '7 - 5'에 '2'를 곱하여 풀어줍니다.

 

5 = 7 * 2 - 5 * 2 + 1

 

5 * 3 = 7 * 2 + 1

 

- '5'가 두개이기 때문에 오른쪽 식의 '5'를 왼쪽으로 넘겨 '5'를 유지한 상태로 값을 늘려줍니다.

 

(26 - 7 * 3) * 3 = 7 * 2 + 1

 

- 지금부터 '5'를 없애고 '7'을 유지합니다. [5 = 26 - 7 * 3]으로 바꿔줄 수 있으니 바꿔서 대입해 줍니다.

 

26 * 3 - 7 * 9 = 7 * 2 + 1

 

- 괄호를 풀어줍니다.

 

26 * 3 - 7 * 9 - 7 * 2 = 1

 

- 오른쪽의 1을 제외한 나머지를 모두 옮겨줍니다.

 

26 * 3 + 7 * (-11) = 1

 

- [26 * x + 7 * y = 1]의 형태로 만들기의 마지막 부분입니다. '26 * 3'까지는 맞지만 그다음 '-'가 나와버리기 때문에 '+'의 형태로 바꿔주기 위한 작업을 해야합니다. '7'은 살려야하기 때문에 '+7'로 만들어 주고 뒤의 수를 '-11'로 만들어 줍니다.

 

7 * 15 = 1

 

- '-11'은 음수 이기때문에 '-11'의 역원을 구해줍니다. '26 - 11 = 15'입니다. '-11'의 역원은 '15'가 되고 '7 mod 26'의 곱셈에 대한 역원의 값은 '105'가 됩니다. [105 / 26 = 4]

 

'26 mod 7'의 역원은 [4] 입니다.