C# BigInteger를 활용한 대규모 숫자 연산

BigInteger는 정수의 자릿수 제한을 사실상 없애 임의 정밀도 연산을 가능하게 합니다. 금융 계산의 초대형 정수, 조합론, 암호학 등에서 필수 도구입니다. 본 글은 BigInteger 기본기부터 실전 예제까지 간략하고 실용적으로 정리합니다.

1. 준비: 네임스페이스와 기본 사용

.NET 5+에서는 바로 사용할 수 있으며, 네임스페이스만 추가하면 됩니다. 큰 정수는 문자열로 파싱하거나 기본 정수형에서 승격해 생성합니다.

using System;
using System.Numerics;

class Program
{
    static void Main()
    {
        // 기본 생성
        BigInteger a = new BigInteger(1234567890123456789L);
        BigInteger b = BigInteger.Parse("987654321098765432109876543210");

        // 산술 연산
        BigInteger sum = a + b;
        BigInteger prod = a * b;
        BigInteger div = b / a;
        BigInteger mod = b % a;

        Console.WriteLine(sum);
        Console.WriteLine(prod);
        Console.WriteLine(div);
        Console.WriteLine(mod);

        // 비교와 속성
        Console.WriteLine(b > a);
        Console.WriteLine(b.IsEven);
        Console.WriteLine(BigInteger.Zero);
        Console.WriteLine(BigInteger.One);

        // 주의: 부동소수점 & decimal에서의 변환은 소수부가 절삭됩니다.
        BigInteger fromDecimal = (BigInteger)123.45m; // 123
        Console.WriteLine(fromDecimal);
    }
}

2. 파싱과 서식: 입력과 출력 다루기

문자열 파싱에는 Parse/TryParse를, 출력 서식에는 표준 숫자 서식을 그대로 활용할 수 있습니다. 16진 출력도 가능합니다.

using System;
using System.Globalization;
using System.Numerics;

class FormatDemo
{
    static void Main()
    {
        // 안전한 파싱
        string input = "123456789123456789123456789";
        if (BigInteger.TryParse(input, out BigInteger x))
        {
            Console.WriteLine(x.ToString("N0", CultureInfo.InvariantCulture)); // 3자리 그룹
            Console.WriteLine(x.ToString("X")); // 16진수
        }

        // 바이트 배열 변환 (리틀 엔디언, 2의 보수 표현)
        BigInteger big = BigInteger.Parse("340282366920938463463374607431768211456");
        byte[] bytes = big.ToByteArray();
        BigInteger roundTrip = new BigInteger(bytes);
        Console.WriteLine(roundTrip == big);
    }
}

3. 고급 연산: 거듭제곱, 모듈러 연산, 최대공약수

큰 지수 연산이나 RSA 같은 모듈러 거듭제곱은 BigInteger의 내장 메서드를 적극 활용합니다. 최대공약수도 제공합니다.

using System;
using System.Numerics;

class AdvancedOps
{
    static void Main()
    {
        BigInteger baseVal = BigInteger.Parse("123456789123456789123456789");
        BigInteger pow = BigInteger.Pow(baseVal, 10); // baseVal^10
        Console.WriteLine(pow);

        // 모듈러 거듭제곱 (빠르고 안전)
        BigInteger mod = BigInteger.Parse("1000000007");
        BigInteger modPow = BigInteger.ModPow(baseVal, 1_000_000, mod);
        Console.WriteLine(modPow);

        // 최대공약수
        BigInteger a = BigInteger.Parse("987654321987654321987654321");
        BigInteger b = BigInteger.Parse("123456789123456789");
        Console.WriteLine(BigInteger.GreatestCommonDivisor(a, b));
    }
}

4. 실전 예제 1: 1000! 계산과 자릿수

팩토리얼은 작은 반복 곱셈으로도 충분합니다. 결과 자릿수는 문자열 길이로 확인합니다.

using System;
using System.Numerics;

class FactorialDemo
{
    static BigInteger Factorial(int n)
    {
        BigInteger res = BigInteger.One;
        for (int i = 2; i <= n; i++) res *= i;
        return res;
    }

    static void Main()
    {
        BigInteger f = Factorial(1000);
        Console.WriteLine(f);
        Console.WriteLine(f.ToString().Length); // 자릿수
    }
}

5. 실전 예제 2: 조합 nCk (오버플로 없이)

분자/분모를 단계적으로 곱하고 매 단계 최대공약수로 약분하면 중간 수의 폭발을 줄일 수 있습니다.

using System;
using System.Numerics;

class BinomialDemo
{
    static BigInteger Binomial(int n, int k)
    {
        if (k < 0 || k > n) return BigInteger.Zero;
        if (k > n - k) k = n - k;
        BigInteger num = BigInteger.One;
        BigInteger den = BigInteger.One;
        for (int i = 1; i <= k; i++)
        {
            num *= n - (k - i);
            den *= i;
            BigInteger g = BigInteger.GreatestCommonDivisor(num, den);
            if (g > 1)
            {
                num /= g;
                den /= g;
            }
        }
        return num / den;
    }

    static void Main()
    {
        Console.WriteLine(Binomial(1000, 500));
    }
}

6. 실전 예제 3: 모듈러 지수로 빠른 암호 연산

RSA 등에서는 지수가 매우 큽니다. 반복 제곱 대신 ModPow를 사용해야 성능과 메모리 모두 유리합니다.

using System;
using System.Numerics;

class ModExpDemo
{
    static void Main()
    {
        BigInteger n = BigInteger.Parse("9516311845790656153499716760847001433441357"); // 모듈러스 (예시)
        BigInteger e = 65537;
        BigInteger message = BigInteger.Parse("12345678901234567890");

        // 암호화: c = m^e mod n
        BigInteger cipher = BigInteger.ModPow(message, e, n);
        Console.WriteLine(cipher);
    }
}

7. 성능 팁과 주의사항

1) BigInteger는 불변입니다. 곱셈/덧셈마다 새 인스턴스가 만들어지므로, 알고리즘을 줄이는 것이 곧 최적화입니다. 가능한 한 약분, 모듈러 연산, 빠른 거듭제곱(제곱-곱 알고리즘)을 사용합니다.

2) 문자열 변환은 무겁습니다. 루프 안에서 ToString 호출을 피하고, 필요한 지점에서만 출력합니다.

3) 부동소수점에서의 변환은 소수부가 절삭됩니다. 정밀한 정수만 필요할 때만 캐스팅을 사용합니다.

4) 바이트 배열 변환은 리틀 엔디언 2의 보수 표현을 사용합니다. 외부 시스템과 교환 시 엔디언/부호 규약을 확인합니다.

5) 작은 형으로의 캐스팅은 OverflowException이 발생할 수 있습니다. 범위 체크 후 변환하거나 TryWriteBytes 등 저수준 API를 고려합니다.

8. 마무리

BigInteger는 큰 수를 다루는 대부분의 시나리오에서 강력하고 간단한 해법을 제공합니다. Parse/ToString으로 I/O를 처리하고, Pow/ModPow/GCD로 고급 연산을 결합하면 조합론과 암호 연산까지 실용 수준으로 구현할 수 있습니다. 위 예제들을 기반으로 자신만의 큰 수 계산 유틸리티를 구성해 보시기 바랍니다.