[CryptoHack] Modular Arithmetic 2

 

개념 설명

---

모듈러 연산 2

우리는 지난 문제로부터 모듈러 p를 고를 것입니다. 그리고 p가 소수일때의 경우로 제한합니다.

정수 모듈러 p는 체(field) $F_p$를 정의합니다.

 

! 만약 모듈러가 소수가 아니라면, 정수 모듈러 n 집합은 환(ring)을 형성합니다.

 

유한체 $F_p$는 정수 $\{0,1..., p-1\}$의 집합이며, 덧셈과 곱셈 모두에서 $a+b=0$, $a\times b = 1$과 같이 집합의 모든 원소 a에 대한 역원이 존재합니다.

 

! 덧셈과 곱셈의 항등원(identity element)는 서로 다릅니다! 항등원은 연산자와 함께 동작할 때 아무것도 수행하지 않아야 합니다.

: $a+0 = a$

: $a \times 1 = a$

 

$p = 17$을 선택한다고 가정합시다. $3^{17} \bmod 17$을 계산하십시오. 그리고 이제 $5^{17} \bmod 17$을 계산하십시오.

$7^{16} \bmod 17$의 결과가 무엇일거라고 생각하나요? 계산해보십시오.

print(3**17 % 17) #3
print(5**17 % 17) #5
print(7**16 % 17) #1

 

이 흥미로운 사실은 페르마의 소정리(Fermat's little theorem)으로 알려져 있습니다. 우리는 RSA 암호화에 대해 생각할 때 페르마의 소정리(그리고 그것의 일반화)가 필요합니다.

 

예제

---

이제 소수 p = 65537을 취합니다. 그리고 $273246787654^{65536} \bmod 65537$을 계산합니다.

 

계산기가 필요했나요?