2010-05-20 7 views
7

나는 상태를 숨기지 않고 이전 출력에서 ​​순수 함수처럼 계산할 수있는 좋은 의사 난수 생성기가 필요합니다. "좋은"에서 말 :PRNG가 숨겨진 상태가 아닌 값을 생성하는 "양호한"PRNG가 있습니까?

  1. 나는 어떤 매개 변수 2^n 반복 그것을 실행하는 (또는 그 중 일부 큰 부분 집합하는) 사이의 모든 또는 거의 모든 값을 포함해야한다는 등의 방법으로 생성 변수화 할 수 있어야합니다 02^n - 1입니다. 여기서 n은 출력 값의 비트 수입니다. n + p 비트

  2. 결합 된 발전기 출력 모두를 포함해야하거나 거의 02^(n + p) - 1 사이의 모든 값 I는 p 파라미터의 비트 수는 그 변수의 모든 가능한 조합 2^n 반복 그것을 실행할 경우.

예를 들어, LCG 순수한 함수처럼 계산 될 수 있고, 그것은 첫 번째 조건을 충족 할 수 있지만, 두 번째를 충족시킬 수 없다. 우리는 32 비트 LCG 인 m = 2^32을 가지고 있으며, 우리의 p = 64 (2 개의 32 비트 매개 변수 ac), n + p = 96이 상수이기 때문에 두 번째 조건을 충족하기 위해 출력에서 ​​3 정수로 데이터를 엿보아야합니다. 불행하게도, 출력은 홀수 및 짝수 int의 순서가 엄격하게 교번하기 때문에 조건을 만족시킬 수 없습니다. 이것을 극복하기 위해서는 숨겨진 상태가 도입되어야하지만, 그것은 순수한 것이 아니며 첫 번째 조건 (긴 감추어 진 기간)을 깨뜨린다.

편집 :는 엄밀히 말하면, 나는 p 비트에 의해, 각 단지 지속적으로 (p + n)를 증가하지, 독특한 "randomish"의 방법을 p + n 비트의 모든 가능한 바이너리 문자열을 생성 n 비트의 전체 상태와 매개 변수화 기능의 가족을 원한다 - 비트 int. 고유 한 방법을 선택하려면 매개 변수화가 필요합니다.

너무 많이 갖고 싶습니까?

+0

난수 생성기에서 거의 별개의 시퀀스를 생성하도록 하시겠습니까? –

+0

@Moron, 네. 생성기는 n actual

+2

k 통화에서 k 개의 고유 번호가 예상되는 경우이 번호는 전혀 임의가 아닙니다. 예 : 나는 항상 마지막 것을 예측할 수있다! 아니면 내가 오해 했습니까? –

답변

1

시도해보십시오. LFSR
필요한 것은 원시 다항식의 목록입니다.
이 방법으로 유한 필드를 생성하는 기간은 크기 2^n-1의 필드를 생성합니다. 그러나 당신은 k^n-1의 어떤 기간이라도 생성하도록이 절차를 일반화 할 수 있습니다.

나는이 구현 보지 못했다,하지만 당신은 구현해야하는 것은 소수의로 번호를 이동하고있다> n은 GCD (S, 2^N-1) == 1. GCD는 최대 공약수를 의미

+0

제가 이해할 수 있듯이, 생성 할 수없는 0을 포함하는 결합 된 값의 하위 집합이 있습니다. – actual

+0

사실입니다. 필요하다면 0에 대한 지원을 수동으로 추가해야하며 예를 들어 0x001에서 0x000까지 미리 정의 된 값에서 점프하고 0x001의 다음 값으로 돌아갈 수 있습니다. –

2

고정 키를 사용하여 블록 암호를 사용할 수 있습니다. 다음 번호를 생성하려면 현재 번호를 해독하고 증분 한 다음 다시 암호화하십시오. 블록 암호는 1 : 1이기 때문에 반드시 반복하기 전에 출력 도메인의 모든 숫자를 반복해야합니다.

+0

재미있는 생각이지만 내 응용 프로그램에는 너무 느립니다. 어쨌든 감사합니다. – actual

+0

흠 ... 어쩌면 그렇게 느린 것도 아닙니다. n + p가 아닌 width p의 키를 생성하고 n + p width의 데이터로 XOR 연산을 시작하면 어떻게 작동 할 것이라고 생각하십니까? n + p 너비의 모든 조합을 생성합니까? – actual

+0

데이터를받는 위치에 따라 다릅니다. 대체로 말하자면, 아마 순열을 발생시키지 않을 것입니다. –