선형 합동 난수 생성기(LCG) 계산기

상태가 m가지뿐이므로 아무리 길어도 m입니다. c가 0이 아닐 때 주기가 정확히 m이 되는 조건은 헐-더먼-그린버거 정리로 정해져 있습니다. ① c와 m이 서로소, ② a−1이 m의 모든 소인수로 나누어떨어짐, ③ m이 4의 배수면 a−1도 4의 배수 — 셋을 모두 만족하면 어느 씨앗에서 출발해도 주기가 m입니다.

m이 2의 거듭제곱인 LCG에서는 하위 k비트의 주기가 정확히 2ᵏ이기 때문입니다. 최하위 비트만 보면 주기가 2라서 0과 1이 그저 번갈아 나옵니다. 전체 주기가 40억이어도 이 결함은 그대로입니다. 나머지 연산으로 작은 범위를 만들려면 상위 비트를 쓰거나, 애초에 LCG가 아닌 생성기를 써야 합니다.

절대 안 됩니다. 연속한 출력 몇 개만 관찰하면 a·c·m을 복원할 수 있고, 하위 비트를 잘라 내 감춰도 격자 기법으로 풀립니다. 예측되면 곤란한 값에는 운영체제가 주는 암호학적 난수(브라우저의 crypto.getRandomValues, 리눅스의 /dev/urandom)를 씁니다.

a=65539, c=0, m=2³¹인 이 생성기는 연속한 세 값을 3차원 좌표로 찍으면 겨우 15개 평면 위에만 놓입니다. 1960~70년대에 널리 쓰이면서 그 시기의 여러 시뮬레이션 결과를 신뢰할 수 없게 만들었습니다. 게다가 c가 0이고 씨앗이 홀수면 최하위 비트가 아예 변하지 않습니다.

곱셈형 LCG가 되어 헐-더먼-그린버거 정리가 적용되지 않습니다. 0이 한 번 나오면 영원히 0에 갇히므로 최대 주기가 m이 아니라 m−1이고, m이 소수일 때 주기는 a의 곱셈 위수입니다. MINSTD(a=16807, m=2³¹−1)가 그 예로 주기가 2147483646입니다.

전송되지 않습니다. 계산은 전부 브라우저 안에서 이뤄지고, 입력값은 이 브라우저의 localStorage에만 남습니다.