간단한 난수 생성기, LCG에 관해서

C언어를 하면서, 난수 생성애 관한 정보를 찾아보다가,

LCG에 관한 내용을 보았고,

여기에 Visual Studio 2010에서 사용되는 인수도 나와있었어요~!

★ LCG란?? (출처 : Wikipedia 문서)

LCG = Linear Congruential Generator (직역 : 선형 합동 생성기)

가장 잘 알려진 난수 생성 방법 중 하나로, 재귀적으로 다음과 같이 정의됩니다.

X_n+1 = (aX_n+c) mod m

여기에서 Seed 값도 중요한데요, 쉽게 생각하시면, Seed = X₀이라고 생각하시면 됩니다.

컴파일러마다 다르겠지만, Visual Studio에서 사용되는 인수를 알려드리고자 해요~!

X_n+1 = (aX_n+c) mod m

※ 인수

m = 2³²

a = 214013 (0x343FD)

c = 2531011 (0x269EC3)

여기에서, 30~16번 bit 범위의 수를 반환하게 되는 것입니다.

(여기에서는 가장 오른쪽을 0번으로 하겠습니다.)

예시) 수식의 결과가 3,357,800,067인 경우

이를 2진수로 나타내면, 1100 1000 0010 0011 1111 0110 1000 0011이고,

위의 빨간 부분의 비트만을 사용하게 됩니다. (2진수로 15자리)

이를 다시 10진수로 표현하면 18467이 나오게 됩니다.

(또한, 2진수로 15자리 만을 사용하게 되므로, 난수의 범위는 0~32767이 나오게 되겠죠?)

하지만, 이 방법은 간단한 대신, Seed 값과 인수만 알고 있다면, 다음에 나오게 될 난수를 미리 예측할 수 있어서,

암호학적 보안상으로는 안전하지 않다고 합니다.

마지막으로, 제가 직접 Visual Studio에서 LCG를 구현해보았는데요,

참고용으로 소스 코드를 올려드릴게요~!

(혹시 오류가 있다면 지적 부탁드릴게요~!)

///////////////////////////////////////////////////
//
// 작성자 : DDManager
// 작성일 : 2019.03.30.
// 프로그램명 : LCG를 이용한 난수 생성기 구현
//
// <프로그램 설명>
// C언어에서 기본적으로 제공하는 난수 생성 함수를 직접 구현해보았음.
// Wikipedia의 LCG 관련 문서를 참조했음.
//
///////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>

// 반복 횟수 (필요에 따라 조정 가능)
#define LOOP 100

// 난수 생성을 위한 LCG 상수 (절대로 바꾸지 마세요!!)
#define MULT 0x343FD
#define INCR 0x269EC3

unsigned seed=1; // 난수의 초기(Seed) 값

// 직접 구현한 난수 생성 함수
int custom_rand(void){
	seed=seed*MULT+INCR;
	return (seed>>16)%32768;
}

int main(void){
	int rnd1,rnd2=0; // 생성된 난수
	int i; // 반복문 제어 변수
	printf("Seed 값을 입력하세요 : ");
	scanf("%d",&seed);
	srand(seed); // 난수 섞기
	for(i=0;i<LOOP;i++){ // 테스트를 위한 반복
		rnd1=rand(); // 라이브러리 함수
		rnd2=custom_rand(); // 직접 구현한 함수
		printf("%d\t%d\n",rnd1,rnd2); // 두 수를 출력 및 비교
	}
	return 0; // 프로그램 종료
}