Modular Arithmetic 2

1. intro

2. code 및 분석

2.1.  code

N/A

 

2.2. 분석

해석이다.

p가 소수일때 Fp를 {0,1,2,...,p-1} 의 유한체라고 하자.

이때 각 요소를 a라고 가정하면, 이 a의 덧셈역과 곱셈역이 존재하며 앞서 공부한 것과 같이

a + b = 0, ab = 1

는 항상 존재한다.

 

이제 p를 17이라고 가정하고

3^17 mod 17과 5^17 mod 17을 계산해보자.

아래와 같이 간단히 나머지만 출력하도록 코딩해보았고

a = b = 3
c = []
d = []

x = 18
n = 17

for i in range(1,x):
    c.append(str(a % n).rjust(2,' '))
    a = a * b

a = b = 5

for i in range(1,x):
    d.append(str(a % n).rjust(2,' '))
    a = a * b

print(c)
print(d)

출력 값은 아래와 같았다.

┌[wyv3rn🐲]-(/mnt/c/hacking)
└> python solve.py
[' 9', '10', '13', ' 5', '15', '11', '16', '14', ' 8', ' 7', ' 4', '12', ' 2', ' 6', ' 1', ' 3']
[' 8', ' 6', '13', '14', ' 2', '10', '16', '12', ' 9', '11', ' 4', ' 3', '15', ' 7', ' 1', ' 5']

공통점이 보이지 않는가?

16승의 값에서 모두 나머지가 1이다.

 

그럼 추측컨데,

7^16 mod 17

또한 16승의 값에서는 나머지가 1이 될 것 같은 느낌적인 느낌이다.

이를 계산해보면 아래와 같다.

┌[wyv3rn🐲]-(/mnt/c/hacking)
└> python solve.py
[' 7', '15', ' 3', ' 4', '11', ' 9', '12', '16', '10', ' 2', '14', '13', ' 6', ' 8', ' 5', ' 1']

 

즉,

a^(p - 1) mod p = 1

임을 알 수 있다.

 

이를 페르마의 소정리 라고 한단다.

 

3. exploit

마찬가지로 문제에서의 형식이

a^(p - 1) mod p

이므로

나머지는 1이 될 것이다.