실무 활용

정수론은 대회 문제에만 쓰이지 않습니다. 암호, 해시, 난수, 검증 숫자처럼 매일 쓰는 시스템 깊숙이 들어 있습니다. 이 장에서는 실제 쓰임새와 표준 라이브러리, 그리고 C++ · Java에서 자주 만나는 함정을 정리합니다.

공개 키 암호: RSA

RSA는 이 문서에서 다룬 도구를 모두 씁니다. 두 소수 p, q로 n = p × q와 φ = (p - 1)(q - 1)을 만들고, φ와 서로소인 e를 고른 뒤 확장 유클리드로 d = e^(-1) mod φ를 구합니다. 암호화는 c = m^e mod n, 복호화는 m = c^d mod n이며 둘 다 빠른 거듭제곱입니다. 아래는 원리를 보여 주는 장난감 예제입니다.

p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)   # 3233, 3120
e = 17
d = pow(e, -1, phi)                  # 2753

message = 65
cipher = pow(message, e, n)          # 2790
print(cipher, pow(cipher, d, n))     # 2790 65

실제 RSA는 2048비트 이상의 소수, 안전한 패딩(OAEP, PSS), 일정 시간 연산이 필요합니다. 암호 알고리즘을 직접 구현해서 서비스에 쓰지 말고 OpenSSL, 언어의 표준 암호 라이브러리처럼 검증된 구현을 쓰세요. Diffie-Hellman 키 교환과 타원 곡선 암호도 모듈러 거듭제곱과 역원 위에 서 있습니다.

그 밖의 쓰임새

• 해시: 문자열의 다항식 해시(라빈-카프)는 큰 소수를 법으로 계산하고, 일부 해시 테이블은 버킷 수를 소수로 잡아 충돌을 고르게 퍼뜨립니다.
• 난수: 선형 합동 생성기는 x = (a × x + c) mod m 꼴이고, 최대 주기를 얻는 조건이 GCD와 소인수로 표현됩니다.
• 검증 숫자: ISBN-10은 mod 11, 신용카드 번호의 룬 알고리즘은 mod 10 검사를 씁니다.
• 일정과 화면: 반복 주기가 다시 맞는 때(LCM), 화면 비율 약분(1920 × 1080 을 GCD 120으로 나눠 16:9)에 씁니다.
• 경우의 수: 대회와 코딩 테스트에서 답이 커지면 10^9 + 7이나 998244353으로 나눈 나머지를 요구합니다.

표준 라이브러리

함정 1: C++ · Java의 곱셈 오버플로

Python 정수는 크기 제한이 없지만 C++과 Java의 int는 32비트, long long/long은 64비트입니다. 10^9 + 7 미만의 두 수를 곱하면 약 10^18이라 int로는 넘치고 64비트에는 들어갑니다. 흔한 실수는 곱한 뒤에 64비트로 바꾸는 것입니다. 오른쪽 식은 int끼리 곱해서 이미 넘친 값을 넓힐 뿐입니다. C++에서 부호 있는 정수의 오버플로는 정의되지 않은 동작이고, Java에서는 조용히 값이 돌아갑니다.

#include <cstdint>
#include <iostream>

const long long MOD = 1'000'000'007LL;

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;  // 둘 다 mod 미만이라 곱이 64비트 안
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// 법이 10^18 처럼 크면 64비트 곱도 넘친다 — GCC/Clang 의 128비트 정수로 곱한다
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
    return static_cast<uint64_t>(static_cast<unsigned __int128>(a) * b % m);
}

int main() {
    int a = 1'000'000'000, b = 1'000'000'000;
    long long wrong = a * b;              // int 곱셈에서 이미 오버플로
    long long right = 1LL * a * b % MOD;  // 먼저 64비트로 넓힌다
    std::cout << right << ' ' << mod_pow(2, 1'000'000'000'000LL, MOD) << '\n';
    (void)wrong;
}

함정 2: 음수의 나머지

Python의 -7 % 3은 2지만 C++과 Java의 -7 % 3은 -1입니다. 뺄셈을 한 뒤 나머지를 취하면 음수가 나올 수 있으므로 ((x % m) + m) % m으로 맞추거나 Java의 Math.floorMod를 씁니다. 확장 유클리드의 계수 x가 음수로 나오는 것도 같은 이유로 보정해야 합니다.

import java.math.BigInteger;

public class ModPitfalls {
    public static void main(String[] args) {
        final long MOD = 1_000_000_007L;
        int a = 1_000_000_000, b = 1_000_000_000;
        long wrong = a * b;              // int 곱셈이 돌아간 값: -1486618624
        long right = (long) a * b % MOD; // 49
        System.out.println(wrong + " " + right);

        System.out.println(-7 % 3);               // -1
        System.out.println(Math.floorMod(-7, 3)); // 2

        BigInteger x = BigInteger.valueOf(3);
        BigInteger m = BigInteger.valueOf(MOD);
        System.out.println(x.modInverse(m));                        // 333333336
        System.out.println(x.modPow(BigInteger.valueOf(200), m)); // 136318165
    }
}

함정 3: 그 밖의 실수

• 페르마의 소정리 a^(p-2)는 법이 소수일 때만 역원입니다. 법이 합성수면 확장 유클리드를 쓰고 서로소인지 확인합니다.
• lcm(a, b) = a * b / gcd(a, b)는 곱에서 먼저 넘칩니다. a / gcd(a, b) * b 순서로 계산합니다.
• C++의 pow, JavaScript의 Math.pow는 부동소수점이라 큰 정수 거듭제곱에서 오차가 납니다.
• sqrt(n)도 부동소수점 오차가 있으므로 반복 조건은 i * i <= n이나 Python의 math.isqrt로 씁니다.
• 체의 크기가 10^8을 넘으면 메모리가 문제됩니다. 비트 배열이나 구간을 나눠 처리하는 분할 체를 고려하세요.
• JavaScript number는 2^53까지만 정수를 정확히 표현하므로 10^9 + 7 미만 두 수의 곱은 BigInt로 계산합니다. 예를 들어 (999_999_999n * 999_999_999n) % 1_000_000_007n은 64n이지만 number로 계산하면 63이 나옵니다.

정리

RSA, 해시, 난수, 검증 숫자는 모두 모듈러 연산 위에 있습니다. 실무에서는 표준 라이브러리의 gcd, pow, BigInteger를 먼저 쓰고, 직접 구현할 때는 곱셈 오버플로, 음수 나머지, 소수가 아닌 법, 부동소수점 거듭제곱을 점검하세요. 암호는 직접 만들지 말고 검증된 라이브러리를 쓰는 것이 원칙입니다.

더 읽을거리

• Python math module
• Python built-in pow
• cppreference: std::gcd
• Java BigInteger
• cp-algorithms: Binary Exponentiation
• cp-algorithms: Binomial Coefficients
• Wikipedia: RSA cryptosystem