큰 수의 소인수분해 (Pollard Rho 알고리즘 활용)

문제 설명

양의 정수 ( n )이 주어졌을 때, 이를 소인수분해하여 모든 소인수를 오름차순으로 출력하는 문제이다. 소인수분해의 결과는 ( n )의 모든 소인수를 중복을 포함하여 나타낸다. 주어진 수는 ( 1 < n < 2^{62} )의 범위를 가지며, 이를 빠르게 처리해야 한다.

핵심 아이디어

1. 효율적인 소인수분해:

   • ( n )의 크기가 매우 크므로 단순한 방식(예: 모든 수를 나누어보는 방식)으로는 처리하기 어렵다.
   • Pollard Rho 알고리즘과 Miller-Rabin 소수 판별 알고리즘을 사용해 효율적으로 소인수를 구한다.

2. Pollard Rho 알고리즘:

   • ( n )의 약수를 찾기 위해 ( f(x) = (x^2 + c) \mod n ) 형태의 함수로 탐색한다.
   • 이 알고리즘은 확률적 방식으로 작동하며, 주어진 ( n )의 소인수를 빠르게 찾는다.

3. Miller-Rabin 소수 판별:

   • ( n )이 소수인지 확인하기 위해 Miller-Rabin 알고리즘을 사용한다.
   • 이 알고리즘은 여러 기반수를 사용하여 ( n )이 소수인지 효율적으로 판단한다.

코드

import java.util.*;

public class Main {
    private static List<Long> factors = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sc.close();

        if (n <= 1) {
            throw new IllegalArgumentException("Input must be greater than 1.");
        }

        factorize(n);
        Collections.sort(factors);

        for (long factor : factors) {
            System.out.println(factor);
        }
    }

    private static long multiply(long a, long b, long mod) {
        long result = 0;
        while (b > 0) {
            if ((b & 1) == 1) {
                result = (result + a) % mod;
            }
            b >>= 1;
            a = (a * 2) % mod;
        }
        return result;
    }

    private static long power(long a, long b, long mod) {
        long result = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                result = multiply(result, a, mod);
            }
            b >>= 1;
            a = multiply(a, a, mod);
        }
        return result;
    }

    private static boolean isPrime(long n) {
        if (n <= 1) return false;
        long[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};

        long d = n - 1;
        int s = 0;
        while (d % 2 == 0) {
            d /= 2;
            s++;
        }

        for (long a : primes) {
            if (a == n) return true;
            if (a > n) break;

            long x = power(a, d, n);
            if (x == 1 || x == n - 1) continue;

            boolean composite = true;
            for (int r = 0; r < s; r++) {
                x = multiply(x, x, n);
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            if (composite) return false;
        }
        return true;
    }

    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private static void factorize(long n) {
        if (n == 1) return;
        if (n % 2 == 0) {
            factors.add(2L);
            factorize(n / 2);
            return;
        }
        if (isPrime(n)) {
            factors.add(n);
            return;
        }

        long x = 2, y = 2, c = 1, g = n;
        Random rand = new Random();

        do {
            if (g == n) {
                x = rand.nextInt((int) Math.min(n - 2, Integer.MAX_VALUE)) + 2;
                y = x;
                c = rand.nextInt(20) + 1;
            }

            x = pollardFunction(x, c, n);
            y = pollardFunction(pollardFunction(y, c, n), c, n);
            g = gcd(Math.abs(x - y), n);
        } while (g == 1);

        factorize(n / g);
        factorize(g);
    }

    private static long pollardFunction(long x, long c, long n) {
        return (multiply(x, x, n) + c) % n;
    }
}

코드 설명

주요 함수

1. factorize:

• 입력 𝑛을 소인수분해한다.
• 소수인 경우 리스트에 추가하고 종료하며, 소수가 아닌 경우 Pollard Rho를 통해 약수를 찾아 분할한다.

2. pollardFunction:

• Pollard Rho 알고리즘에서 사용하는 반복 함수 𝑓(𝑥)=(𝑥2+𝑐)mod  𝑛를 구현한다.

3. isPrime:

• Miller-Rabin 알고리즘을 사용하여 𝑛이 소수인지 판별한다.

4. multiply:

• 모듈러 연산을 고려한 곱셈을 수행한다. 오버플로 방지를 위해 수동으로 구현하였다.

5. power:

• 모듈러 거듭제곱 연산을 구현한다.

6. gcd:

• 두 수의 최대공약수를 구한다.

흐름

• 입력받은 𝑛을 처리하고 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑧𝑒를 호출한다.
• 𝑛이 소수이면 바로 결과에 추가하고, 그렇지 않으면 Pollard Rho 알고리즘으로 약수를 찾아 재귀적으로 처리한다.
• 모든 소인수를 구한 후 오름차순으로 정렬하여 출력한다.

So...

Pollard Rho 알고리즘과 Miller-Rabin 알고리즘을 결합하여 (2^{62}) 이하의 수를 빠르게 소인수분해하였다.
이 방식은 확률적 요소를 포함하지만, 주어진 입력 범위에서는 안정적이고 효율적이다.
복잡한 수학적 알고리즘을 구현하면서 기본적인 연산 최적화와 데이터 구조 활용의 중요성을 확인할 수 있었다.