| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
암호학이 대두되면서 큰 소수를 구할 필요가 생겼고, 그와 동시에 큰 합성수의 소인수분해에 대한 연구도 진행되었다.2. 알고리즘
2.1. 기초
주어진 숫자 n의 소인수를 구한다고 할 경우 아래와 같은 순서로 진행하면 된다.* 1. i=2로 시작하여 i++ 하면서 n%i == 0 인지 체크한다.
* 2. n%i==0이 성립하는 경우 i를 소인수로 등록한 후 n은 i로 나눈 값을 저장하고 i는 i++ 하지 않고 i부터 다시 시작하도록 한다.
* 3. n이 1이 될 때까지 위 과정을 반복한다.
* 2. n%i==0이 성립하는 경우 i를 소인수로 등록한 후 n은 i로 나눈 값을 저장하고 i는 i++ 하지 않고 i부터 다시 시작하도록 한다.
* 3. n이 1이 될 때까지 위 과정을 반복한다.
이 알고리즘으로 소인수를 구하면 천억이 넘는 숫자도 소인수가 순식간에 구해진다.
간단하게 파이썬으로 코딩 해보면 다음과 같다.
#!syntax python
# -*- coding: utf-8 -*-
import os
import sys
def find_prime(input_num):
if input_num <= 2:
return [input_num,]
for idx in range(2,input_num):
if input_num % idx == 0:
ret_list = []
val_a = find_prime(idx)
val_b = find_prime(int(input_num/idx))
ret_list = val_a + val_b
return ret_list
return [input_num,]
def main():
try:
input_num = int(sys.argv[1])
except:
print("usage: python main.py <number>")
print(" ex> python main.py 12345")
quit()
prime_list = find_prime(input_num)
check_num = 1
for prime_at in prime_list:
check_num *= prime_at
print("[%s] input_num=%d, check_num=%d" % (input_num == check_num, input_num, check_num))
print("%s" % prime_list)
main()
다만 위의 프로그램은 프로그래밍을 익히는 용도로는 유용할수 있으나, 실제 소인수분해 용으로 쓰기에는 적합하지 않다. 실제로 컴퓨터로 다루는 수는 1000억은 '겨우'라는 소리가 나올만큼 큰 수를 다룰 필요가 있기 때문이다.
가장 쉬운 방법은 다른 프로그램을 이용해서 미리 소수 테이블을 작성해 두고, 이를 활용하는 것이다. 예를 들어 216 보다 작은 소수는 6542개인데, 이를 미리 배열에 저장해 두면, 42억 (=232) 보다 작은 수는 겨우 6542번 나누어 보기만 하면 소수인지 판정하거나, 1개 이상의 소인수를 구할 수 있다. 232보다 작은 소수는 모두 약 2억개(203,280,221개)인데, 이를 미리 구해서 적절한 DB에 저장해 두면 약 1844경 (= 264 = 18,446,744,073,709,551,616)보다 작은 수의 소인수 분해를 쉽게 할 수 있다.
20자리 정도 되는 이정도 수면 큰 수라고 생각할 수 있지만, RSA 암호화같은 암호학에서 기본 수백자리 수를 다뤄야 한다. RSA 넘버를 보면 가장 작은 것이 100자리 부터 시작하는데, 그마저 250자리 수 까지는 모두 소인수분해되었다. 가장 큰 RSA-2048은 무려 617자리 수이다. 수의 단위 중 이름이 붙은 최고 단위인 구골이 101자리 수라는 것을 생각해보면, RSA 암호화에서 다루는 수는 사람에게는 어마어마하게 큰 수이다.
밑과 지수를 구하는 기본적인 파이썬 함수는 여기서 설명되어 있다.
2.2. 페르마 소인수분해법
곱셈 공식을 응용한 소인수분해법.[math(N=x^2-y^2)]을 만족하는 두 자연수 [math(x)], [math(y)]를 찾을 수 있다면, [math(x+y)]와 [math(x-y)] 모두 [math(N)]의 약수가 된다. 식을 조금 변형하여, [math(N+y^2=x^2)]이 제곱수가 되도록 하는 자연수 [math(y)]를 찾는 문제가 된다.
특성상 [math(\sqrt{N})]에 가까운 약수를 찾을 때 유용하며, [math(N)]이 5 이상의 홀수일 때만 적용 가능하다. 또한, [math(N)]이 소수일 경우 성능이 매우 떨어지기 때문에, [math(y)]의 값이 어느 정도 커지면 위의 기초 알고리즘을 대신 사용해야 한다.
한두 개의 소인수만 발견할 수 있기 때문에, 소인수분해를 마치려면 아래 알고리즘을 재귀적으로 수행해야 한다.
유사 코드로 표현하면 다음과 같다. 변수 [math(x_2)], [math(y_2)]는 곱셈 연산을 한 번으로 줄이기 위해 도입한 변수이다.
1. 홀수 [math(N)]을 입력받는다.
2. [math(x=\left\lceil\sqrt{n}\right\rceil)], [math(y=0)]
3. [math(x_2=x^2)], [math(y_2=0)]
4. [math(N+y_2)]의 값을 [math(x_2)]와 비교하여, 같으면 5로, 좌변이 크면 6로, 우변이 크면 8로.
5. [math(x-y)]를 출력하고 종료한다. 이는 [math(N)]의 비자명한 약수이다.
6. [math(x_2\leftarrow x_2+2x+1)], [math(x\leftarrow x+1)]
7. 5로
8. [math(y_2\leftarrow y_2+2y+1)], [math(y\leftarrow y+1)]
9. [math(y\geq N/6)]일 때, [math(N)]은 소수이다. 알고리즘을 종료한다.
10. 5로
[math(N)]을 4로 나눈 나머지가 1일 때, [math(x)]는 홀수, [math(y)]는 짝수이고, [math(N)]을 4로 나눈 나머지가 3일 때, [math(x)]는 짝수, [math(y)]는 홀수이다. 이를 이용하여 실행 시간을 절반으로 줄일 수 있다. 기초 알고리즘과 결합하면, 다음과 같다.
1. 홀수 [math(N)]을 입력받는다.
2. [math(x=\left\lceil\sqrt{n}\right\rceil)], [math(y=y_2=0)]
3. [math(N\equiv3\ (\mathrm{mod}\ 4))]일 때, [math(y=y_2=1)]
4. [math(x+y)]가 짝수일 때, [math(x\leftarrow x+1)]
5. [math(x_2=x^2)]
6. [math(N+y_2)]의 값을 [math(x_2)]와 비교하여, 같으면 7로, 좌변이 크면 8로, 우변이 크면 10으로.
7. [math(x-y)]를 출력하고 종료한다. 이는 [math(N)]의 비자명한 약수이다.
8. [math(x_2\leftarrow x_2+4x+4)], [math(x\leftarrow x+2)]
9. 7로
10. [math(y_2\leftarrow y_2+4y+4)], [math(y\leftarrow y+2)]
11. [math(2y<x)]일 때, 8로. 아래 코드는 [math(\sqrt{N}/3)] 이하의 소인수를 찾기 위한 기초 소인수분해 알고리즘이다.
12. [math(i=3)], [math(i_2=27)]
13. [math(N)]이 [math(i)]의 배수일 때, [math(i)]를 출력하고 종료한다.
14. [math(i_2\leftarrow i_2+12i+12)], [math(i\leftarrow i+2)]
15. [math(i_2>N)]일 때, [math(N)]은 소수이다. 알고리즘을 종료한다.
16. 13으로
2.3. 오일러 소인수분해법
2.4. 폴라드 로 알고리즘
1975년 존 폴라드가 발표한 소인수분해 알고리즘. 확률적 알고리즘으로, [math(N)]이 합성수더라도 소인수분해에 가끔 실패할 수 있다. 다만 시간복잡도는 확실히 줄어든다.다음과 같은 함수를 생각하자.
- [math(g(x)=x^2+1\mod\ N)]
- [math(x_{i+1}=g(x_i))]
- [math(h(y)=y^2+1\mod\ p)]
- [math(y_0=x_0\mod\ p)], [math(y_{i+1}=h(y_i))]
[math(x_i=x_j)]이면 [math(y_i=y_j)]이기 때문에, [math(\left\{x_i\right\})]에서 발생한 충돌은 [math(\left\{y_i\right\})]에서도 충돌을 일으킨다. 만약 [math(y_i=y_j)]인데 [math(x_i\neq x_j)]이라면, [math(\gcd(x_i-x_j,N))]은 [math(p)]의 배수이지만 [math(N)]이 아니다. 이러한 [math(i)]와 [math(j)]를 찾는 게 폴라드 로 알고리즘의 핵심이다.
[math(\mathbb{N}_N)]을 정점으로 하고 [math((x,g(x)))]를 간선으로 하는 유향 그래프를 생각하자. 위에서 말한 성질로 인해 이 그래프에는 반드시 사이클이 존재하며, 이는 [math(\left\{x_i\right\})]가 주기성을 띤다는 것을 의미한다. Floyd's cycle-finding algorithm을 이용하여 그 주기를 찾을 수 있다.
[math(x_i=x_{2i})]가 성립하는 가장 작은 자연수 [math(i)]에 대해, 사이클의 주기 [math(d)]는 [math(i)]의 약수이며, 임의의 음이 아닌 정수 [math(j)]에 대해 [math(x_{i+dj}=x_{2(i+dj)})]이다.
[math(\left\{y_i\right\})]의 주기가 [math(\left\{x_i\right\})]의 주기보다 작은지는 수열을 직접 계산하기 전까지는 알 수 없으며, 혹시나 주기가 같다면 [math(x_0)]의 값을 달리하여 알고리즘을 다시 돌리면 된다.
폴라드 로 알고리즘을 유사 코드로 표현하면 다음과 같다.
1. 자연수 [math(N)]을 입력받는다.
2. [math(N=25)]일 때, [math(5)]를 출력한다.[1]
3. [math(x)]를 임의로 정한다.
4. [math(y=x)]
5. [math(x\leftarrow g(x))]
6. [math(y\leftarrow g(g(y)))]
7. [math(x=y)]이면 3로
8. [math(d=\gcd(x-y,N))]
9. [math(d=1)]이면 5로
10. [math(d)]는 [math(N)]의 자명하지 않은 약수이다. [math(d)]를 출력하고 종료한다.
2.5. 이차 체
Quadratic Sieve페르마 소인수분해법의 단점은 조건을 만족하는 [math(y)]를 찾기 매우 어렵다는 데 있다. 홀수 [math(N)]에 대해 [math(N+y^2=x^2)]을 만족하는 자연수 [math(y)]의 개수는 [math(\sqrt{N})]보다 작은 [math(N)]의 약수의 개수와 같다. 페르마 소인수분해법은 기초 알고리즘에서 나눗셈을 덧셈으로 바꾼 정도밖에 시간복잡도를 개선하지 못했다.
그런데 [math(y)]를 일일이 탐색하는 것이 아니라 만들어낼 수 있다면 어떨까? 이차 체는 이를 실제로 구현한 알고리즘이다.
다음과 같은 함수 [math(Q)]를 생각하자.
- [math(Q(x)=x^2-N)]
- [math(Q(x_{i_1})Q(x_{i_2})\cdots Q(x_{i_r})\equiv(x_{i_1}x_{i_2}\cdots x_{i_r})^2\ (\mathrm{mod}\ N))]
[math(N)]의 크기에 맞추어 적당한 [math(B)]를 정한다. 모든 소인수가 [math(B)] 이하인 정수를 [math(B)]-smooth number라 한다. 다음과 같은 과정을 거쳐서 수열 [math(\left\{x_i\right\})]을 생성한다.
- [math(n=0,\ \pm1,\ \pm2,\cdots)]에 대해, [math(Q\left(\left\lfloor\sqrt{N}\right\rfloor+n\right))]이 [math(B)]-smooth일 때, [math(\left\lfloor\sqrt{N}\right\rfloor+n)]을 수열 [math(\left\{x_i\right\})]에 추가한다.
[math(E)]에 열을 추가할 때마다 [math(E)]의 핵을 계산한다. 즉, 다음을 만족하는 벡터 [math(\vec{a})]를 찾는다.
- [math(E\vec{a}\equiv\mathbf{0}\ (\mathrm{mod}\ 2))], [math(a_k=1)]
마지막으로
- [math(\displaystyle x=\prod_{i=1}^kx^{a_i})]
- [math(\displaystyle y=\prod_{i=1}^kQ(x_i)^{a_i/2}=\prod_{j=0}^{\pi(B)}e_j^{\frac{1}{2}\sum_{i=1}^ka_ie_{i,\ j}})]
이차 체 알고리즘을 유사 코드로 나타내면 다음과 같다. 위의 설명과 달리 수열과 행렬이 0-based이기 때문에 변수의 index가 다른 점이 있다.
1. 홀수 [math(N)]을 입력받는다.
2. 소수 기저의 상한 [math(B)]를 정하고, 에라토스테네스의 체를 이용해 [math(B)] 이하의 소수를 모두 구하여 수열 [math(\left\{p_j\right\})]에 저장한다.
3. 빈 수열 [math(\left\{x_i\right\})], [math(\left\{A_i\right\})]와 크기가 [math(0\times(\pi(B)+1))]인 행렬 [math(E)], [math(V)], 크기가 [math(\pi(B)+1)]인 수열 [math(\left\{e_i\right\})]를 선언한다.[2]
4. [math(n=0)]
4. [math(x=\left\lfloor\sqrt{N}\right\rfloor)]
5. [math(Q(x)=0)]일 경우 [math(N)]은 제곱수이다. [math(x)]를 출력하고 종료한다.
6. [math(\displaystyle Q(x)=-C\prod_{j=0}^{pi(B)-1}p_j^{e_j})]와 같이 소인수분해한다. ([math(C)]는 [math(B)]보다 큰 소수의 곱으로 나타나는 자연수)
7. [math(C>1)]일 경우 11로
8. [math(e_{\pi(B)}=1)]
9. [math(x_0=x)], [math(A_0=1)], [math(E_0=e)], [math(V_0=e\mod2)]
10. [math(n\ \leftarrow\ n+1)]
11. [math(x^+=x)], [math(x^-=x)]
12. [math(x^+\ \leftarrow\ x^++1)]
13. [math(\displaystyle Q(x^+)=C\prod_{j=0}^{\pi(B)-1}p_j^{e_j})]와 같이 소인수분해한다.
14. [math(C>1)]일 경우 29로
15. [math(e_{\pi(B)}=0)], [math(a=2^n)], [math(\displaystyle v=\sum_{j=0}^{\pi(B)}2^j(e_j\mod2))]
16. [math(0\leq i<n)]인 정수 [math(i)]에 대해 다음을 반복한다.
[math(v\ \mathrm{xor}\ V_i)]가 [math(v)]보다 작을 경우, [math(v\ \leftarrow\ v\ \mathrm{xor}\ V_i)], [math(a\ \leftarrow\ a\ \mathrm{xor}\ A_i)]
17. [math(v=0)]일 경우, 25로18. [math(V_n\ \leftarrow\ v)], [math(A_n\ \leftarrow\ a)]
19. [math(k=n)]
20. [math(k>0)]과 [math(V_k>V_{k-1})]이 모두 성립하는 동안, 다음을 반복한다.
[math(V_k)]와 [math(V_{k-1})]의 값을 교환하고, [math(A_k)]와 [math(A_{k-1})]의 값을 교환한 다음, [math(k)]에서 [math(1)]을 뺀다.
21. [math(0\leq i<k)]인 정수 [math(i)]에 대해 다음을 반복한다.[math(v\ \mathrm{xor}\ V_i)]가 [math(V_i)]보다 작을 경우, [math(V_i\ \leftarrow\ v\ \mathrm{xor}\ V_i)], [math(A_i\ \leftarrow\ a\ \mathrm{xor}\ A_i)]
22. [math(x_n\ \leftarrow\ x^+)], [math(E_n\ \leftarrow\ e)]23. [math(n\ \leftarrow\ n+1)]
24. 29로
25. [math(y_1=x^+)]
26. [math(0\leq i<n)]인 정수 [math(i)]에 대해 다음을 반복한다.
[math(a\ \mathrm{and}\ 2^i\neq0)]일 경우, [math(e\ \leftarrow\ e+E_i)], [math(y_1\ \leftarrow\ y_1x_i\mod N)]. 이때 [math(\mathrm{and})]는 비트 연산자이다.
27. [math(\displaystyle y_2=\prod_{j=0}^{\pi(B)-1}p_j^{\frac{e_j}{2}}\mod N)]28. [math(y_1\neq y_2)]이고 [math(y_1+y_2\neq N)]일 경우, [math(\gcd(y_1-y_2,\ N))]을 출력하고 알고리즘을 종료한다.
29. [math(x^-\ \leftarrow\ x^--1)]
30. [math(\displaystyle Q(x^-)=C\prod_{j=0}^{\pi(B)-1}p_j^{e_j})]와 같이 소인수분해한다.
31. [math(C>1)]일 경우 46으로
32. [math(e_{\pi(B)}=0)], [math(a=2^n)], [math(\displaystyle v=\sum_{j=0}^{\pi(B)}2^j(e_j\mod2))]
33. [math(0\leq i<n)]인 정수 [math(i)]에 대해 다음을 반복한다.
[math(v\ \mathrm{xor}\ V_i)]가 [math(v)]보다 작을 경우, [math(v\ \leftarrow\ v\ \mathrm{xor}\ V_i)], [math(a\ \leftarrow\ a\ \mathrm{xor}\ A_i)]
34. [math(v=0)]일 경우, 42로35. [math(V_n\ \leftarrow\ v)], [math(A_n\ \leftarrow\ a)]
36. [math(k=n)]
37. [math(k>0)]과 [math(V_k>V_{k-1})]이 모두 성립하는 동안, 다음을 반복한다.
[math(V_k)]와 [math(V_{k-1})]의 값을 교환하고, [math(A_k)]와 [math(A_{k-1})]의 값을 교환한 다음, [math(k)]에서 [math(1)]을 뺀다.
38. [math(0\leq i<k)]인 정수 [math(i)]에 대해 다음을 반복한다.[math(v\ \mathrm{xor}\ V_i)]가 [math(V_i)]보다 작을 경우, [math(V_i\ \leftarrow\ v\ \mathrm{xor}\ V_i)], [math(A_i\ \leftarrow\ a\ \mathrm{xor}\ A_i)]
39. [math(x_n\ \leftarrow\ x^+)], [math(E_n\ \leftarrow\ e)]40. [math(n\ \leftarrow\ n+1)]
41. 46으로
42. [math(y_1=x^-)]
43. [math(0\leq i<n)]인 정수 [math(i)]에 대해 다음을 반복한다.
[math(a\ \mathrm{and}\ 2^i\neq0)]일 경우, [math(e\ \leftarrow\ e+E_i)], [math(y_1\ \leftarrow\ y_1x_i\mod N)]
44. [math(\displaystyle y_2=\prod_{j=0}^{\pi(B)-1}p_j^{\frac{e_j}{2}}\mod N)]45. [math(y_1\neq y_2)]이고 [math(y_1+y_2\neq N)]일 경우, [math(\gcd(y_1-y_2,\ N))]을 출력하고 알고리즘을 종료한다.
46. 12로
2.5.1. 최적화
여기서부터는 알고리즘 자체의 난이도가 크게 상승하는 대신, 수많은 최적화 기법을 통해 실행 속도를 크게 향상시킬 수 있다. 달리 말하면, 어떠한 최적화도 하지 않을 경우 폴라드 로 알고리즘보다도 느린 게 이차 체 알고리즘이다. 최적화에는 다음과 같은 요소가 있다.- 오일러 조건을 이용한 소수 기저의 선별
[math(x^2-N)]이 [math(p)]를 소인수로 가질 경우, [math(N\equiv x^2\ (\mathrm{mod}\ p))]가 성립한다. 즉, [math(x^2-N)]은 [math(N)]이 mod [math(p)]에 대한 이차 잉여가 되도록 하는 소수 [math(p)]로만 소인수분해가 가능하며, 이를 만족하지 않는 소수는 에라토스테네스의 체에서 쳐내야 한다. - 토넬리-샹크스 알고리즘을 이용한 [math(x^2-N)] 소인수분해의 배치 처리
토넬리-샹크스 알고리즘은 [math(N\equiv r^2\ (\mathrm{mod}\ p))]을 만족하는 [math(r)]의 값 중 하나를 직접 구해준다. 소수 기저를 선별할 때 [math(N)]의 제곱근 [math(r_p)]와 [math(p-r_p)]도 같이 구해서 근처에 적어둔다.
먼저 [math(Q(x^++1))], [math(Q(x^++2))], [math(Q(x^++3))], ⋯, [math(Q(x^++s))]를 나열한다. 이 수열의 계차수열이 등차수열임을 이용해 곱셈을 한 번만 사용하여 모두 계산할 수 있다. [math(s)]의 값이 너무 클 필요는 없다.
다음으로 소수 기저의 원소 [math(p)]에 대해 [math(x^++t\equiv r_p\ (\mathrm{mod}\ p))]를 만족하는 [math(t)]를 계산한 후, 여기서부터 [math(p)]칸씩 건너뛰어가며 [math(Q(x^++t))]를 [math(p)]로 나누어간다. [math(x^++t\equiv-r_p\ (\mathrm{mod}\ p))]에 대해서도 똑같이 나누어간다. 소수 기저를 모두 돌면서 나눗셈을 끝냈을 때 [math(1)]만 남으면 소인수분해에 성공한 것이다. 소인수를 실시간으로 저장할 수도 있겠지만, [math(B)]-smooth number가 매우 적기 때문에 일단 다 나눈 후에 다시 한 번 소인수분해를 하는 게 더 효율적이다. - 방정식 [math(x^2-N\equiv0\ (\mathrm{mod}\ p^n))]의 해의 점화식을 이용한 나눗셈 연산 횟수 줄이기
토넬리-샹크스 알고리즘을 이용해 불필요한 나눗셈을 크게 줄였다면, 큰 수를 직접 나누어보지 않고도 [math(p^n)]으로 나누어떨어지는지 확인하는 방법이 있을 것이라고 추측할 수 있다. - [math(p)]가 홀수 소수이고 [math(x_n)]이 [math(x_n^2-N\equiv0\ (\mathrm{mod}\ p^n))]를 만족할 때, [math(x_{n+1}=x_n+(x_n^2+N)(-2x_1)^{-1})]이다. 이때 [math((-2x_1)^{-1})]은 [math(-2x_1)]의 mod [math(p)]에 대한 역원이다.
- [math(p=2)]일 때는 상황이 다르다. 먼저 [math(x_n^2-N\equiv0\ (\mathrm{mod}\ 2))]의 해는 모든 짝수이다. [math(N\equiv3\ (\mathrm{mod}\ 4))]이면 모든 짝수 [math(x)]에 대해 [math(x_n^2-N)]은 4의 배수가 아니고, [math(N\equiv5\ (\mathrm{mod}\ 8))]이면 모든 짝수 [math(x)]에 대해 [math(x_n^2-N)]은 8의 배수가 아닌 4의 배수이며, [math(N\equiv1\ (\mathrm{mod}\ 8))]이면 모든 짝수 [math(x)]에 대해 [math(x_n^2-N)]은 8의 배수이다. 16의 배수부터는 다음의 과정을 거친다.
- [math(N\equiv1\ (\mathrm{mod}\ 16))]이면 [math(x_4=1)] 또는 [math(x_4=7)]이며,
[math(N\equiv9\ (\mathrm{mod}\ 16))]이면 [math(x_4=3)] 또는 [math(x_4=5)]이다. - [math(n\ge4)]일 때, [math(x_{n+1}=x_n+(x_n^2-N)/2)]으로 계산한다.
- 희소 행렬을 이용한 [math(E)]와 [math(V)]의 메모리 최적화
소수 기저의 크기는 [math(B/ln B)]에 비례하는데, 정작 [math(E)]의 한 열에 들어가는 양수는 [math(\log_2B)]보다도 적다. 즉, 불필요한 [math(0)]을 모두 저장해야 하는 행렬을 사용하는 대신, 양수와 그 위치를 리스트로 만들어 관리하는 것이 메모리를 최적화하고 불필요한 순회도 막아줄 수 있다.
이를 이용하면, [math(x^2-N)] 또는 [math(N-x^2)]의 로그를 구해놓고 [math(\ln p)]를 빼가면서 소인수분해를 배치 처리할 수 있다. 물론 부동소수점 오차가 존재하지만, 정수의 로그이기 때문에 오차가 [math(\ln2)]에 달하지 않는 이상 문제가 없다. 오히려 불필요하게 긴 수를 매우 작은 오차를 감수하고 53비트로 쳐내기 때문에 더욱 빠른 배치 처리가 가능하다.