# 가산 난수 생성기 (Additive Random Number Generator, Additive RNG)

가산 난수 생성기(Additive RNG)는 수열의 앞선 값들 가운데 정해진 위치의 두 개(또는 그 이상)를 정수 덧셈으로 더해 다음 값을 만드는 의사난수 생성기입니다. 대표적인 형태는 X_n = (X_{n−24} + X_{n−55}) mod 2^w처럼 일정 간격(지연)의 값을 더하는 '가산 지연 피보나치 생성기'이며, 도널드 커누스의 『컴퓨터 프로그래밍의 예술』 2권에 소개되어 있습니다. 구조적으로는 XOR 대신 정수 덧셈을 쓰고 여러 비트 원소를 다루는 LFSR이라고 볼 수 있습니다.

## 자세히 알아보기

차수 n의 원시 다항식을 기반으로 하고 원소 폭이 w비트이면, 최하위 비트열은 보통의 LFSR과 같아 주기가 2^n − 1이고, 전체 수열은 최대 (2^n − 1)·2^(w−1)의 주기를 가집니다. 초기 원소 가운데 적어도 하나의 최하위 비트가 1이어야 한다는 조건만 지키면 초기화가 거의 자유롭고, 구현이 단순하며 소프트웨어에서 매우 빠릅니다. 이 때문에 몬테카를로 시뮬레이션, 게임, 통계 표본 추출 같은 분야에서 쓰였습니다.

'가산 합동 생성기'라고 부르기도 하지만 정확한 표현은 아니며, 선형 합동 생성기(X_{n+1} = aX_n + c mod m)와는 다른 계열입니다.

## 블록체인·암호화폐에서는

가산 난수 생성기는 암호용으로 쓰면 안 됩니다. 출력이 과거 출력들의 단순한 덧셈 관계를 가지므로, 연속 출력을 충분히 관찰하면 내부 상태 전체를 복원하고 이후 값을 예측할 수 있습니다. 최하위 비트는 순수한 선형 수열이어서 베를레캄프-매시 알고리즘으로 바로 분석됩니다. 리터는 이런 생성기에 비선형 결합기(예: 동적 치환)를 덧붙여 스트림 암호를 만들자고 제안했지만, 현대의 표준적 선택은 아닙니다.

개인 키, 니모닉, 서명 난스, 검증자 추첨, 온체인 게임 결과에는 운영체제의 암호학적 난수 생성기(getrandom, /dev/urandom 등)나 NIST SP 800-90A DRBG, 검증 가능한 난수(VRF) 같은 암호학적으로 안전한 생성기를 써야 합니다. 일반 프로그래밍 언어의 기본 난수 함수로 지갑 키를 만들었다가 자금을 잃은 사고가 반복되었습니다.

## 쉽게 말하면

앞에서 나온 숫자 두 개를 더해 다음 숫자를 만드는 빠른 숫자 뽑기 기계입니다. 빠르지만 규칙을 아는 사람에게는 다음 숫자가 보입니다.

## 예시

mod 10에서 X_n = (X_{n−1} + X_{n−2})로 시작값 1, 1을 두면 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, …가 나옵니다(아주 작은 장난감 예시이며 실제 생성기는 훨씬 긴 지연을 씁니다).

---
출처: https://achivx.kr/glossary/additive-random-number-generator-additive-rng-%EA%B0%80%EC%82%B0-%EB%82%9C%EC%88%98-%EC%83%9D%EC%84%B1%EA%B8%B0-%EA%B0%80%EC%82%B0-rng/ · ACHIVX 용어 사전 · 수정일 2026-10-20