임의의 정수 생성
나는 임의성에 대한 공식적인 개념에 대해 그다지 경험이 없기 때문에 미리 사과드립니다.
제목은 대부분을 말합니다. 동일한 빈도를 사용하든 중요하지 않든 모든 정수가 나타날 수있는 합리적인 시간 내에 임의의 정수를 생성하고 싶습니다. 추가 기능으로 컴퓨터 메모리는 문제가되지 않습니다. 생성 된 숫자를 저장할 수있는 무한한 메모리 공간이 있어도이를 수행 할 수있는 방법이 명확하지 않기 때문입니다. 실제로 적절한 알고리즘을 찾는 데 진전이 없었지만 여기에 내 관찰이 있습니다.
임의의 실수를 생성 할 수 있다면 플로어 함수와 같은 함수를 사용하여 정수를 생성 할 수 있습니다. 임의의 간격 사이에서 임의의 실수를 생성 할 수있는 경우$[a,b]$, 다음과 같은 점근 함수를 사용할 수 있습니다. $\tan$ 실수를 생성합니다.
일반적으로 정수에 대해 더 크거나 같은 카디널리티를 갖는 집합 S가 있고 S 내에서 임의로 요소를 생성 할 수 있다면 S의 구성원을 정수에 매핑하여 임의의 정수를 생성 할 수 있습니다.
나는 소수이며 임의의 큰 정수를 포함하지만 쉽게 계산할 수없는 소수 간격 시퀀스와 같은 시퀀스가 있다는 것을 알고 있습니다.
그러나 그것이 내가 생각할 수있는 것에 관한 것입니다. 문제에 대한 쉬운 해결책이 없다고해도 놀라지 않을 것입니다. 그러나 이것이 왜 불가능한 지에 대한 이유가 있다면 저도 듣고 싶습니다.
답변
계산이 중단 될 수 없기 때문에 임의의 크기는 의미가 없습니다!
임의의 정수의 모든 비트에 대해 동전을 던졌다 고 생각하면 동전 던지기가 끝이 없음을 알 수 있습니다.
임의의 크기로 플레이 할 때주의해야합니다. 수학적으로 말할 수 있습니다.$x$ 임의의 정수, 즉 $x \stackrel{R}{\leftarrow} \mathbb Z$그러나 당신이 이것의 가치를 찾으려고 할 때 당신은 그것의 세대에 직면하게 될 것입니다. 균일 한 임의의 정수를 원한다면 분명히 실패 할 것입니다!
이제 다음과 같은 제한이 있다고 가정합니다. $0\color{red}{<} x \leq 2^L$그런 다음 LFSR 을 사용 하여 범위에서 난수를 생성 할 수 있습니다 . 크기가있는 LFSR의 경우$L$ 최대이고 주기적이며 $2^L-1$. 이 기간에는 가능한 모든 방문$L$모두 0 상태를 제외한-비트 숫자. 시간부터 씨앗을 얻어서 사용할 수 있습니다.
LFSR은 CSPRNG (Cryptographically Secure Random Pseudo Generator)와는 거리가 멀다는 점에 유의하십시오. 그냥$2L$ LFSR의 비트 출력은 Berlakamp-Massay 알고리즘으로 인해 다음 비트를 결정하기에 충분합니다. 실제로 가우스 제거만으로도 충분하지만 BM은 훨씬 빠릅니다.