페르마 소인수분해법

페르마 소인수분해법(Fermat's factorization method)은 홀수 자연수를 제곱의 차를 이용하여 소인수분해하는 알고리즘이다. 피에르 드 페르마가 고안한 방법이다.

이 알고리즘은 제곱합동식[math]\displaystyle{ x^2 \equiv y^2 \pmod N }[/math]을 이끌어내는 가장 기초적인 방법으로, 이를 응용 및 개량하여 연분수 소인수분해법, 이차 체, 수체 체 등 빠른 소인수분해법이 20세기 말에 개발되었다.

아이디어

모든 홀수 자연수는 두 자연수의 제곱의 차로 나타낼 수 있다.

[math]\displaystyle{ N=mn = \left(\frac{m+n}{2}\right)^2 - \left(\frac{m-n}{2}\right)^2 = x^2-y^2 (m\gt n, N: \text{odd}) }[/math]

홀수를 자연수의 곱으로 나타내면 두 수는 반드시 홀수여야만 한다. 그러므로 [math]\displaystyle{ x, y = \frac{m \pm n}{2} }[/math]는 필연적으로 자연수가 된다. 만약 주어진 자연수가 합성수이면, [math]\displaystyle{ N=x^2-y^2, x-y \geq 3 }[/math]인 순서쌍 [math]\displaystyle{ (x, y) }[/math]가 존재한다.

따라서 함수 [math]\displaystyle{ f(x)=x^2-N }[/math]을 지정해서 [math]\displaystyle{ f(x)=y^2 }[/math], 즉 함숫값이 제곱수가 되는 조건을 찾는다면 [math]\displaystyle{ N=x^2-y^2=(x+y)(x-y) }[/math] 꼴로 만들 수 있게 된다.

기본 접근

먼저 기준값[math]\displaystyle{ a=\lceil \sqrt{N} \rceil }[/math]을 찾는다. 만약 [math]\displaystyle{ \sqrt{N} }[/math]이 자연수로 딱 떨어진다면 소인수분해는 그 자리서 끝난다. 하지만 상당한 경우 주어진 수는 제곱수가 아니며 이 경우 아래 방법을 따른다.

[math]\displaystyle{ f(x)=x^2-N, x \in \{a, a+1, \cdots \} }[/math]의 값들을 차례대로 계산해서 제곱수를 발견할 때까지 반복한다.

이를테면 [math]\displaystyle{ N=161423 }[/math]을 소인수분해하려고 한다면, [math]\displaystyle{ \lceil \sqrt{N} \rceil=402 }[/math]이므로 [math]\displaystyle{ x \geq 402 }[/math]에 대해서 [math]\displaystyle{ f(x) = x^2-N }[/math]을 계산한다.

[math]\displaystyle{ f(402)=181, f(403)=986, f(404)=1793, f(405)=2602, f(406)=3413, f(407)=4226, f(408)=5041, \cdots }[/math]

위 함숫값들 중 제곱수가 되는 식은 [math]\displaystyle{ f(408)=408^2-N=71^2 }[/math]이다. 따라서 [math]\displaystyle{ N=408^2-71^2=(408-71)(408+71)=337\cdot 479 }[/math]임을 알 수 있다.

만약 나누어진 두 수 중 하나라도 여전히 합성수이면 소인수분해를 계속하지만, 둘 다 소수임이 판명나면 소인수분해는 끝난다. 위의 예시에서는 337, 479 모두 소수이다. 만약 직접 나누기를 시도했다면 337 이하의 소수들에 대해 노가다를 행했겠지만, 페르마 소인수분해법으로는 좀 더 수월한 방법으로 풀린다.

직접 나누기 방법은 어떤 합성수의 1보다 큰 가장 작은 약수를 우선순위로 찾는다. 반면 페르마 소인수분해법은 주어진 수의 제곱근([math]\displaystyle{ \sqrt{N} }[/math])에 가장 가까운 약수를 중심으로 찾으므로 시작점이 전혀 다르다.

참고로 이 알고리즘은 어떤 수가 크기가 비슷한 약수끼리 곱해져 있을 때 아주 쉽게 해를 찾을 수 있다. 가령 [math]\displaystyle{ 2021=2025-4=45^2-2^2=43 \cdot 47 }[/math]의 경우, 두 소인수의 차가 작아서 제곱의 차 모양을 한 방에 찾을 수 있다.

물론 [math]\displaystyle{ 2019 =338^2-335^2 =3\cdot 673 }[/math]과 같이 소인수의 크기가 극과 극으로 벌어져 있으면 직접 나누기보다도 속도가 느려진다. 그러므로 어떤 수를 소인수분해하려 할 때, 먼저 일정 기준 이하의 작은 소수들로 나누어지는지를 확인하고, 그 다음 이 방법을 적용하는 것이 좋다.

다른 접근

사실 여기서 [math]\displaystyle{ g(y)=y^2+N (y\gt 0) }[/math]을 지정해서 함숫값이 제곱수가 되는 경우를 찾아갈 수도 있다. 그렇게 해서 [math]\displaystyle{ g(y)=x^2 }[/math]인 [math]\displaystyle{ x }[/math]를 찾는다면 [math]\displaystyle{ N=x^2-y^2 }[/math]을 마찬가지로 유도할 수 있다.

하지만 만약 어떤 합성수의 약수가 해당 수의 제곱근에 가까울 경우 위의 기본 접근 방식이 더 빠르다. 이유는 [math]\displaystyle{ f(x)=x^2-N(\geq 0), g(y)(\geq N) }[/math]의 목표는 제곱수를 찾는 것인데, 일반적으로 임의의 자연수는 크기가가 작을 때 제곱수가 출몰할 확률이 크기 때문이다.

만약 위에서 든 예시를 이 변형된 함수로 제곱수 조건을 추적한다면, [math]\displaystyle{ g(1) \cdots g(71) }[/math]에 이르러서 해가 나온다. 이처럼 페르마 소인수분해법에서는 대개 큰 쪽인 [math]\displaystyle{ x }[/math]를 독립 변수로 잡는다.

경우의 수 추리기

그런데 위와 같이 제곱수 찾기를 시행할 때, 모든 [math]\displaystyle{ x\gt \sqrt{N} }[/math]에 대해 일일이 [math]\displaystyle{ f(x) }[/math]의 값을 조사할 필요는 없다. 이차잉여를 이용하면 제곱수가 불가능한 경우들을 미리 쳐낼 수 있다.

가령 4로 나눈 나머지를 생각할 때, 주어진 홀수 합성수의 경우 나머지가 1 또는 3 두 경우를 생각할 수 있다. 그리고 어떤 자연수의 제곱을 4로 나눈 나머지는 0 또는 1이다. 이를 토대로 아래와 같이 조건을 세울 수 있다.

[math]\displaystyle{ \begin{cases}N\equiv 1 \pmod 4 \Rightarrow x \equiv 1, y\equiv 0 \pmod 2 \\ N\equiv 3 \pmod 4 \Rightarrow x \equiv 0, y\equiv 1 \pmod 2 \end{cases} }[/math]

바로 위 문단에서 살핀 예시에서는 161423을 4로 나눈 나머지가 3이므로, (짝수)²-(홀수)² 형태만 알아보면 되므로 실제로 조사할 경우의 수는 절반으로 줄어든다.

이러한 경우의 수 추리기는 소수 또는 소수의 거듭제곱이 기준인 이차잉여를 이용하여 제한 조건을 여러 개 찾을 수 있다. 특히 거듭제곱의 차수가 올라가면 경우의 수를 더 줄일 수 있지만, 제한 조건의 식은 그만큼 복잡해진다.

먼저 이차잉여의 집합인 [math]\displaystyle{ R_m=\{0 \leq r \lt m: r \equiv x^2 \pmod m, x \in \mathbb{Z} \} }[/math]을 구한다. 그 다음 [math]\displaystyle{ N \equiv n \pmod m }[/math]인 나머지[math]\displaystyle{ n }[/math]을 집합의 각 원소에 더한 새 집합인 [math]\displaystyle{ R_{+n, m}=\{0 \leq r' \lt m: r' \equiv r+n \pmod m, r \in R_m \} }[/math]을 구한다. 그러면 [math]\displaystyle{ R_{x^2, m} = R_m \cap R_{+n, m} }[/math]이고, 이것이 [math]\displaystyle{ x^2 \equiv y^2+N \pmod m }[/math]을 만족할 [math]\displaystyle{ x^2 }[/math]의 조건이다.

2의 거듭제곱

2의 거듭제곱 중 제곱수(즉 4의 거듭제곱)를 법으로 하는 이차잉여는 아래 규칙을 따른다.

• [math]\displaystyle{ \mod 4: 0, 1 }[/math] (2개)
• [math]\displaystyle{ \mod{16}: 0, 4, 8k+1 }[/math] (4개)
• [math]\displaystyle{ \mod{64}: 0, 16, 32k+4, 8k+1 }[/math] (12개)
• 0이 아닌 이차잉여는 [math]\displaystyle{ 4^n(8k+1) }[/math] 형태로 써진다.
• [math]\displaystyle{ a^2 \equiv 4^n \pmod{8 \cdot 4^n} (n \geq 0) }[/math]이면 [math]\displaystyle{ a \equiv 2^n \pmod{2 \cdot 2^n} }[/math]이 성립한다.
• [math]\displaystyle{ 2 \nmid b }[/math]일 때, [math]\displaystyle{ a^2 \equiv b^2 \pmod{4 \cdot 4^n} }[/math]이면 [math]\displaystyle{ a \equiv \pm b \pmod{2\cdot 4^n} }[/math]이다.

법 64를 예로 들어보자. 모든 나머지 연산은 환 [math]\displaystyle{ \mathbb{Z}/64\mathbb{Z} }[/math]내에서 이루어진다.

• [math]\displaystyle{ N = 161423 \equiv 15 \pmod{64} }[/math]
• [math]\displaystyle{ x^2 \mod{64} }[/math]의 가능한 값은 [math]\displaystyle{ R_{64}=\{0, 16, 4, 36, 1, 9, 17, 25, 33, 41, 49, 57 \} }[/math]이다.
• [math]\displaystyle{ y^2+N \mod{64} }[/math]의 경우 위 집합의 각 원소에서 각각 15씩을 더하면 된다: [math]\displaystyle{ R_{+15, 64}=\{15, 31, 19, 51, 16, 24, 32, 40, 48, 56, 0, 8 \} }[/math]
• 그러므로 [math]\displaystyle{ x^2 \mod{64} }[/math]의 후보는 바로 위 두 집합의 교집합이다.
• [math]\displaystyle{ R_{x^2, 64}=R_{64} \cap R_{+15, 64} = \{0, 16 \} }[/math]
• 따라서 [math]\displaystyle{ x^2 \equiv 0 \text{ or } 16 \pmod{64} }[/math]과 같이 쓸 수 있다. 그리고 이를 다시 정리하면 [math]\displaystyle{ x \equiv 0 \text{ or } 4 \pmod 8 }[/math]이 된다. 좀 더 간단히 쓰면 [math]\displaystyle{ x \equiv 0 \pmod 4 }[/math]이다.

이 조건을 이끌어 냄으로써 경우의 수를 4분의 1로 추릴 수 있다. 실제로 [math]\displaystyle{ N \equiv 7 \pmod 8 }[/math]이면 [math]\displaystyle{ 4\mid x }[/math]라는 사실은 변하지 않는다. 추가로 [math]\displaystyle{ N \equiv 3 \pmod 8 }[/math]이면 [math]\displaystyle{ R_{x^2, 64}= \{4, 36 \} }[/math] 즉 [math]\displaystyle{ x^2 \equiv 4 \pmod{32} }[/math]이며, 이는 [math]\displaystyle{ x \equiv 2 \pmod 4 }[/math]와 동치이다.

[math]\displaystyle{ y }[/math]의 경우 경우의 수가 좀 더 많이 추려진다. 앞서 [math]\displaystyle{ R_{x^2, 64} = \{0, 16 \} }[/math]임을 이끌어냈을 때, 각 원소에서 15를 빼면 [math]\displaystyle{ R_{y^2, 64} = \{49, 1 \} }[/math]이 나온다. 법 64에 대한 제곱근을 구하면 [math]\displaystyle{ R_{y, 32} = \{\pm 7, \pm 1 \} }[/math] (32개 중 4개 꼴)이 나와서, 경우의 수는 8분의 1로 줄어든다.

참고로 [math]\displaystyle{ N \equiv 1 \pmod 4 }[/math]이면 위의 [math]\displaystyle{ x, y }[/math]의 홀짝이 서로 반대가 되며, 경우의 수도 반대로 각각 8분의 1, 4분의 1로 줄어든다.

3의 거듭제곱

3의 거듭제곱 중 제곱수(즉 9의 거듭제곱)를 법으로 하는 이차잉여는 아래 규칙을 따른다.

• [math]\displaystyle{ \mod 9: 0, 3k+1 }[/math] (4개)
• [math]\displaystyle{ \mod{81}: 0, 27k+9, 3k+1 }[/math] (31개)
• [math]\displaystyle{ \mod{729}: 0, 243k+81, 27k+9, 3k+1 }[/math] (274개)
• 0이 아닌 이차잉여는 [math]\displaystyle{ 9^n(3k+1) }[/math] 형태로 써진다.
• [math]\displaystyle{ a^2 \equiv 9^n \pmod{3 \cdot 9^n} (n \geq 0) }[/math]이면 [math]\displaystyle{ a \equiv \pm 3^n \pmod{3 \cdot 3^n} }[/math]이 성립한다.
• [math]\displaystyle{ 3 \nmid b }[/math]일 때, [math]\displaystyle{ a^2 \equiv b^2 \pmod{9^n} }[/math]이면 [math]\displaystyle{ a \equiv \pm b \pmod{9^n} }[/math]이다.

여기서는 [math]\displaystyle{ \mathbb{Z}/81\mathbb{Z} }[/math]을 기준으로 접근한다. 2의 거듭제곱 문단과 같은 방법을 쓴다.

• [math]\displaystyle{ N = 161423 \equiv 71 \pmod{81} }[/math]
• [math]\displaystyle{ x^2 \mod{81} }[/math]의 가능한 값은 [math]\displaystyle{ R_{81}=\{0, 9, 36, 63, 1, 4, 7, \cdots 79 \} }[/math]이다.
• [math]\displaystyle{ y^2+N \mod{81} }[/math]의 경우 위 집합의 각 원소에서 각각 71씩을 더하면 된다: [math]\displaystyle{ R_{+71, 81}=\{71, 80, 26, 53, 72, 75, 78, \cdots 69 \} }[/math]
• 마찬가지로 교집합을 셈해서 [math]\displaystyle{ x^2 \mod{81} }[/math]의 후보를 구한다.
• [math]\displaystyle{ R_{x^2, 81}=R_{81} \cap R_{+79, 81} = \{0, 9, 36, 63 \} }[/math]
• 따라서 [math]\displaystyle{ x^2 \equiv 0 \pmod{81} \text{ or } x^2 \equiv 9 \pmod{27} }[/math]과 같이 쓸 수 있다. 그리고 이를 다시 정리하면 [math]\displaystyle{ x \equiv 0 \pmod{9} \text{ or } x \equiv \pm 3 \pmod{9} }[/math]가 된다. 좀 더 간단히 쓰면 [math]\displaystyle{ x \equiv 0 \pmod 3 }[/math]이다.

위 예시와 같이 [math]\displaystyle{ N \equiv 2 \pmod 3 }[/math]이면 [math]\displaystyle{ 3\mid x }[/math]이라는 일정한 결론을 얻을 수 있다. 이는 법의 3의 차수를 올려서 조건을 살펴도 마찬가지다.

반면 [math]\displaystyle{ y }[/math]의 경우 경우의 수가 꽤 많이 줄어든다. [math]\displaystyle{ R_{x^2, 81} = \{0, 9, 36, 63 \} }[/math]의 각 원소에서 71을 빼면 [math]\displaystyle{ R_{y^2, 81} = \{10, 19, 46, 73 \} }[/math]을 도출한다. 이를 다시 쓰면 [math]\displaystyle{ y^2 \equiv 10 \pmod{81} \text{ or } y^2 \equiv 19 \pmod{27} }[/math]이며, 제곱근을 구하면 [math]\displaystyle{ y \equiv \pm 35 \pmod{81} \text{ or } y^2 \equiv \pm 10 \pmod{27} }[/math]이 나온다. 즉 경우의 수는 81개 중 8개 꼴로 추려진다.

참고로 [math]\displaystyle{ N \equiv 1 \pmod 3 }[/math]이면 위의 [math]\displaystyle{ x, y }[/math]의 3의 배수 여부는 서로 반대가 되며, 경우의 수도 반대로 각각 81분의 8, 3분의 1로 줄어든다.

5와 20, 100

소수가 커지면 조건식도 복잡해지며, 차수를 올림으로써 경우의 수를 줄이는 이점은 적어진다. 그래서 큰 소수의 이차잉여는 1차 내에서 조건식을 간단히 하는 편이 낫다. 물론 5의 경우 십진법의 특수성을 활용하여 법 20 또는 법 100을 편리하게 활용할 수 있다.

• [math]\displaystyle{ \mod 5: 0, 1, 4 }[/math] (3개)
• [math]\displaystyle{ \mod{20}: 0, 5, 1, 4, 9, 16 }[/math] (6개)
• [math]\displaystyle{ \mod{100}: 0, 25, 20k+1, 20k+4, 20k+9, 20k+16 }[/math] (18개)
• [math]\displaystyle{ a^2 \equiv 0 \text{ or } 25 \pmod{100} \Leftrightarrow a \equiv 0 \text{ or } 5 \pmod{10}, (5 \nmid b) a^2 \equiv b^2 \pmod{20} \Leftrightarrow a^2 \equiv \pm b \pmod{10} }[/math]

[math]\displaystyle{ N=161423 \equiv 3 \pmod{20} }[/math]이라는 사실에 착안해서 앞선 문단과 같은 방법으로 제한 조건을 찾는다. 그러면 [math]\displaystyle{ x^2 \equiv 4 \pmod{20}, y^2 \equiv 1 \pmod{20} }[/math]이 되어 [math]\displaystyle{ x \equiv \pm 2 \pmod{10}, y^2 \equiv \pm 1 \pmod{10} }[/math]이 된다.

이처럼 20으로 나눈 나머지를 활용하면 [math]\displaystyle{ x, y \mod{10} }[/math], 즉 일의 자리를 도출할 수 있다. 그런데 만약 [math]\displaystyle{ N \equiv \pm 1 \pmod 5 }[/math]이면, 경우의 수는 더 줄어든다.

이를테면 [math]\displaystyle{ N \equiv 29 \pmod{100} }[/math]이면 [math]\displaystyle{ N \equiv 9 \pmod{20} }[/math]이므로 [math]\displaystyle{ R_{(x^2, y^2), 20} = \{(9, 0), (5, 16) \} }[/math]이 나온다. 첫째 경우, [math]\displaystyle{ y^2 \equiv 0 \pmod{20} \Rightarrow y^2 \equiv 0 \pmod{100} }[/math]이다. 그러므로 [math]\displaystyle{ x^2 \equiv 29 \pmod{100} \Rightarrow x \equiv 23 \pmod{50} }[/math]임을 알 수 있다. 둘째 경우, [math]\displaystyle{ x^2 \equiv 5 \pmod{20} \Rightarrow x^2 \equiv 25 \pmod{100} }[/math]이며 여기서는 [math]\displaystyle{ x \equiv 5 \pmod{10} }[/math] 이 된다.

이렇게 놓고 보면 [math]\displaystyle{ R_{x, 50} = \{23, 27, 5, 15, 25, 35, 45 \} }[/math]가 되어 경우의 수는 50개 중 7개 꼴로 줄어든다. 한편 같은 방법으로 접근하면 [math]\displaystyle{ y^2 \equiv 0 \text{ or } 96 \pmod{100} }[/math]이며, [math]\displaystyle{ y \equiv 0 \pmod{10} \text{ or } y \equiv \pm 14 \pmod{50} }[/math]라는 사실을 알 수 있다.

그 밖의 소수

법 7, 11, 13에 대한 이차잉여는 아래와 같다.

• [math]\displaystyle{ \mod 7: 0, 1, 2, 4 }[/math] (4개)
• [math]\displaystyle{ \mod 11: 0, 1, 3, 4, 5, 9 }[/math] (6개)
• [math]\displaystyle{ \mod 13: 0, 1, 3, 4, 9, 10, 12 }[/math] (7개)

홀수 소수[math]\displaystyle{ p }[/math]를 법으로 하는 이차잉여로 경우의 수를 줄인다면 [math]\displaystyle{ x, y \mod p }[/math]의 가짓수는 [math]\displaystyle{ \frac{p \pm 1}{2} }[/math]개가 된다.

즉 제한 조건을 하나를 추가할 때마다 경우의 수는 대략 절반씩 줄어든다는 사실을 알 수 있다.

적용 예

앞서 아이디어 문단에서 든 예시에서 수 크기를 올려보자. [math]\displaystyle{ N=1724881 }[/math]을 제곱의 차를 이용하여 소인수분해를 한다. 이 예시는 위에서 소개한 이차잉여를 이용한 경우의 수 추리기가 진가를 발휘한다.

먼저 독립변수의 시작점은 [math]\displaystyle{ x \geq \lceil \sqrt{N} \rceil=1314 }[/math]부터 셈한다.

• [math]\displaystyle{ N \equiv 17 \pmod{64} }[/math]. 이차잉여의 교집합을 구하면 [math]\displaystyle{ R_{x^2, 64}=R_{64} \cap R_{+17, 64} = \{0, 16, 4, 36, 1, 9, 17, \cdots 57 \} \cap \{17, 33, 21, 53, 18, 26, 34, \cdots 10 \} = \{17, 33 \} }[/math]. 따라서 [math]\displaystyle{ x^2 \equiv 17 \text{ or } 33 \pmod{64} }[/math]이고, 법 64에 대한 제곱근을 구하면 [math]\displaystyle{ x \equiv \pm 9 \text{ or } \pm 15 \pmod{32} }[/math]임을 알 수 있다. (①)
• [math]\displaystyle{ N \equiv 67 \pmod{81} }[/math]. 마찬가지로 이차잉여의 교집합을 구한다. [math]\displaystyle{ R_{x^2, 81}=R_{81} \cap R_{+67, 81} = \{0, 9, 36, 63, 1, 4, 7, \cdots 79 \} \cap \{67, 76, 22, 49, 68, 71, 74, \cdots 65 \} = \{67, 76, 22, 49 \} }[/math] 그러므로 [math]\displaystyle{ x^2 \equiv 67 \pmod{81} \text{ or } x^2 \equiv 22 \pmod{27} }[/math]임을 알 수 있으며, 이를 풀면 [math]\displaystyle{ x \equiv \pm 38 \pmod{81} \text{ or } x \equiv \pm 7 \pmod{27} }[/math]이다. (②)
• [math]\displaystyle{ N \equiv 81 \pmod{100} }[/math]. 위에서 소개한 법 100 관련 문단을 이용하면 [math]\displaystyle{ x^2 \equiv 81 \text{ or } 25 \pmod{100} }[/math]임을 알 수 있고, 이는 곧 [math]\displaystyle{ R_{x, 50}=\{9, 41, 5, 15, 25, 35, 45 \} }[/math]임을 뜻한다. (③)

여기서 7, 11, 13으로 나눈 나머지 등으로 조건을 더 세울 수 있지만, 여기서는 위 세 조건으로 경우의 수를 걸러본다.

• 앞서 구한 [math]\displaystyle{ x \geq 1314 }[/math]와 조건 ③을 먼저 조합하면 [math]\displaystyle{ x }[/math]의 후보는 다음과 같다.
• [math]\displaystyle{ x \in \{1315, 1325, 1335, 1341, 1345, 1355, 1359, 1365, 1375, 1385, 1391, 1395, 1405, 1409, \cdots \} }[/math]
• 그 다음 조건 ①을 불러와서 32로 나눈 나머지가 9, 15, 17 또는 23인 값들만을 추린다.
• [math]\displaystyle{ x \in \{1335, 1359, 1385, 1391, 1425, 1455, 1495, 1545, 1559, 1585, 1591, 1609, 1615, 1641, 1655, \cdots \} }[/math]
• 그리고 조건 ②를 이용하여 81로 나눈 나머지가 38 또는 43이거나, 27로 나눈 나머지가 7 또는 20인 경우만을 고른다.

이렇게 목록을 추리다 보면 남는 후보 중 가장 작은 수는 [math]\displaystyle{ x=1559 }[/math]이다. 그런데 이 경우 [math]\displaystyle{ f(x) =x^2-N \Rightarrow f(1559) =1559^2-1724881 =705600 }[/math]인데 마침 이 값은 840의 제곱이다! [math]\displaystyle{ x }[/math]의 후보를 이차잉여로 거르고 나서 함숫값을 대입했더니 한 방에 해를 찾은 케이스다. 물론 자연수의 크기가 커지면 함숫값 대입을 여러 번 하는 경우도 많아진다.

이와 같이 해를 찾고 나면 [math]\displaystyle{ N=1559^2-840^2 \Rightarrow 1724881=719 \cdot 2399 }[/math]임을 알 수 있다. 719와 2399는 둘 다 소수이므로, 소인수분해는 여기서 종료한다.

소수 판정

이 소인수분해법을 변형하면 소수판정법으로 구성할 수 있다. 직접 나누기로 소인수분해 및 소수 판정이 모두 가능한 것과 같은 맥락이다.

어떤 홀수 자연수가 임의의 상수 [math]\displaystyle{ c }[/math]에 대해 [math]\displaystyle{ N=x^2-y^2, x-y \geq c }[/math]인 자연수 [math]\displaystyle{ x, y }[/math]의 해가 존재하지 않으면 [math]\displaystyle{ c \leq a \leq \sqrt{N}, a \mid N }[/math]인 약수 [math]\displaystyle{ a }[/math]도 존재하지 않는다.

홀수 자연수의 경우 1 다음으로 가장 작은 약수는 3 이상이다. 그러므로 [math]\displaystyle{ N=x^2-y^2, x-y \geq 3 }[/math]인 자연수 해가 존재하지 않으면 주어진 자연수는 홀수임을 알 수 있다. [math]\displaystyle{ x-y \geq 3 \Rightarrow x+y=\frac{N}{x-y} \leq \frac{N}{3} }[/math]이므로 [math]\displaystyle{ x }[/math]의 허용 범위는 [math]\displaystyle{ x \leq \frac{3}{2}+\frac{N}{6} \approx \frac{N}{6} }[/math]이다.

하지만 이렇게만 접근하면 효율은 떨어진다. [math]\displaystyle{ N }[/math]이 커질수록 허용 범위도 자연수 크기에 비례하여 넓어지기 때문. 가령 [math]\displaystyle{ N=250013 }[/math]이 소수인지 알아보려면 [math]\displaystyle{ 501 \leq x \lt 41671 }[/math] 범위에 대해 조사를 해야 한다. 그런데 주어진 홀수가 3, 5, 7, 11, 13의 배수가 아니라는 사실은 직접 나누기 내지는 배수판정법 등으로 쉽게 알 수 있을 것이다. 이에 착안해서 "가능한 가장 작은 약수는 그 다음 소수인 17"로 조건을 내린다면, [math]\displaystyle{ x-y \geq 17, x+y \leq \frac{N}{17} \Rightarrow x \leq \frac{17}{2}+\frac{N}{34} }[/math]가 되므로 허용 범위를 [math]\displaystyle{ 501 \leq x \lt 7362 }[/math]과 같이 사전에 좁힐 수 있다. 그리고 직접 나누는 소수의 범위를 넓히면 [math]\displaystyle{ x }[/math]의 범위는 더 좁아진다.

다시 말해 3 이상의 적절한 상수 [math]\displaystyle{ c }[/math]를 잡아서, [math]\displaystyle{ 3 \leq a \leq c }[/math] 구간에서는 직접 나누기로, [math]\displaystyle{ c \lt a \leq \sqrt{N} }[/math] 구간에서는 제곱의 차로 약수의 존재성을 조사하면 된다. 그리고 두 구간에서 모두 약수를 찾을 수 없게 되면, 주어진 자연수는 소수임이 판명난다.

소수 판정 예시

위의 예시([math]\displaystyle{ N=250013 }[/math])에서 [math]\displaystyle{ c=47 }[/math]로 잡고 이 상수 이하의 소수로는 나누어떨어지지 않음을 알고 있다고 간주하자. 그러면 47 다음 소수는 53이므로 [math]\displaystyle{ 53 \leq a \leq \sqrt{N} \lt 501 }[/math]범위에서 약수가 전무함을 보이면 된다.

[math]\displaystyle{ x-y \geq 53, x+y \leq \frac{N}{53} \Rightarrow x \lt 2386 }[/math]이므로, [math]\displaystyle{ x \in \{501, 502, \cdots 2385 \} }[/math](ⓐ) 내에서 후보들을 소거해 나간다.

다음 단계는 이차잉여를 이용한 제한 조건 찾기이다. 앞서 '적용 예' 문단과 같은 방법으로 경우의 수를 추린다.

• [math]\displaystyle{ N \equiv 29 \pmod{64}, R_{64}=\{0, 16, 4, 36, 1, 9, 17, \cdots 57 \}, R_{+29, 64}=\{29, 45, 33, 1, 30, 38, 46, \cdots 22 \}, R_{x^2, 64} = \{33, 1 \} }[/math]이므로 [math]\displaystyle{ x^2 \equiv 33 \text{ or } 1 \pmod{64} \Rightarrow x \equiv \pm 15 \text{ or } \pm 1 \pmod{32} }[/math]이다. 정리하면 [math]\displaystyle{ R_{x, 32} = \{1, 15, 17, 31 \} }[/math]
• [math]\displaystyle{ N \equiv 2 \pmod 3 }[/math]이면 [math]\displaystyle{ x \equiv 0 \pmod 3 }[/math]이라는 정보만을 알 수 있다.
• 위의 두 조건을 연립하면 [math]\displaystyle{ R_{x, 96} = \{3, 45, 51, 93 \} }[/math]임을 알 수 있다. (①)
• [math]\displaystyle{ N \equiv 13 \pmod{20} \Rightarrow x \equiv \pm 3 \pmod{10} }[/math]이다. 즉 일의 자리는 3 또는 7. (②)
• [math]\displaystyle{ N \equiv 1 \pmod 7, R_7=\{0, 1, 2, 4\}, R_{+1, 7}= \{1, 2, 3, 5\}, R_{x^2, 7}=\{1, 2 \} }[/math]이므로 위와 같은 방법으로 [math]\displaystyle{ R_{x, 7}=\{1, 3, 4, 6\} }[/math]을 도출한다. (③)
• [math]\displaystyle{ N \equiv 5 \pmod{11}, R_{11}=\{0, 1, 3, 4, 5, 9\}, R_{+5, 11}= \{5, 6, 8, 9, 10, 1\}, R_{x^2, 11}=\{1, 5, 9 \} }[/math]이므로 [math]\displaystyle{ R_{x, 11}=\{1, 3, 4, 7, 8, 10\} }[/math]이다. (④)

이제 위 조건들을 토대로 ⓐ에서 구한 x의 후보를 소거해간다.

• 조건 ①을 만족하는 값들을 남기면 [math]\displaystyle{ x \in \{525, 531, 573, 579, 621, \cdots 2355 \} }[/math]
• 조건 ②를 만족하는 값들은 [math]\displaystyle{ x \in \{573, 627, 717, 723, 813, \cdots 2307 \} }[/math]
• 다음으로 조건 ③, ④를 이어서 적용하면 남는 후보는 [math]\displaystyle{ x \in \{573, 813, 1053, 1107, 1203, 1917, 2157, 2307 \} }[/math]이다.
• 남는 후보들을 [math]\displaystyle{ f(x)=x^2-N }[/math]에 대입하여 제곱수 여부를 알아본다. 하지만 확인해보면 어떤 함숫값도 제곱수가 아님을 알 수 있다.

이로써 [math]\displaystyle{ N=(x-y)(x+y), 53 \leq x-y \leq 501 }[/math]을 만족하는 자연수 [math]\displaystyle{ x, y }[/math]는 존재하지 않음을 알 수 있다. 그리고 맨 처음에 둔 전제인 '3 이상 47 이하의 약수는 없다'는 조건까지 포함하면, 250013은 소수임을 알 수 있다.

같이 보기

• 오일러 소인수분해법