선형 합동 생성기

2개의 모듈로-9 LCG는 파라미터에 따라 사이클 길이가 어떻게 달라지는지를 보여줍니다.각 행은 반복될 때까지 상태가 진화하고 있음을 나타냅니다.맨 위 행은 m = 9, a = 2, c = 0 및 길이 6의 주기를 생성하는 시드 1을 가진 생성기를 나타냅니다.두 번째 행은 시드 3과 동일한 생성기로, 길이가 2인 사이클을 생성합니다.a = 4 및 c = 1(맨 아래 행)을 사용하면 [0, 8]에 있는 시드와 함께 사이클 길이가 9가 됩니다.

Linear Congruential Generator(LCG; 선형 합동 생성기)는 불연속적인 부분 선형 방정식으로 계산된 의사 난수 시퀀스를 생성하는 알고리즘입니다.이 메서드는 가장 오래되고 가장 잘 알려진 의사 난수 생성 알고리즘 중 하나를 나타냅니다.이면에 있는 이론은 비교적 이해하기 쉽고, 특히 스토리지 비트 절단을 통해 모듈식 산수를 제공할 수 있는 컴퓨터 하드웨어에서 쉽게 구현되고 빠릅니다.

제너레이터는 반복 관계에 의해 정의됩니다.

X_{n+1}=\left(aX_{n}+c\right){\bmod {m}

$X$ 서 X $(\displaystyle$ X $)$ 는 $X$ 의사 랜덤 값의 시퀀스입니다.

m,\,0<m

, 0

m,\,0<m

<

m,\,0<m

\

displaystyle

m ,

0

<

m

}

m,\,0<m

: "계수"

a,\,0<a<m

0

a,\,0<a<m

<

a,\,0<a<m

<

a,\,0<a<m

\

displaystyle

a ,

0 < a

<

m

} :"더 큰"

c,\,0\leq c<m

,

c,\,0\leq c<m

c <

c,\,0\leq c<m

\

display

c , ,

0

\

leq

c <

m

}

c,\,0\leq c<m

: "display"

X_{0},\,0\leq X_{0}<m

0

X_{0},\,0\leq X_{0}<m

X_{0},\,0\leq X_{0}<m

†

X_{0},\,0\leq X_{0}<m

<

X_{0},\,0\leq X_{0}<m

{

displaystyle X

_ {

0

, ,

0

\

leq

X _ {

0

} <

m

} : "시드" 또는 "시작값"

생성기를 지정하는 정수 상수입니다.c = 0이면 종종 곱셈 합동 생성기(MCG) 또는 레머 RNG라고 합니다. c 0 0이면 혼합 합동 ^[1]^{: 4-}생성기라고 합니다.

c would 0일 때, 수학자는 반복을 선형 변환이 아닌 아핀 변환이라고 부르지만, 잘못된 이름은 컴퓨터 ^[2]^{: 1}과학에서 잘 확립되어 있다.

역사

레머 발전기는 1951년에^[3] 출판되었고 선형 합동 발전기는 1958년에 W. E. Thomson과 A에 의해 출판되었다.로텐버그.^[4]^[5]

기간 길이

LCG의 장점은 적절한 파라미터 선택으로 알려진 기간과 긴 기간이 모두 발생한다는 것입니다.유일한 기준은 아니지만 기간이 너무 짧은 것은 의사 난수 ^[6]생성기의 치명적인 결함입니다.

LCG는 난수의 정식 테스트를 통과할 수 있는 의사 난수를 생성할 수 있지만 출력 품질은 파라미터 m과 ^[7]^[1]^[8]^[9]^[10]^[2]a의 선택에 매우 민감합니다.예를 들어, a = 1 및 c = 1은 긴 주기를 가지지만 분명히 비순서인 단순 모듈로-m 카운터를 생성합니다.

지금까지 의 선택이 불충분하면 LCG의 실장이 비효율적이었습니다.특히 1970년대 초에 널리 사용되었던 LANDU를 예로 들 수 있는데, 이 부실한 LCG의 ^[11]사용으로 인해 현재 의문시되고 있다.

파라미터 선택에는 다음 세 가지 일반적인 패밀리가 있습니다.

m 소수, c = 0

이것은 원래 Lehmer RNG 구조입니다.승수 a가 정수 모듈로 m의 원시 원소로 선택되면 주기는 m-1이다.초기 상태는 1과 m-1 사이에서 선택해야 합니다.

소수계수의 단점 중 하나는 모듈식 축소를 위해서는 두 배의 폭 곱과 명시적인 축소가 필요하다는 것입니다.종종 2의 제곱보다 약간 작은 소수(메르센 소수 2-1과³¹ 2-1이 인기 있음⁶¹)를 사용하므로, 감소 모듈로 m^e = 2 - d는 (ax mod^e 2) + d /ax^e/2로 계산할 수 있다.결과가 너무 크면 m을 조건부 감산해야 하지만, 감산 횟수는 ad/m으로 제한되며, d가 작으면 1로 쉽게 제한될 수 있다.

배폭 제품을 사용할 수 없고 승수를 신중하게 선택할 경우 Schray의 방법을^[12] 사용할 수 있습니다.이를 위해 인자 m = q+r, 즉 q = µm/a' 및 r = m mod a를 선택합니다.그런 다음 ax mod m = a(x mod q) - rxx/q를 계산합니다.x mod q < q µ m/a이므로 첫 번째 항은 am/a = m보다 엄격히 작습니다.a가 r q(및 r/q 1 1)로 선택되면 두 번째 항도 m:r ⌊ rx / rx rx / q = x (r/q) x x < m보다 작아집니다.따라서 두 제품 모두 단일 폭 곱으로 계산할 수 있으며, 그 차이는 [1-m, m-1] 범위에 있으므로 단일 ^[13]조건부 덧셈으로 [0, m-1]로 줄일 수 있다.

두 번째 단점은 1µ x < m의 값을 균일한 랜덤비트로 변환하는 것이 어색하다는 것입니다.2의 거듭제곱보다 약간 작은 소수가 사용되는 경우 결측값이 단순히 무시될 수 있습니다.

m의 거듭제곱은 2, c = 0

m을 2의 거듭제곱(대부분 m = 2³² 또는 m = 2⁶⁴)으로 선택하면 계수 연산을 단순히 이항 표현만 잘라서 계산할 수 있으므로 특히 효율적인 LCG가 생성됩니다.실제로 최상위 비트는 일반적으로 전혀 계산되지 않습니다.단, 단점도 있습니다.

이 형식은 최대 주기 m/4를 가지며, 3 3 또는 5 5(mod 8)일 경우 달성됩니다.초기 상태₀ X는 홀수여야 하며 X의 하위 3비트는 2개의 상태를 번갈아 나타내므로 유용하지 않습니다.이 형태는 계수가 4분의 1이고 c ^[1]≠ 0인 발전기와 동등하다는 것을 알 수 있다.

2승률의 곱셈을 사용할 때 더 심각한 문제는 낮은 비트의 주기가 높은 비트에 비해 짧다는 것입니다.X의 최하위 비트는 변경되지 않으며(X는 항상 홀수), 다음 2비트는 2개의 상태를 번갈아 사용합니다.(if 5(mod 8)의 경우 비트1은 변경되지 않고 비트2가 번갈아 바뀝니다.3 3(mod 8)일 경우 비트2는 변경되지 않고 비트1이 번갈아 바뀝니다.비트 3은 4의 주기로 반복되며 비트4는 8의 주기로 반복됩니다.X의 최상위 비트만이 전체 주기를 달성합니다.

c 0 0

c 0 0인 경우 파라미터를 올바르게 선택하면 모든 시드 값에 대해 m과 같은 기간이 허용됩니다.이 문제는 다음과 ^[1]^{: 17—19}같은 경우에만 발생합니다.

$m$ { $display style$ m}과 $m$ c { $display style$ c $}$ 는 $c$ 비교적 소수입니다.
$a-1$ - 1 $(디스플레이$ 스타일 $a-1)$ 은 $a-1$ m $(디스플레이 스타일$ m $m$ 의 모든 소수 인수로 나눌 수 있다.
$a-1$ $a$ $a-1$ - 1 $(디스플레이$ 스타일 $a-1)$ 은 $a-1$ m $(디스플레이 스타일$ m $)$ 이 $m$ 4로 나누어지면 4로 나누어집니다.

이 세 가지 요건을 헐-도벨 ^[14]^[15]정리라고 한다.

이 형식은 임의의 m과 함께 사용할 수 있지만, 2의 거듭제곱과 같이 많은 소수 인수가 있는 m에서만 잘 작동합니다. 컴퓨터의 단어 크기를 사용하는 것이 가장 일반적인 선택입니다.m이 제곱이 없는 정수일 경우 이는 µ 1(mod m)만 허용하므로 PRNG가 매우 불량하다. 가능한 전체 주기 승수는 m이 소수 계수를 반복하는 경우에만 선택할 수 있다.

헐-도벨 정리가 최대 주기를 제공하지만 좋은 발전기를 보장하는 것은 충분하지 않습니다.예를 들어 a - 1은 필요 이상으로 m의 소수 인수로 나누어지지 않는 것이 바람직하다.따라서 m이 2의 거듭제곱인 경우 a - 1은 4로 나누어지지만 8로 나누어서는 안 된다. 즉, a - 5(mod 8)^[1]^{: §3.2.1.3}이다.

실제로, 대부분의 곱셈기는 비랜덤성 또는 다른 테스트에 불합격하는 시퀀스를 생성하며, 모든 적용^[1]^{: §3.3.3} 가능한 기준에 만족하는 곱셈기를 찾는 것은 매우 어렵다.스펙트럼 테스트는 가장 중요한 테스트 ^[16]중 하나입니다.

계수 2의 거듭제곱은 c = 0에 대해 위에서 설명한 것과 같은 문제를 공유합니다. 낮은 k비트는 계수^k 2의 제너레이터를 형성하고 따라서 주기 2를^k 반복하며, 최상위 비트만 전체 주기를 달성합니다.r보다 작은 의사 난수가 필요한 경우 "rX/m"은 X mod r보다 훨씬 높은 품질의 결과입니다.유감스럽게도 대부분의 프로그래밍 언어는 후자를 훨씬 쓰기 쉽게 만듭니다.X % r더 일반적으로 사용되는 형식입니다.

발생기는 계수(예를 들어 m이 2의 거듭제곱이면 c가 홀수여야 함)에 비해 상대적으로 소수인 한 c의 선택에 민감하지 않으므로 일반적으로 c=1 값이 선택됩니다.

c의 다른 선택들에 의해 생성된 급수는 c=^[1]^{: 11}1일 때 급수의 단순한 함수로 쓸 수 있다.구체적으로 Y가 Y = 0 및_n+1 Y = aY_n+1 mod m으로 정의된₀ 시제품 계열이라면 일반 계열_n+1 X = aX_n+c mod m은 Y의 아핀 함수로 쓸 수 있습니다.

X_{n}=(X_{0}(a-1)+c)Y_{n}+X_{0}=(X_{1}-X_{0})Y_{n}+X_{0}{\pmod {m}}.

보다 일반적으로 승수와 계수가 동일한 두 계열 X와 Z는 다음과 같이 관련된다.

{X_{n}-X_{0}\over X_{1}-X_{0}=Y_{n}={a^{n}-1 \over a-1}={Z_{n}-Z_{0} \over Z_{1}-Z_{0}{\pmod {m}}.

일반적으로 사용되는 파라미터

다음 표는 다양한 컴파일러의 런타임라이브러리에 내장된 rand() 함수를 포함하여 일반적으로 사용되는 LCG의 파라미터를 나타내고 있습니다.이 표는 인기를 나타내는 것이지 에뮬레이트할 예는 아닙니다.이들 파라미터의 대부분은 빈약합니다.양호한 파라미터의 표를 사용할 ^[10]^[2]수 있습니다.

원천	계수 m	승수 a	증량 c	rand() 또는 Random(L)의 시드 출력 비트
ZX81	2¹⁶ + 1	75	74
수치 레시피	2개³²	1664525	1013904223
볼랜드 C/C++	2개³²	22695477	1	비트 30..16 in rand .. 30 . 0 in land()
glibc(GCC에서 ^[17]사용)	2개³¹	1103515245	12345	비트 30..0
ANSI C: Watcom, 디지털 Mars, CodeWarrior, IBM VisualAge C/C++^[18] C90, C99, C11: ISO/IEC 9899,^[19] C17에서의 제안	2개³¹	1103515245	12345	비트 30..16
Borland Delphi, 버추얼	2개³²	134775813	1	비트 63..32/(시드×L)
터보 파스칼	2개³²	134775813(8088405₁₆)	1
Microsoft Visual/Quick C/C++	2개³²	214013 (343FD₁₆)	2531011 (269EC3₁₆)	비트 30..16
Microsoft Visual Basic (6 이전)^[20]	$224$	1140671485(43FD43FD)₁₆	12820163 (C39EC3₁₆)
네이티브^[21] API의 Rtl Uniform	2³¹ − 1	2147483629 (7FFFFED₁₆)	2147483587(7FFFFC3₁₆)
Apple CarbonLib, C++11's`minstd_rand0`,^[22] MATLAB의 v4 레거시 제너레이터 mcg16807^[23]	2³¹ − 1	16807	0	"MNSTD" 참조
C++11의`minstd_rand`^[22]	2³¹ − 1	48271	0	"MNSTD" 참조
MMIX (도날드 크누스)	2개⁶⁴	6364136223846793005	1442695040888963407
뉴리브, Musl	2개⁶⁴	6364136223846793005	1	비트 63..32
VMS의 MTH$RANDOM,^[24] 이전 버전의 glibc	2개³²	69069 (10DCD₁₆)	1
Java의 java.util.랜덤, POSIX [ln]rand48, glibc [ln]rand48[_r]	2개⁴⁸	25214903917 (5DEECE66D₁₆)	11	비트 47..16
`random0`^[25]^[26]^[27]^[28]^[29]	134456 = 27³⁵	8121	28411	${X_{n}} {134456}$
POSIX^[30] [jm]rand48, glibc [mj]rand48 [_r]	2개⁴⁸	25214903917 (5DEECE66D₁₆)	11	비트 47..15
POSIX [de]rand48, glibc [de]rand48 [_r]	2개⁴⁸	25214903917 (5DEECE66D₁₆)	11	비트 47..0
cc65^[31]	2개²³	65793 (10101₁₆)	4282663 (415927₁₆)	비트 22..8
cc65	2개³²	16843009 (10101₁₆)	826366247 (31415927₁₆)	비트 31..16
이전 공통: 랜두^[11]	2개³¹	65539	0

위와 같이 LCG가 항상 생성되는 값의 모든 비트를 사용하는 것은 아닙니다.예를 들어 Java 실장은 반복할 때마다 48비트 값으로 동작하지만 최상위 32비트만 반환합니다.이는 고차 비트가 저차 비트보다 주기가 길기 때문입니다(아래 참조).이 잘라내기 기술을 사용하는 LCG는 사용하지 않는 LCG보다 통계적으로 더 좋은 값을 산출합니다.이는 특히 범위를 줄이기 위해 mod 조작을 사용하는 스크립트에서 두드러집니다.랜덤 번호 mod 2를 변경하면 0과 1이 번갈아 가며 자릅니다.

장점과 단점

LCG는 고속으로 상태를 유지하기 위해 최소한의 메모리(1 modulo-m 수치, 많은 경우 32비트 또는 64비트)가 필요합니다.이를 통해 여러 개의 독립 스트림을 시뮬레이션하는 데 유용합니다.LCG는 암호화 어플리케이션용으로 의도된 것이 아닙니다.사용해서는 안 됩니다.이러한 어플리케이션에는 암호화로 보호된 의사난수 생성기를 사용합니다.

선형 합동 생성기의 3차원 하이퍼플레인입니다.이 구조는 스펙트럼 테스트에서 측정하는 것이다.

LCG에는 몇 가지 특정한 약점이 있지만, 그 결함의 대부분은 너무 작은 상태에서 비롯됩니다.오랜 세월 소강상태에 빠진 사람들이 이런 작은 모듈리로 그것들을 사용한다는 것은 그 기술의 강점을 증명하는 것으로 볼 수 있다.스테이트가 충분히 큰 LCG는 엄격한 통계 테스트에도 합격할 수 있습니다.상위 32비트를 반환하는 모듈로-2 LCG는 TestU01의 SmallCrush ^{[citation needed]}스위트에 합격하고 96비트 LCG는 가장 엄격한 BigCrush ^[32]스위트에 합격합니다.

특정 예에서는 (생일 정리에 따라) 32비트의 출력을 가진 이상적인 난수 발생기가 $µm 16$ ≤ 2의 결과 후에 이전 출력의 복제를 시작할 것으로 예상된다.출력이 완전하고 절단되지 않은 상태인 PRNG는 전체 기간이 경과할 때까지 중복이 발생하지 않으며 이는 쉽게 검출할 수 있는 통계 결함입니다.관련된 이유로 PRNG는 필요한 출력 수의 제곱보다 긴 기간을 가져야 합니다.최신 컴퓨터 속도를 고려하면, 이는 가장 요구가 적은 애플리케이션을 제외한 모든 애플리케이션에 대해 2의 기간을⁶⁴ 의미하며, 요구가 까다로운 시뮬레이션에는 더 긴 기간을 의미합니다.

LCG 고유의 단점은 n차원 공간에서 점을 선택하기 위해 사용할 경우, 그 점이 최대 $" n!" m$ 하이퍼플레인 (George Marsaglia에 ^[7]의해 개발된 Marsaglia의 정리)에 놓여 있다는 것입니다.이는 시퀀스_n X의 연속된 값 사이의 시리얼 상관에 의한 것입니다.부주의하게 선택된 승수는 일반적으로 훨씬 적은 수의 넓은 간격을 가지므로 문제가 발생할 수 있습니다.LCG 품질에 대한 간단한 테스트인 스펙트럼 테스트는 이 간격을 측정하여 양호한 승수를 선택할 수 있도록 한다.

평면 간격은 계수 및 승수에 따라 달라집니다.계수가 충분히 크면 이 거리가 2배 정밀도 수치 분해능 이하로 줄어들 수 있습니다.승수의 선택은 계수가 클수록 덜 중요해집니다.스펙트럼 지수를 계산하고 곱셈기가 나쁜 곱셈기가 아님을 확인하는 것이 여전히 필요하지만, 순전히 확률적으로 계수가⁶⁴ 약 2보다 클 때 나쁜 곱셈기를 만날 가능성은 극히 낮다.

LCG에 고유한 또 다른 결함은 m을 2의 거듭제곱으로 선택할 때 하위 비트의 기간이 짧다는 것입니다.이는 필요한 출력보다 큰 계수를 사용하고 상태의 최상위 비트를 사용함으로써 완화할 수 있습니다.

단, 어플리케이션에 따라서는 LCG가 좋은 옵션이 될 수 있습니다.예를 들어 임베디드 시스템에서는 사용 가능한 메모리 용량이 크게 제한되어 있는 경우가 많습니다.마찬가지로 비디오 게임 콘솔과 같은 환경에서는 LCG의 상위 비트 수가 적은 것으로 충분합니다.(m이 2의 거듭제곱일 때 LCG의 하위 비트는 어떤 랜덤성에도 의존하지 마십시오).하위 비트는 매우 짧은 사이클을 거칩니다.특히 m이 2의 거듭제곱일 때 모든 풀사이클 LCG는 홀수 결과와 짝수 결과를 번갈아 생성합니다.

LCG는 고품질 랜덤성이 중요한 비암호화 애플리케이션에서의 적합성에 대해 매우 신중하게 평가해야 합니다.몬테카를로 시뮬레이션의 경우, LCG는 필요한 랜덤 샘플 수의 세제곱보다 훨씬 큰 계수를 사용해야 합니다.즉, 예를 들어 (좋은) 32비트 LCG를 사용하여 약 1,000개의 난수를 얻을 수 있습니다.64비트 LCG는 약 2개의²¹ 랜덤샘플(200만 개 조금 넘음)에 적합합니다.이러한 이유로 실제로 LCG는 대규모 몬테카를로 시뮬레이션에 적합하지 않다.

샘플코드

파이썬 코드

다음은 생성기 형태로 Python에서 LCG를 구현한 것입니다.

부터 collections.displicate 수입품 발전기  방어하다 lcg(계수: 인트, a: 인트, c: 인트, 씨를 뿌리다: 인트) -> 발전기[인트, 없음., 없음.]:     "선형 합동 생성기."""     하는 동안에 진실의:         씨를 뿌리다 = (a * 씨를 뿌리다 + c) % 계수         산출하다 씨를 뿌리다

프리 파스칼

Free Pascal은 기본 의사 난수 생성기로 Mersenne Twister를 사용하는 반면, Delphi는 LCG를 사용합니다.위 표의 정보를 기반으로 한 Free Pascal의 Dellphi 호환 예를 다음에 나타냅니다.동일한 RandSeed 값을 지정하면 Delphi와 동일한 난수 시퀀스가 생성됩니다.

구성 단위 lcg_module; {$ifdef fpc} {$mode delphi} {$endif} 인터페이스  기능. LC Grandom: 확장된; 과부하; 인라인; 기능. LC Grandom(컨스턴트 범위:롱인트): 롱인트; 과부하; 인라인;  실행 기능. IM: 주요; 인라인; 시작한다.   랜드시드 := 랜드시드 * 134775813 + 1;   결과 := 랜드시드; 끝.;  기능. LC Grandom: 확장된; 과부하; 인라인; 시작한다.   결과 := IM * 2.32830643653870e-10; 끝.;  기능. LC Grandom(컨스턴트 범위: 롱인트): 롱인트; 과부하; 인라인; 시작한다.   결과 := IM * 범위 날카롭게 하다 32; 끝.;

모든 의사 난수 생성기와 마찬가지로 LCG는 상태를 저장하고 새로운 번호를 생성할 때마다 변경해야 합니다.여러 스레드가 동시에 이 상태에 액세스하여 레이스 상태가 될 수 있습니다.구현에서는 동시에 실행되는 스레드에서 동일한 난수의 시퀀스를 피하기 위해 서로 다른 스레드에 대해 고유한 초기화 상태에서 각각 다른 상태를 사용해야 합니다.

LCG 파생상품

다른 형태의 선형 합동 생성기인 여러 개의 생성기가 있으므로 LCG 분석에 사용되는 기술을 적용할 수 있습니다.

보다 긴 기간을 생성하는 한 가지 방법은 가장 낮은 공통 배수를 갖는 서로 다른 기간의 여러 LCG의 출력을 합산하는 것이다. 비흐만-힐 발생기는 이러한 형태의 한 예이다(완전 공수기를 선호하지만, 소수 계수는 짝수 기간을 의미하므로 적어도 2의 공통 계수가 있어야 한다).이는 컴포넌트 LCG 모듈리의 곱과 동일한 계수를 갖는 단일 LCG와 동등함을 나타낼 수 있습니다.

단어 크기가 b=2이고^w 지연 r과 s(r > s)가 b ± b^s ± ^[33]^[34]1인^r LCG와 같다.

승수가 a인 Multi-with-carry PRNG는 큰 소수계수 ab-1^r 및 2승수 b의 LCG와 동등하다.

치환된 합동 생성기는 2승 LCG에서 시작하여 하위 비트의 단주기 문제를 제거하기 위해 출력 변환을 적용합니다.

다른 PRNG와의 비교

장주기 의사랜덤 시퀀스를 얻기 위해 널리 사용되는 또 다른 프리미티브는 선형 피드백 시프트 레지스터 구조이며, 이는 GF(2)[x] 위의 다항식 링인 GF(2)[x]의 산술에 기초한다.정수의 덧셈과 곱셈이 아니라, 기본 연산은 배타적 또는 이월 없는 곱셈이며, 이는 보통 일련의 논리적 시프트로 구현됩니다.이들 비트는 모두 풀주기라는 장점이 있습니다.산술모듈로2를^k ^[35]괴롭히는 하위 비트의 취약성에 시달리지 않습니다.

이 과의 예로는 엑스시프트 발생기와 메르센 트위스터가 있다.후자는 매우 긴 기간(2-1¹⁹⁹³⁷)과 가변 균일성을 제공하지만 일부 통계적 ^[36]테스트에 실패합니다.Lagged Fibonacci 제너레이터도 이 범주에 속합니다.연산 덧셈을 사용하지만 이들 주기는 최하위 비트 중 LFSR에 의해 보증됩니다.

TestU01 제품군에 구현된 선형 복잡도 테스트와 같은 적절한^[37] 테스트를 통해 선형 피드백 시프트 레지스터의 구조를 쉽게 감지할 수 있습니다. LFSR의 연속 비트에서 초기화된 부울 순환 행렬은 결코 다항식보다 높은 순위를 갖지 않습니다.비선형 출력 혼합 함수(xoshiro256** 및 순열 합동 생성기 구성 등)를 추가하면 통계 테스트의 성능을 크게 향상시킬 수 있습니다.

PRNG의 또 다른 구조는 강력한 출력 혼합 기능과 결합된 매우 단순한 반복 함수입니다.여기에는 카운터 모드 블록 암호 및 SplitMix64 등의 비암호 생성기가 포함됩니다.

LCG와 유사하지만 동등하지 않은 구조는 다원발생기이다.k_n x2의 X = (aX₁_n−1 + aX₂_n−2 + · · + aX_k_n−k) mod m. 소수계수를 사용하면 m-1까지의^k 주기를 발생시킬 수 있으므로 LCG 구조를 더 큰 주기로 확장하는 것이 유용하다.

고품질의 의사 난수를 생성하는 강력한 기술은 서로 다른 구조의 PRNG를 2개 이상 조합하는 것입니다.LFSR과 LCG의 합계(KISS 또는 xorwow 구성 등)는 어느 정도의 비용으로 고속화할 수 있습니다.

「」를 참조해 주세요.

난수 생성기 목록 – 통계적 적격성이 더 뛰어난 PRNG를 포함한 기타 PRNG
ACON 제너레이터– ACG와 혼동하지 마십시오.ACG는 LCG와 LFSR 제너레이터의 변형에 사용된 것으로 보입니다.
치환 합동 생성기
풀 사이클
반전 합동 생성기
멀티플 위드 캐리
레메르 RNG(일명 파크-밀러 RNG)
복합 선형 합동 생성기

메모들

^ ^a ^b ^c ^d ^e ^f ^g Knuth, Donald (1997). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Reading, MA: Addison-Wesley Professional. pp. 10–26.
^ ^a ^b ^c Steele, Guy; Vigna, Sebastiano (15 January 2020). "Computationally easy, spectrally good multipliers for congruential pseudorandom number generators". arXiv:2001.05304 [cs.DS]. At this point it is unlikely that the now-traditional names will be corrected. 계산의 수학(등장 예정).관련 데이터는 https://github.com/vigna/CPRNG에서 확인할 수 있습니다.
^ Lehmer, Derrick H. (1951). "Mathematical methods in large-scale computing units". Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery: 141–146.
^ Thomson, W. E. (1958). "A Modified Congruence Method of Generating Pseudo-random Numbers". The Computer Journal. 1 (2): 83. doi:10.1093/comjnl/1.2.83.
^ Rotenberg, A. (1960). "A New Pseudo-Random Number Generator". Journal of the ACM. 7 (1): 75–77. doi:10.1145/321008.321019. S2CID 16770825.
^ L'Ecuyer, Pierre (13 July 2017). Chan, W. K. V.; D'Ambrogio, A.; Zacharewicz, G.; Mustafee, N.; Wainer, G.; Page, E. (eds.). History of Uniform Random Number Generation (PDF). Proceedings of the 2017 Winter Simulation Conference (to appear). Las Vegas, United States. hal-01561551.
^ ^a ^b Marsaglia, George (September 1968). "Random Numbers Fall Mainly in the Planes" (PDF). PNAS. 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi:10.1073/pnas.61.1.25. PMC 285899. PMID 16591687.
^ Park, Stephen K.; Miller, Keith W. (October 1988). "Random Number Generators: Good Ones Are Hard To Find" (PDF). Communications of the ACM. 31 (10): 1192–1201. doi:10.1145/63039.63042. S2CID 207575300.
^ Hörmann, Wolfgang; Derflinger, Gerhard (1993). "A Portable Uniform Random Number Generator Well Suited for the Rejection Method" (PDF). ACM Transactions on Mathematical Software. 19 (4): 489–495. CiteSeerX 10.1.1.52.3811. doi:10.1145/168173.168414. S2CID 15238956. a multiplier about as small as √m, produces random numbers with a bad one-dimensional distribution.
^ ^a ^b L'Ecuyer, Pierre (1999). "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure". Mathematics of Computation. 68 (225): 249–260. Bibcode:1999MaCom..68..249L. CiteSeerX 10.1.1.34.1024. doi:10.1090/S0025-5718-99-00996-5. 에라타도 꼭 읽어주세요.
^ ^a ^b Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed.). ISBN 978-0-521-43064-7.
^ Jain, Raj (9 July 2010). "Computer Systems Performance Analysis Chapter 26: Random-Number Generation" (PDF). pp. 19–20. Retrieved 2017-10-31.
^ Fenerty, Paul (11 September 2006). "Schrage's Method". Retrieved 2017-10-31.
^ Hull, T. E.; Dobell, A. R. (July 1962). "Random Number Generators" (PDF). SIAM Review. 4 (3): 230–254. Bibcode:1962SIAMR...4..230H. doi:10.1137/1004061. hdl:1828/3142. Retrieved 2016-06-26.
^ Severance, Frank (2001). System Modeling and Simulation. John Wiley & Sons, Ltd. p. 86. ISBN 978-0-471-49694-6.
^ Austin, David (March 2008). "Random Numbers: Nothing Left to Chance". American Mathematical Society.
^ glibc-2.26 릴리즈에서의 실장."TYPE_0" 테스트 후 코드를 참조하십시오. stdlib.h에 있는 GNU C 라이브러리의 rand()는 상태가 8바이트로 선언된 경우에만 단순한(싱글 상태) 선형 합동 생성기를 사용합니다.상태가 클 경우(어레이), 발생기는 가산 피드백 발생기(minstd_rand0을 사용하여 초기화)가 되어 주기가 증가한다.이 라이브러리의 랜덤 시퀀스를 재현하는 간이 코드를 참조해 주세요.
^ K. Entacher (21 August 1997). A collection of selected pseudorandom number generators with linear structures. CiteSeerX 10.1.1.53.3686. Retrieved 16 June 2012.
^ "Last public Committee Draft from April 12, 2011" (PDF). p. 346f. Retrieved 21 Dec 2014.
^ "How Visual Basic Generates Pseudo-Random Numbers for the RND Function". Microsoft. 24 June 2004. Archived from the original on 21 July 2020. Retrieved 17 June 2011.
^ MSDN에 관한 문서에도 불구하고 RtlUniform은 LCG를 사용하지만 Lemer 알고리즘이 아닌 Windows Vista 이전의 구현은 결함이 있습니다.이는 곱셈 결과가 모듈로를 적용하기 전에 32비트로 줄어들기 때문입니다.
^ ^a ^b "ISO/IEC 14882:2011". ISO. 2 September 2011. Retrieved 3 September 2011.
^ "Creating and Controlling a Random Number Stream". MathWorks. Retrieved 7 June 2021.
^ "GNU Scientific Library: Other random number generators".
^ 스티븐 채프먼입니다"예 6.4 – 난수 발생기""엔지니어를 위한 MATLAB 프로그래밍", 2015. 페이지 253-256.
^ 스티븐 채프먼입니다"예 6.4 – 난수 발생기""엔지니어를 위한 애플리케이션을 사용한 MATLAB 프로그래밍", 2012. 페이지 292–295.
^ S. J. 채프먼 랜덤 02004.
^ 스티븐 채프먼입니다"포트란 90/95 소개", 1998. 페이지 322–324.
^ 우팅차이"모듈: 현대 포트란의 주요 특징." 페이지 6-7.
^ 오픈 그룹 베이스 사양 제7호 IEEE 규격 1003.1, 2013년판
^ Cadot, Sidney. "rand.s". cc65. Retrieved 8 July 2016.
^ O'Neill, Melissa E. (5 September 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. pp. 6–7. HMC-CS-2014-0905.
^ Tezuka, Shu; L'Ecuyer, Pierre (October 1993). On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators (PDF). Workshop on Stochastic Numerics. Kyoto University.
^ Tezuka, Shi; L'Ecuyer, Pierre (December 1992). Analysis of Add-with-Carry and Subtract-with-Borrow Generators (PDF). Proceedings of the 1992 Winter Simulation Conference. pp. 443–447.
^ Gershenfeld, Neil (1999). "Section 5.3.2: Linear Feedback". The Nature of Mathematical Modeling (First ed.). Cambridge University Press. p. 59. ISBN 978-0-521-57095-4.
^ Matsumoto, Makoto; Nishimura, Takuji (January 1998). "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator" (PDF). ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995. S2CID 3332028. Archived from the original (PDF) on 2017-11-07.
^ Eastlake, Donald E. 3rd; Schiller, Jeffrey I.; Crocker, Steve (June 2005). "Traditional Pseudo-random Sequences". Randomness Requirements for Security. IETF. sec. 6.1.3. doi:10.17487/RFC4086. BCP 106. RFC 4086.

레퍼런스

Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 7.1.1. Some History", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
젠틀, 제임스 E. (2003)난수 생성 및 몬테카를로 방법, 제2판, 스프링어, ISBN 0-387-00178-6.
Joan Boyar (1989). "Inferring sequences produced by pseudo-random number generators" (PDF). Journal of the ACM. 36 (1): 129–141. doi:10.1145/58562.59305. S2CID 3565772. (이 백서에서는, 특정의 의사 주파수 발생기에 의해서 생성된 시퀀스를 추론하기 위한 효율적인 알고리즘이 제시되고 있다.

외부 링크

시뮬레이션 선형 합동 생성기는 매개 변수를 조작할 때 의사 난수 사이의 상관 관계를 시각화합니다.
난수 생성 보안:주석이 달린 참고 문헌
sci.math에 게시된 선형 합동 생성기
Goldstein Technologies LLC의 "Death of Art" 컴퓨터 아트 프로젝트는 LCG를 사용하여 33,554,432개의 이미지를 생성합니다.
P. L'Ecuyer와 R.Simard, "TestU01: 랜덤 번호 생성기의 경험적 테스트를 위한 C 라이브러리", 2006년 5월 개정, 2006년 11월, ACM Transactions on Mathemical Software, 33, 4, 제22조, 2007년 8월.
LCG를 크래킹하는 다른 방법에 대한 기사

[KnuthV2-1] ^ ^a ^b ^c ^d ^e ^f ^g Knuth, Donald (1997). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Reading, MA: Addison-Wesley Professional. pp. 10–26.

[Steele20-2] Steele, Guy; Vigna, Sebastiano (15 January 2020). "Computationally easy, spectrally good multipliers for congruential pseudorandom number generators". arXiv:2001.05304 [cs.DS]. At this point it is unlikely that the now-traditional names will be corrected. 계산의 수학(등장 예정).관련 데이터는 https://github.com/vigna/CPRNG에서 확인할 수 있습니다.

[3] Lehmer, Derrick H. (1951). "Mathematical methods in large-scale computing units". Proceedings of 2nd Symposium on Large-Scale Digital Calculating Machinery: 141–146.

[4] Thomson, W. E. (1958). "A Modified Congruence Method of Generating Pseudo-random Numbers". The Computer Journal. 1 (2): 83. doi:10.1093/comjnl/1.2.83.

[5] Rotenberg, A. (1960). "A New Pseudo-Random Number Generator". Journal of the ACM. 7 (1): 75–77. doi:10.1145/321008.321019. S2CID 16770825.

[History-6] L'Ecuyer, Pierre (13 July 2017). Chan, W. K. V.; D'Ambrogio, A.; Zacharewicz, G.; Mustafee, N.; Wainer, G.; Page, E. (eds.). History of Uniform Random Number Generation (PDF). Proceedings of the 2017 Winter Simulation Conference (to appear). Las Vegas, United States. hal-01561551.

[Marsaglia68-7] Marsaglia, George (September 1968). "Random Numbers Fall Mainly in the Planes" (PDF). PNAS. 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi:10.1073/pnas.61.1.25. PMC 285899. PMID 16591687.

[Park88-8] Park, Stephen K.; Miller, Keith W. (October 1988). "Random Number Generators: Good Ones Are Hard To Find" (PDF). Communications of the ACM. 31 (10): 1192–1201. doi:10.1145/63039.63042. S2CID 207575300.

[Hörmann92-9] Hörmann, Wolfgang; Derflinger, Gerhard (1993). "A Portable Uniform Random Number Generator Well Suited for the Rejection Method" (PDF). ACM Transactions on Mathematical Software. 19 (4): 489–495. CiteSeerX 10.1.1.52.3811. doi:10.1145/168173.168414. S2CID 15238956. a multiplier about as small as √m, produces random numbers with a bad one-dimensional distribution.

[LEcuyer99-10] L'Ecuyer, Pierre (1999). "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure". Mathematics of Computation. 68 (225): 249–260. Bibcode:1999MaCom..68..249L. CiteSeerX 10.1.1.34.1024. doi:10.1090/S0025-5718-99-00996-5. 에라타도 꼭 읽어주세요.

[Press-11] Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed.). ISBN 978-0-521-43064-7.

[12] Jain, Raj (9 July 2010). "Computer Systems Performance Analysis Chapter 26: Random-Number Generation" (PDF). pp. 19–20. Retrieved 2017-10-31.

[13] Fenerty, Paul (11 September 2006). "Schrage's Method". Retrieved 2017-10-31.

[14] Hull, T. E.; Dobell, A. R. (July 1962). "Random Number Generators" (PDF). SIAM Review. 4 (3): 230–254. Bibcode:1962SIAMR...4..230H. doi:10.1137/1004061. hdl:1828/3142. Retrieved 2016-06-26.

[HullDobell-15] Severance, Frank (2001). System Modeling and Simulation. John Wiley & Sons, Ltd. p. 86. ISBN 978-0-471-49694-6.

[Austin2008-16] Austin, David (March 2008). "Random Numbers: Nothing Left to Chance". American Mathematical Society.

[17] -2.26 릴리즈에서의 실장."TYPE_0" 테스트 후 코드를 참조하십시오. stdlib.h에 있는 GNU C 라이브러리의 rand()는 상태가 8바이트로 선언된 경우에만 단순한(싱글 상태) 선형 합동 생성기를 사용합니다.상태가 클 경우(어레이), 발생기는 가산 피드백 발생기(minstd_rand0을 사용하여 초기화)가 되어 주기가 증가한다.이 라이브러리의 랜덤 시퀀스를 재현하는 간이 코드를 참조해 주세요.

[18] K. Entacher (21 August 1997). A collection of selected pseudorandom number generators with linear structures. CiteSeerX 10.1.1.53.3686. Retrieved 16 June 2012.

[19] "Last public Committee Draft from April 12, 2011" (PDF). p. 346f. Retrieved 21 Dec 2014.

[20] "How Visual Basic Generates Pseudo-Random Numbers for the RND Function". Microsoft. 24 June 2004. Archived from the original on 21 July 2020. Retrieved 17 June 2011.

[21] MSDN에 관한 문서에도 불구하고 RtlUniform은 LCG를 사용하지만 Lemer 알고리즘이 아닌 Windows Vista 이전의 구현은 결함이 있습니다.이는 곱셈 결과가 모듈로를 적용하기 전에 32비트로 줄어들기 때문입니다.

[cpp11-22] "ISO/IEC 14882:2011". ISO. 2 September 2011. Retrieved 3 September 2011.

[23] "Creating and Controlling a Random Number Stream". MathWorks. Retrieved 7 June 2021.

[24] "GNU Scientific Library: Other random number generators".

[25] 스티븐 채프먼입니다"예 6.4 – 난수 발생기""엔지니어를 위한 MATLAB 프로그래밍", 2015. 페이지 253-256.

[26] 스티븐 채프먼입니다"예 6.4 – 난수 발생기""엔지니어를 위한 애플리케이션을 사용한 MATLAB 프로그래밍", 2012. 페이지 292–295.

[27] S. J. 채프먼 랜덤 02004.

[28] 스티븐 채프먼입니다"포트란 90/95 소개", 1998. 페이지 322–324.

[29] 우팅차이"모듈: 현대 포트란의 주요 특징." 페이지 6-7.

[30] 오픈 그룹 베이스 사양 제7호 IEEE 규격 1003.1, 2013년판

[31] Cadot, Sidney. "rand.s". cc65. Retrieved 8 July 2016.

[32] O'Neill, Melissa E. (5 September 2014). PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (Technical report). Harvey Mudd College. pp. 6–7. HMC-CS-2014-0905.

[33] Tezuka, Shu; L'Ecuyer, Pierre (October 1993). On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators (PDF). Workshop on Stochastic Numerics. Kyoto University.

[34] Tezuka, Shi; L'Ecuyer, Pierre (December 1992). Analysis of Add-with-Carry and Subtract-with-Borrow Generators (PDF). Proceedings of the 1992 Winter Simulation Conference. pp. 443–447.

[35] Gershenfeld, Neil (1999). "Section 5.3.2: Linear Feedback". The Nature of Mathematical Modeling (First ed.). Cambridge University Press. p. 59. ISBN 978-0-521-57095-4.

[36] Matsumoto, Makoto; Nishimura, Takuji (January 1998). "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator" (PDF). ACM Transactions on Modeling and Computer Simulation. 8 (1): 3–30. CiteSeerX 10.1.1.215.1141. doi:10.1145/272991.272995. S2CID 3332028. Archived from the original (PDF) on 2017-11-07.

[rfc4086-37] Eastlake, Donald E. 3rd; Schiller, Jeffrey I.; Crocker, Steve (June 2005). "Traditional Pseudo-random Sequences". Randomness Requirements for Security. IETF. sec. 6.1.3. doi:10.17487/RFC4086. BCP 106. RFC 4086.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

Search

선형 합동 생성기

네임스페이스

더

목차

역사