도입
암호학에서 Number Theory는 암호학에서 가장 중요하게 다루는 2가지 이론 중 하나이다. Number Theory; 즉, 정수론은 아주 오래전부터 연구되어온 복잡한 학문이기 때문에 복잡한 정수론 문제를 사용하여 암호를 푸는 문제를 어렵게 설계하기 위하여 사용된다.
그렇다면 정수론은 무엇을 다루는 학문인가?
A Sample Problem 1
Problem 1. Find Solution $2^a + 3^b = n!$, in Nonnegative Integers $a, b$ and $n$
$n$ 이 0인 경우부터 순서대로 계산해 나가면 답을 구할 수 있다.
- $n=0$ : 좌변도 0이 되어야하지만, 어떤 수의 제곱수는 절대 0이 될 수 없기 떄문에 불가능하다.
- $n=1$ : 좌변도 1이 되어야하지만, 어떤 수의 제곱수의 최소값은 제곱일 때 "1"이기 때문에 좌변의 최소값인 1+1은 1이 아니므로 불가능하다.
여기까지는 명확하게 답을 알 수 있었지만 만약 $n$이 더 큰 범위에서는 어떻게 문제를 해결해야할까?
우리는 여기서 좌변과 우변이 같은 수라면, 좌변과 우변을 각각 어떤 수 $X$로 나눈 "나머지"역시 동일해야한다는 아이디어를 적용한다.
좌변을 이루는 항은 2의 제곱수와 3의 제곱수이므로 다음의 2가지 경우로 나누어 생각해보자.
$n\ge2$
양변을 2로 나누어보자.
- $2^a$는 2의 제곱수이므로 2로 나눈 나머지가 0이다.
- $3^b$는 3의 제곱수이므로 2로 나눈 나머지는 1이다.
즉, 좌변을 2로 나누면 항상 $0+1=1$의 나머지를 가진다. 그러나 우변은 $n$의 팩토리얼인데, n이 2보다 같거나 커지면 항상 우변은 $2$가 곱해진 값이 결과로 나오기 떄문에 나눈 나머지가 0이 된다.
따라서 $n\ge2, a> 0, b> 0$이면 더이상 답이 존재하지 않는다.
그럼 더 나아가 이제 $a, b$의 범위를 확장해보자.
만약 $a=0$ 이고 $b=0$라면 $1+1 = 2$가 되므로 답이 존재한다. $(a=0, b=0, n=2)$
만약 $b=0$이면 좌변을 2로 나누었을 때 $0+1=1$이 되므로 답이 존재하지 않는다.
따라서 $n\ge2, a> 0, b\ge 0$이면 더이상 답이 존재하지 않는다.
만약 $a=0$이면 좌변을 2로 나누었을 때 $1+1=2 = 0$이 되므로 좌변과 우변의 나머지가 동일한 경우가 존재할 수 있다. 그럼 이제 $3$으로 나눈 나머지를 생각해보자.
$n\ge 3$
양변을 3으로 나누어보자. 이떄 $a=0$인 경우를 가정하므로 3으로 나눈 나머지는 1이다.
- 1을 3으로 나눈 나머지는 1이다.
- $3^b$는 3의 제곱수이므로 3으로 나눈 나머지는 0이다.
즉, 좌변을 3으로 나누면 항상 $1+0=1$의 나머지를 가진다. 그러나 우변은 3의 배수이므로 나눈 나머지가 0이 된다. 따라서 양변의 나머지가 다르므로 답이 존재하지 않는다.
따라서 $n\ge3, a\ge 0, b\ge 0$이면 더이상 답이 존재하지 않는다.
즉, 이 문제의 유일한 해답은 다음과 같다.
$$ a=0, b=0, n=2$$
A Sample Problem 2 : 3의 배수, 9의 배수 판정법
$376548$은 다음과 같이 정리할 수 있다.
$$= 3\times 10^5 + 7\times10^4 + 6\times10^3 + 5\times10^2 + 4\times10 + 8$$
어떤 수 $X$를 10번 곱한 수는 X를 9번 곱한 수 + X로 나타낼 수 있다. 따라서 다음과 같이 표현된다.
$$ = 3+7+6+5+4+8 + 99999 \times 3 + 9999 \times 7 + … $$
따라서 $999$.. 로 표현된 항들은 3으로/9로 나눈 나머지가 0이므로 무시되기 때문에 기존 숫자의 합으로 표현된 항인 $3+7+6+5+4+8$만 남는다.
그래서 자릿수의 합이 3의 배수인지/9의 배수인지에 따라서 그 숫자가 3의 배수인지, 9의 배수인지를 쉽게 알 수 있는 것이다!