페르마 소인수분해법 문서 원본 보기

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

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

== 아이디어 ==
모든 홀수 자연수는 두 자연수의 제곱의 차로 나타낼 수 있다.

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

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

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

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

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

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

<math>f(402)=181, f(403)=986, f(404)=1793, f(405)=2602, f(406)=3413, f(407)=4226, f(408)=5041, \cdots</math>

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

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

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

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

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

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

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

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

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

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

<math>\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>R_m=\{0 \leq r < m: r \equiv x^2 \pmod m, x \in \mathbb{Z} \}</math>을 구한다. 그 다음 <math>N \equiv n \pmod m</math>인 나머지<math>n</math>을 집합의 각 원소에 더한 새 집합인 <math>R_{+n, m}=\{0 \leq r' < m: r' \equiv r+n \pmod m, r \in R_m \}</math>을 구한다. 그러면 <math>R_{x^2, m} = R_m \cap R_{+n, m}</math>이고, 이것이 <math>x^2 \equiv y^2+N \pmod m</math>을 만족할 <math>x^2</math>의 조건이다.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

* <math>\mod 5: 0, 1, 4</math> (3개)
* <math>\mod{20}: 0, 5, 1, 4, 9, 16</math> (6개)
* <math>\mod{100}: 0, 25, 20k+1, 20k+4, 20k+9, 20k+16</math> (18개)
* <math>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>N=161423 \equiv 3 \pmod{20}</math>이라는 사실에 착안해서 앞선 문단과 같은 방법으로 제한 조건을 찾는다. 그러면 <math>x^2 \equiv 4 \pmod{20}, y^2 \equiv 1 \pmod{20}</math>이 되어 <math>x \equiv \pm 2 \pmod{10}, y^2 \equiv \pm 1 \pmod{10}</math>이 된다.

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

이를테면 <math>N \equiv 29 \pmod{100}</math>이면 <math>N \equiv 9 \pmod{20}</math>이므로 <math>R_{(x^2, y^2), 20} = \{(9, 0), (5, 16) \}</math>이 나온다. 첫째 경우, <math>y^2 \equiv 0 \pmod{20} \Rightarrow y^2 \equiv 0 \pmod{100}</math>이다.<ref>어떤 자연수의 제곱이 20의 배수이면 그 수는 자동으로 100의 배수이기 때문</ref> 그러므로 <math>x^2 \equiv 29 \pmod{100} \Rightarrow x \equiv 23 \pmod{50}</math>임을 알 수 있다. 둘째 경우, <math>x^2 \equiv 5 \pmod{20} \Rightarrow x^2 \equiv 25 \pmod{100}</math>이며 여기서는 <math>x \equiv 5 \pmod{10}</math> 이 된다.

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

=== 그 밖의 소수 ===
법 7, 11, 13에 대한 이차잉여는 아래와 같다.
* <math>\mod 7: 0, 1, 2, 4</math> (4개)
* <math>\mod 11: 0, 1, 3, 4, 5, 9</math> (6개)
* <math>\mod 13: 0, 1, 3, 4, 9, 10, 12</math> (7개)

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

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

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

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

* <math>N \equiv 17 \pmod{64}</math>. 이차잉여의 교집합을 구하면 <math>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>x^2 \equiv 17 \text{ or } 33 \pmod{64}</math>이고, 법 64에 대한 제곱근을 구하면 <math>x \equiv \pm 9 \text{ or } \pm 15 \pmod{32}</math>임을 알 수 있다. (①)
* <math>N \equiv 67 \pmod{81}</math>. 마찬가지로 이차잉여의 교집합을 구한다. <math>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>x^2 \equiv 67 \pmod{81} \text{ or } x^2 \equiv 22 \pmod{27}</math>임을 알 수 있으며, 이를 풀면 <math>x \equiv \pm 38 \pmod{81} \text{ or } x \equiv \pm 7 \pmod{27}</math>이다. (②)
* <math>N \equiv 81 \pmod{100}</math>. 위에서 소개한 법 100 관련 문단을 이용하면 <math>x^2 \equiv 81 \text{ or } 25 \pmod{100}</math>임을 알 수 있고, 이는 곧 <math>R_{x, 50}=\{9, 41, 5, 15, 25, 35, 45 \}</math>임을 뜻한다. (③)

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

* 앞서 구한 <math>x \geq 1314</math>와 조건 ③을 먼저 조합하면 <math>x</math>의 후보는 다음과 같다.
* <math>x \in \{1315, 1325, 1335, 1341, 1345, 1355, 1359, 1365, 1375, 1385, 1391, 1395, 1405, 1409, \cdots \}</math>
* 그 다음 조건 ①을 불러와서 32로 나눈 나머지가 9, 15, 17 또는 23인 값들만을 추린다.
* <math>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인 경우만을 고른다.<ref>9로 나눈 나머지가 2 또는 7인 경우를 1차로 고르고 본래 조건을 2차로 적용해도 된다</ref>

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

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

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

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

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

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

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

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

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

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

* <math>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>x^2 \equiv 33 \text{ or } 1 \pmod{64} \Rightarrow x \equiv \pm 15 \text{ or } \pm 1 \pmod{32}</math>이다. 정리하면 <math>R_{x, 32} = \{1, 15, 17, 31 \}</math>
* <math>N \equiv 2 \pmod 3</math>이면 <math>x \equiv 0 \pmod 3</math>이라는 정보만을 알 수 있다.
* 위의 두 조건을 연립하면 <math>R_{x, 96} = \{3, 45, 51, 93 \}</math>임을 알 수 있다. (①)
* <math>N \equiv 13 \pmod{20} \Rightarrow x \equiv \pm 3 \pmod{10}</math>이다. 즉 일의 자리는 3 또는 7. (②)
* <math>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>R_{x, 7}=\{1, 3, 4, 6\}</math>을 도출한다. (③)
* <math>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>R_{x, 11}=\{1, 3, 4, 7, 8, 10\}</math>이다. (④)

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

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

== 같이 보기 ==
* [[오일러 소인수분해법]]

{{각주}}
{{수론 알고리즘}}
[[분류:알고리즘]]