소개

현대 암호학 수업을 들어보셨나요? 마지막으로 확인했을 때 가장 많이 물어보는 질문은 다음과 같았습니다:

(사진 번역: 소인수분해에 대해서 더 알고싶어요! 수학 연습도 재미있었고 그 응용 부분도 재미있었습니다. 감사합니다!) 이 수업에서는 수학 자물쇠(mathematical locks)를 구성할 때 소인수분해가 근본적인 역할을 했던 것을 살펴봤습니다. 수학 자물쇠(또는 일방향 함수)는 한쪽으로는 수행하기 쉽지만 역방향으로는 힘든 과정이 필요합니다.

예를 들어, P1 = 709 와P2 = 733와 같은 임의의 큰 소수 두 개를를 골라서

N = P1 * P2의 값을 얻기 위해 두 수를 곱해봅시다.

N = 709 * 733 = 519697     (이건 계산하기 쉽습니다)

하나의 큰 수 (519697) 와 이 수의 소인수를 구했습니다 (709 * 733)

여기서 소인수분해 를 하는 부분 없이 다음과 같이 주어졌다고 생각해 봅시다:

519697 = ? * ?     (이건 계산하기 어렵습니다)

여기서 소수 곱을 알아내라고 한다면 어디서부터 시작해야 할까요? 걱정하지 마세요, 누구한테나 어려운 문제이니까요! 해답을 얻기 위해서는 수많은 시행착오가 필요합니다. 곱셈은 빠르지만(쉽고) 인수분해는 느립니다(어렵습니다). 이런 간단한 사실이 RSA 암호화 방식의 기초가 됩니다.

여기를 클릭해서 움직이는 그래프를 통해 그 차이점을 확인하세요.

더 깊이 공부하기 전에 첫 번째 단계를 조금 더 들여다보기 위해 스스로에게 중요한 질문을 해봅시다. "임의의 큰 소수 두 개를 고르라"고 했을 때 어떻게 쉽게 소수를 고를 수 있을까요? 이 문제는 쉬운가요?

잠시 생각해 보면, 이 단계에서 적어도 무작위로 생성된 숫자가 (예를 들어,  99194853094755497) 소수이거나 합성수라는 사실을 확인해야 한다는 것을 금방 알아챌 수 있습니다. 계산기에 이를 알려주는 버튼이 있나요?

저에게는 보이지 않는데요…. 왜일까요?

그 이유를 알아내기 위해 이 응용문제부터 풀어 봅시다...