Trial division

시행 나눗셈(Trial division)은 정수 인수분해(integer factorization) 알고리듬 중 가장 힘들지만 이해하기 가장 쉽습니다. 시행 나눗셈 위의 본질적인 아이디어는 만약 정수 n, 인수화될 정수가 차례로 n보다 작은 각 숫자로 나눌 수 있는지 확인하기 위한 테스트입니다. 예를 들어, 정수 $n = 12$ 에 대해, 그것을 나누는 숫자는 1, 2, 3, 4, 6, 12뿐입니다. 이 목록에서 가장 큰 소수의 거듭제곱(powers of primes)만 선택하면 $12 = 3 \times 4 = 3 \times 2 2$ 임을 제공합니다.

시행 나눗셈은 피보나치(Fibonacci)에 의해 그의 저서 Liber Abaci (1202)에서 처음으로 설명되었습니다.^[1]

Method

정수 n이 주어지면 (n은 "인수화될 정수"로 참조됨), 시행 나눗셈은 n이 임의의 더 작은 숫자로 나뉠 수 있는지 여부를 시스템적으로 테스트하는 것으로 구성됩니다. 분명하게, 임의적인 n이 3, 등에 의한 것보다 2로 나누어질 가능성이 더 높기 때문에 n보다 작은 후보 인수를 2부터 위쪽 방향으로 순서대로 테스트하는 것은 가치가 있습니다. 이 순서화와 함께, 숫자가 이미 2로 나누어지지 않는 것으로 결정되면 4로 나누어지는지 테스트할 필요가 없고, 3에 대한 것과 3의 임의의 배수에도 마찬가지고, 이런 식으로 계속됩니다. 그러므로, 노력은 후보 인수로 소수만 선택함으로써 줄일 수 있습니다. 게다가, n이 어떤 숫자 p로 나뉠 수 있으면 n = p × q이고 q가 p보다 작으면, n은 이전에 q 또는 q의 소수 인수로 나누어지는 것으로 감지되었을 것이기 때문에 시행 인수는 $\scriptstyle {\sqrt {n}}$ 보다 더 이상 갈 필요가 없습니다.

소수 인수에 대한 명확한 경계가 가능합니다. $P i$ 가 P₁ = 2, P₂ = 3, P₃ = 5, 등이 되도록 $i$ 번째 소수라고 가정합니다. 그런-다음 n의 가능한 인수로 테스트할 가치가 있는 마지막 소수는 $P i$ 이며, 여기서 $P 2 i + 1 > n$ 입니다; 이때 상등은 $P i + 1$ 이 인수라는 것을 의미합니다. 따라서 2, 3, 및 5로 테스트하면 다음 소수의 제곱이 49이기 때문에 25가 아니라 n = 48까지 충분하고, n = 25 아래에서 단지 2와 3이 충분합니다. n의 제곱근이 정수이면, 그것이 인수이고 n은 완전 제곱(perfect square)입니다.

시행 인수로 연속적인 정수를 사용하는 시행 나눗셈 알고리듬의 예제는 다음과 같습니다 (Python에서 작성됨):

def trial_division(n: int) -> list[int]:
    """Return a list of the prime factors for a natural number."""
    a = []               # Prepare an empty list.
    f = 2                # The first possible factor.    
    while n > 1:         # While n still has remaining factors...
        if n % f == 0:   # The remainder of n divided by f might be zero.        
            a.append(f)  # If so, it divides n. Add f to the list.
            n //= f      # Divide that factor out of n.
        else:            # But if f is not a factor of n,
            f += 1       # Add one to f and try again.
    return a             # Prime factors may be repeated: 12 factors to 2,2,3.

또는 2배 더 효율적입니다:

def trial_division(n: int) -> list[int]:
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1: a.append(n)
    # Only odd number is possible
    return a

이들 버전의 시행 나눗셈은 n의 모든 가능한 인수를 확인하기 때문에 하나가 있으면 n의 인수를 찾기 위해 보장됩니다 — 그리고 n이 소수이면, 이것은 n까지의 모든 시행 인수를 의미합니다. 따라서, 알고리듬이 하나의 인수, n를 찾으면, n이 소수(prime)라는 증명입니다. 만약 하나보다 많은 인수가 발견되면, n은 복합 정수(composite integer)입니다. 이것을 말하는 더 계산적으로 유리한 방법은, 그 제곱이 n을 초과하지 않는 임의의 소수가 나머지 없이 그것을 나누면, n은 소수가 아니라는 것입니다.

아래는 C++ 버전입니다 (f를 제곱하지 않음)

template <class T, class U>
vector<T> TrialDivision(U n)
{
    vector<T> v; T f;
    f = 2;
    while (n % 2 == 0) { v.push_back(f); n /= 2; }
    f = 3;
    while (n % 3 == 0) { v.push_back(f); n /= 3; }
    f = 5;
    T ac = 9, temp = 16;
    do {
        ac += temp; // Assume addition does not cause overflow with U type
        if (ac > n) break; 
        if (n % f == 0) {
            v.push_back(f);
            n /= f;
            ac -= temp;
        }
        else { 
            f += 2;
            temp += 8;
        }
    } while (1);
    if (n != 1) v.push_back(n);
    return v;
}

Speed

최악의 경우에서, 시행 나눗셈은 힘든 알고리듬입니다. 밑수-2 n 자릿수 숫자 a에 대해, 2에서 시작하고 a의 제곱근까지만 작동하면, 알고리듬은 다음의 시행 나눗셈을 요구합니다:

\pi (2^{n/2})\approx {2^{n/2} \over \left({\frac {n}{2}}\right)\ln 2}

여기서 $\pi (x)$ 는 x보다 작은 소수의 개수, 소수-세는 함수(prime-counting function)를 나타냅니다. 이것은 소수를 후보 인수로 얻기 위한 소수성 테스트(primality testing)의 오버헤드를 고려하지 않습니다. 유용한 테이블은 클 필요가 없습니다: P(3512) = 32749, 16비트 부호화된 정수에 맞는 마지막 소수와 부호-없는 16비트 정수에 대해 P(6542) = 65521입니다. 그것은 65537² = 4,295,098,369까지의 숫자에 대해 소수성을 테스트하기에 충분합니다. 그러한 테이블 (보통 에라토스테네스의 체를 통해)을 준비하는 것은 많은 숫자가 테스트되어야 하는 것이면 오직 가치가 있습니다. 만약 대신 변형이 소수성 테스트 없이 사용되지만, 단순히 제곱근보다 작은 모든 각 홀수로 나누면 밑수-2 n 자릿수 숫자 a, 소수 여부에 관계없이, 최대 약 다음이 걸릴 수 있습니다:

2^{n/2}

두 경우 모두에서, 요구된 시간은 숫자의 자릿수에 따라 지수적으로 증가합니다.

그렇더라도, 이것이 가장 잘 알려진 알고리듬도 지수적으로 시간이 증가한다는 점을 고려하면 상당히 만족스러운 방법입니다. 주어진 길이의 정수에서 균등하게 무작위로 선택된 a에 대해, 2가 a의 인수일 확률이 50%이고 3이 a의 인수일 확률이 33%이고, 이런 식으로 계속됩니다. 모든 양의 정수 중 88%는 100 아래의 인수를 가지고 92%는 1000 아래에 인수를 가진다는 것을 알 수 있습니다. 따라서, 임의적인 큰 a에 직면했을 때, $a=1000$ 에 대해 밑수-2 $n=10$ 이므로, 작은 소수로 나눔가능성에 대해 확인하는 것이 좋습니다.

어쨌든, 작은 소수에서 인수를 가지지 않는 많은-자릿수 숫자는 시행 나눗셈으로 인수화하기 위해 며칠 또는 몇 달이 걸릴 수 있습니다. 그러한 경우에서, 이차 체(quadratic sieve) 및 일반적인 숫자 필드 체(general number field sieve, GNFS)와 같은 다른 방법이 사용됩니다. 이들 방법은 역시 초-다항식 시간 증가도 있기 때문에, n 자릿수의 실질적인 한계는 매우 빠르게 도달됩니다. 이러한 이유로, 공개-키 암호화(public key cryptography)에서, a에 대한 값은 슈퍼컴퓨터와 컴퓨터 그리드와 같은 임의의 사용-가능한 컴퓨터 시스템 또는 컴퓨터 클러스터에서 유용한 기간에 공개적으로 알려진 방법에 의해 인수화될 수 없도록 비슷한 크기의 큰 소수 인수를 가지도록 선택됩니다. 인수화되어 온 가장 큰 암호화-등급 숫자는 GNFS와 여러 슈퍼컴퓨터의 자원을 사용하는 RSA-250, 250 자릿수 숫자입니다. 실행 시간은 2700 코어 년이었습니다.

References

^ Mollin, Richard A. (2002). "A brief history of factoring and primality testing B. C. (before computers)". Mathematics Magazine. 75 (1): 18–29. doi:10.2307/3219180. JSTOR 3219180. MR 2107288.

Childs, Lindsay N. (2009). A concrete introduction to higher algebra. Undergraduate Texts in Mathematics (3rd ed.). New York, NY: Springer-Verlag. ISBN 978-0-387-74527-5. Zbl 1165.00002.
Crandall, Richard; Pomerance, Carl (2005). Prime numbers. A computational perspective (2nd ed.). New York, NY: Springer-Verlag. ISBN 0-387-25282-7. Zbl 1088.11001.

External links

Wikiversity offers a lesson on prime factorization using trial division with Python.

Fast JavaScript Prime Factor Calculator using trial division. Can handle numbers up to about 2⁵³
Trial Division in Java, C and JavaScript (in Portuguese)

[1] Mollin, Richard A. (2002). "A brief history of factoring and primality testing B. C. (before computers)". Mathematics Magazine. 75 (1): 18–29. doi:10.2307/3219180. JSTOR 3219180. MR 2107288.

[1]