[Cryptohack] RSA starter 1 write up

~ RSA의 모든 연산 모든 문제에는 모듈러 지수화 ( 나머지 연산 ) 을 사용하게 된다 ~

 

mod는 나머지 연산자이다 

10 mod 3이면 10%3과 같은건데 쉽게 다시 말하면 

나머지가 3보다 작을때까지 계속 뺀다고 생각하면 된다 

10 - 3 = 7

7 - 3 = 4

4 - 3 = 1

결국 답은 1이되는것이다 

실제로, 10%3 하면 몫은 3 나머지는 1이 나오게 된다 

% = mod 

 

다시 문제로 돌아와서 

101¹⁷ mod 22663 을 구하라고 했는데 거듭제곱과 나머지연산자를 한번에 수행해주는 

pow 함수를 사용할 것이다 

result = pow(2, 3)  # 2의 3승인 8을 계산합니다.
print(result)       # 출력: 8

result_with_modulus = pow(2, 3, 5)  # (2의 3승)을 5로 나눈 나머지를 계산합니다. 결과는 3입니다.
print(result_with_modulus)          # 출력: 3

pow ( base,exponent,modulus ) 

이런 식의 함수인데 설명하자면 이렇다 

 

base: 거듭 제곱할 밑 숫자
exponent: 밑을 거듭 제곱할 지수
modulus (선택적): 제공된 경우, 결과는 해당 모듈러 값으로 나눈 나머지로 계산

 

문제를 말로 풀면

1. 101의 17을 제곱하고 그 값을  22663을 22663보다 작은 값이 나올때까지 빼준다

2. 101의 17을 제곱하고 그 값을 22663으로 나머지연산을해 나머지를 구한다 

같은 말이다 

 

print(pow(101,17,22663))

코드로 표현해보면 이런식으로 나오게된다 

 = 19906