herhangi bir rastgele tamsayı oluştur
Herhangi bir biçimsel rastgelelik kavramı konusunda pek tecrübeli olmadığım için şimdiden özür dilerim.
Başlık çoğunu söylüyor: Makul bir süre içinde rastgele bir tamsayı oluşturmak istiyorum, her tamsayının görünebileceği, eşit sıklıkta olsun veya olmasın önemli değil. Ek olarak, bilgisayar belleği bir sorun değildir, çünkü oluşturulan bu sayıları depolamak için sonsuz bellek alanı olsa bile, bunun nasıl yapılacağı açık değildir. Aslında uygun bir algoritma bulmak için herhangi bir ilerleme kaydetmedim ama işte gözlemlerim.
Rastgele herhangi bir gerçek sayı üretebiliyorsanız, herhangi bir tamsayı oluşturmak için zemin işlevi gibi işlevleri kullanabilirsiniz. Herhangi bir aralık arasında rastgele herhangi bir gerçek sayı üretebilseydiniz$[a,b]$, daha sonra asimptotik işlevleri kullanabilirsiniz. $\tan$ herhangi bir gerçek sayı oluşturmak için.
Genel olarak, tamsayılara eşit veya daha büyük bir kardinaliteye sahip bir S kümesine sahipsem ve S içinde rastgele bir öğe oluşturabilirsem, S'nin üyelerini tam sayılara eşleyerek rastgele herhangi bir tamsayı üretebilirim.
Asal boşluk dizisi gibi rastgele olan ve keyfi olarak büyük tamsayılar içeren, ancak kolayca hesaplanamayan diziler olduğunu biliyorum.
Ancak düşünebildiklerimle ilgili bu. Sorunun kolay bir çözümü olmasa şaşırmam ama bunun neden mümkün olmadığına dair bir nedeni varsa ben de duymak isterim.
Yanıtlar
Rasgele boyutun hiçbir anlamı yoktur, çünkü hesaplama durduramaz!
Rastgele tam sayının her biti için bir jeton attığınızı düşünün, o zaman yazı tura atmanın hiç bitmediğini görebilirsiniz.
Keyfi boyutta oynarken dikkatli olunmalıdır. Matematiksel olarak şunu söyleyebilirsin$x$ rastgele bir tam sayı olabilir, yani $x \stackrel{R}{\leftarrow} \mathbb Z$ancak, bunun bir değerini bulmaya çalıştığınızda, onun nesliyle yüzleşeceksiniz. Tek tip bir rastgele tam sayı istiyorsanız, o zaman açıkçası başarısız olacaktır!
Şimdi gibi bir sınırınız olduğunu varsayalım $0\color{red}{<} x \leq 2^L$o zaman aralıkta rastgele sayılar oluşturmak için LFSR'leri kullanabilirsiniz . Boyuta sahip bir LFSR ise$L$ maksimal ise periyodiktir ve bir periyodu vardır $2^L-1$. Bu dönemde mümkün olan her şeyi ziyaret eder$L$tamamen sıfır durumu dışında bitlik sayılar. Zamandan bir tohum alıp kullanmaya başlayabilirsiniz.
LFSR'nin Kriptografik Olarak Güvenli Rastgele Sözde Üreteci (CSPRNG) olmaktan uzak olduğunu unutmayın. Sadece sahip olmak$2L$ LFSR'den bit çıktısı, Berlakamp-Massay algoritması nedeniyle sonraki bitleri belirlemek için yeterlidir - ve aslında, Gauss eliminasyonu yeterlidir, ancak BM çok daha hızlıdır-.