다중 정밀도의 기본 알고리즘

D4. [x^2 - N 테스트.] y <- [sqrt(x^2 - N)] 또는 [sqrt(x^2 - N)]으로 설정한다. y^2 = x^2 - N이면, (x - y)가 원하는 인수이고, 알고리즘이 종료된다. 그렇지 않으면 단계 D3으로 돌아간다. |

이 절차를 빠르게 실행하는 여러 방법이 있다. 예를 들어, N mod 3 = 2이면, x는 3의 배수여야 한다; x = 3x'로 설정하고, x'에 해당하는 다른 체를 사용하여 속도를 세 배로 높일 수 있다. N mod 9 = 1, 4, 또는 7이면, x는 각각 (modulo 9)에서 ±1, ±2, 또는 ±4와 합동이어야 한다; 따라서 두 체를 실행한다 (x = 9x' + a인 x'와 x = 9x'' - a인 x''에 대해 하나씩) 속도를 4.5배 높인다. N mod 4 = 3이면, x mod 4가 알려져 있고 속도가 추가로 4배 증

알고리즘 D의 속도를 높이는 훨씬 더 중요한 방법은 대부분의 이진 컴퓨터에서 발견되는 불리언 연산을 사용하는 것이다. 예를 들어, MIX가 워드당 30비트를 가진 이진 컴퓨터라고 가정하자. 테이블 S[i, k_i]는 항목당 하나의 비트로 메모리에 유지할 수 있다; 따라서 30개의 값이 하나의 워드에 저장될 수 있다. 메모리의 지정된 워드의 k번째 비트가 0이면 1 <= k <= 30에 대해 어큐뮬레이터의 k번째 비트를 0으로 대체하는 AND 연산을 사용하여 30개의 x 값을 한 번에 처리할 수 있다! 편의를 위해

알고리즘 D의 속도를 높이는 훨씬 더 중요한 방법은 대부분의 이진 컴퓨터에서 발견되는 불리언 연산을 사용하는 것이다. 예를 들어, MIX가 워드당 30비트를 가진 이진 컴퓨터라고 가정하자. 테이블 S[i, k_i]는 항목당 하나의 비트로 메모리에 유지할 수 있다; 따라서 30개의 값이 하나의 워드에 저장될 수 있다. 메모리의 지정된 워드의 k번째 비트가 0이면 1 <= k <= 30에 대해 어큐뮬레이터의 k번째 비트를 0으로 대체하는 AND 연산을 사용하여 30개의 x 값을 한 번에 처리할 수 있다! 편의를 위해

m_i에 대한 테이블 항목이 lcm(m_i, 30) 비트를 포함하도록 테이블 S[i, j]의 여러 복사본을 만들 수 있다; 그러면 각 모듈러스에 대한 체 테이블이 정수 개의 워드를 채운다. 이러한 가정 하에서, 알고리즘 D의 주요 루프의 30번의 실행은 다음 형태의 코드와 동등하다:

D2 LD1 K1 rI1 <- k_1.

D2 LD1 K1 rI1 <- k_1.

LDA S1,1 rA <- S'[1, rI1].

DEC1 1 rI1 <- rI1 - 1.