정수론 기초: 소수·최대공약수·합동식

정수론이 쓰이는 곳

정수론은 정수의 나눗셈 구조를 다룬다. 프로그래밍에서는 세 군데서 자주 만난다.

• 큰 수를 나머지로 다루는 문제: 「답을 10⁹+7로 나눈 나머지를 출력하라」. 경우의 수가 정수 범위를 넘을 때 쓴다.
• 주기·배수 문제: 여러 주기가 동시에 맞는 시점(최소공배수), 나머지 조건을 동시에 만족하는 수(중국인의 나머지 정리).
• 공개키 암호: RSA는 오일러 정리와 모듈러 역원, 디피-헬먼은 모듈러 거듭제곱 위에 서 있다(인코딩·암호화·해시·토큰화와 디지털 서명).

출발점: 나눗셈 정리와 산술의 기본 정리

소인수분해가 유일하므로 최대공약수, 약수의 개수, 약수의 합 같은 값이 모두 소인수분해 하나에서 나온다.

언어마다 음수의 나머지 부호가 다르다. Python -7 % 3은 2, C·Java·JavaScript는 −1이다. 나눗셈 정리의 0 ≤ r을 원하면 ((a % m) + m) % m으로 맞춘다.

최대공약수, 최소공배수, 베주 항등식

유클리드 호제법은 gcd(a, b) = gcd(b, a mod b)를 반복한다. 단계 수는 작은 수의 자릿수의 5배를 넘지 않으므로 O(log min(a, b))다. 코드와 복잡도 분석은 재귀 함수에 있다.

x, y는 확장 유클리드 알고리즘으로 구한다. 호제법을 거꾸로 따라 올라가며 계수를 갱신한다.

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0              # a·1 + 0·0 = a
    d, x, y = ext_gcd(b, a % b)     # b·x + (a % b)·y = d
    return d, y, x - (a // b) * y   # a·y + b·(x − ⌊a/b⌋·y) = d
 
ext_gcd(240, 46)  # (2, -9, 47): 240·(−9) + 46·47 = 2

소수 찾기와 소인수분해: 에라토스테네스의 체

def smallest_prime_factors(n):
    spf = list(range(n + 1))
    for i in range(2, int(n ** 0.5) + 1):
        if spf[i] == i:                       # i가 소수
            for j in range(i * i, n + 1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf
 
def factorize(k, spf):
    out = []
    while k > 1:
        out.append(spf[k]); k //= spf[k]
    return out  # factorize(360, spf) → [2, 2, 2, 3, 3, 5]

모듈러 연산과 합동식

a ≡ b (mod n)은 n ∣ (a − b), 즉 a와 b를 n으로 나눈 나머지가 같다는 뜻이다. 덧셈·뺄셈·곱셈은 나머지를 먼저 취해도 결과가 같으므로 중간마다 mod를 해서 수가 커지는 것을 막는다. 나눗셈은 그대로 안 되고 모듈러 역원을 곱해야 한다.

선형 합동 생성기: 모듈러 연산으로 만드는 난수

난수 함수 없이 난수를 흉내 내는 가장 단순한 방법이 선형 합동 생성기(LCG, Linear Congruential Generator) 다. 직전 값에 곱하고 더한 뒤 나머지를 취하는 일을 반복한다.

x_(n+1) = (a · x_n + c) mod m        x_0 = 시드(seed)

• 시드가 같으면 수열도 같다. 그래서 「시간」을 시드로 쓴다. 현재 시각을 나노초 단위로 읽으면(time.time_ns()) 실행마다 다른 수열이 나온다.
• 값은 m가지뿐이라 언젠가 반복된다. 주기가 m 전체가 되는 조건(헐-도벨 정리)은 c와 m이 서로소, a - 1이 m의 모든 소인수로 나누어떨어짐, m이 4의 배수면 a - 1도 4의 배수, 세 가지다.
• 범위 [lo, hi]의 수는 lo + x mod (hi - lo + 1)로 얻는다. m이 범위 크기의 배수가 아니면 작은 값이 조금 더 자주 나오는 치우침이 생긴다. 하위 비트는 주기가 짧으므로 상위 비트를 쓰는 편이 낫다.
• 중복 없이 k개를 뽑을 때는 범위의 수를 배열에 담고, 피셔-예이츠 셔플을 앞 k칸까지만 돌린다. i번째 칸을 [i, 끝] 중 난수 위치와 맞바꾸는 일을 k번 하면 O(k)에 뽑힌다.
• Java java.util.Random이 a = 0x5DEECE66D, c = 11, m = 2⁴⁸인 LCG다. 몇 개의 출력만 보면 다음 값을 계산할 수 있어 보안에는 쓰지 않는다. 토큰·비밀번호처럼 예측되면 안 되는 값은 운영체제의 엔트로피를 쓰는 암호학적 난수 생성기(Python secrets, Java SecureRandom)로 만든다.

중국인의 나머지 정리

「2로 나누면 1, 3으로 나누면 2, 7로 나누면 5가 남는 수」처럼 여러 나머지 조건을 동시에 푸는 정리다.

x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), …, x ≡ a_k (mod n_k)
n₁ … n_k가 쌍마다 서로소이면, N = n₁n₂…n_k에 대해 mod N에서 해가 하나뿐이다.
 
cᵢ = N / nᵢ,  dᵢ = cᵢ의 mod nᵢ 역원(확장 유클리드)
x = Σ aᵢ·cᵢ·dᵢ  (mod N)

위 예의 답은 x ≡ 5 (mod 42)다(5 = 2·2+1 = 3·1+2 = 7·0+5). 모듈러가 서로소가 아니면 gcd(nᵢ, nⱼ)가 aᵢ − aⱼ를 나누는 조건이 모든 쌍에서 성립할 때만 해가 있고, 해는 lcm(n₁, …, n_k)을 법으로 하나다.

이 정리는 반대 방향으로도 쓴다. 큰 n에 대한 계산을 n의 소인수 거듭제곱별로 나눠 하고 합친다. RSA 복호화를 약 4배 빠르게 하는 CRT 최적화가 그 예다.

산술 함수

• 모두 곱셈적 함수다. 서로소인 a, b에 대해 f(ab) = f(a)f(b).
• 약수들의 φ를 더하면 n이 된다: Σ φ(d) = n(d는 n의 약수). 18의 약수 1, 2, 3, 6, 9, 18에서 1 + 1 + 2 + 2 + 6 + 6 = 18.
• 1~N의 φ를 모두 구할 때는 체를 쓴다.

phi = list(range(n + 1))
for i in range(2, n + 1):
    if phi[i] == i:                 # 아직 안 건드렸으면 소수
        for j in range(i, n + 1, i):
            phi[j] -= phi[j] // i   # phi[j] *= (1 - 1/i)

오일러 정리와 페르마의 소정리

오일러 정리:       gcd(a, n) = 1이면  a^φ(n) ≡ 1 (mod n)
페르마의 소정리:   소수 p가 a를 나누지 않으면  a^(p−1) ≡ 1 (mod p)

여기서 두 가지가 바로 나온다.

• 큰 지수 줄이기: a^e ≡ a^(e mod φ(n)) (mod n) (gcd(a, n) = 1일 때).
• 소수 법의 역원: a⁻¹ ≡ a^(p−2) (mod p). 10⁹+7, 998244353 같은 소수를 법으로 쓰는 이유다. 조합 nCr mod p를 팩토리얼과 역원 팩토리얼로 O(1)에 구할 수 있다.

RSA는 n = pq, φ(n) = (p−1)(q−1)에서 ed ≡ 1 (mod φ(n))인 e, d를 고르고, 오일러 정리 덕분에 (m^e)^d ≡ m (mod n)이 성립하는 구조다. 페르마 소정리의 역은 성립하지 않으므로(카마이클 수) 소수 판정에는 밀러–라빈 같은 확률적 판정법을 쓴다.

고정 폭을 넘는 정수: 자릿수 묶음 덧셈

200만 자리 수처럼 64비트(long long, 최대 약 9.2 × 10¹⁸)에 들어가지 않는 수는 자릿수를 묶어 배열에 담고 초등학교 세로셈처럼 받아올림을 직접 처리한다.

1. 수를 문자열로 읽고 끝(일의 자리)부터 9자리씩 잘라 정수 배열에 담는다. 한 칸이 밑(base) 10⁹의 한 자리다. 끝부터 담아야 길이가 다른 수도 같은 인덱스가 같은 자리가 된다.
2. 같은 인덱스끼리 더하고 carry = 합 // 10⁹를 다음 칸으로 넘긴다. 칸에는 합 % 10⁹를 남긴다.
3. 마지막 받아올림이 남으면 칸을 하나 늘린다. 출력은 가장 높은 칸부터 하되, 두 번째 칸부터는 앞자리 0을 채워 9자리로 쓴다.

Python int, Java BigInteger, JavaScript BigInt 같은 임의 정밀도 정수가 내부에서 같은 일을 한다. CPython은 한 칸에 30비트(밑 2³⁰)를 쓴다.

정리

• 산술의 기본 정리(소인수분해의 유일성)가 gcd, 약수, φ 계산의 바탕이다.
• gcd는 유클리드 호제법으로 O(log n), 베주 계수와 모듈러 역원은 확장 유클리드로 구한다.
• 여러 수를 소인수분해할 때는 체로 가장 작은 소인수를 미리 기록한다.
• 모듈러 산술에서 나눗셈은 역원 곱셈이고, 역원은 서로소일 때만 있다. 소수 법이면 a^(p−2).
• 동시에 여러 나머지 조건이 걸리면 중국인의 나머지 정리, 큰 지수는 오일러 정리로 줄인다.
• 선형 합동 생성기는 모듈러 연산으로 난수를 흉내 내며, 시간을 시드로 쓴다. 예측 가능하므로 보안에는 쓰지 않는다.
• 64비트를 넘는 수는 자릿수를 묶어 배열에 담고 받아올림을 직접 처리한다.

관련 노트: 재귀 함수, 선형 점화식의 일반항, 빅오 표기법과 시간 복잡도, 인코딩·암호화·해시·토큰화와 디지털 서명, 순열과 조합