Madencilik

Video - Sahte rasgele Sayaç Jeneratörleri

Rasgele ve Sahte Random Sayaç Jeneratörleri. Brit Cruise tarafından düzenlendi.

DÖNÜŞÜM

Fiziksel dünyayı gözlemlediğimizde, her yerde rastgele dalgalanmalar görürüz. Gürültü olarak bilinen rasgele dalgalanmaları ölçerek gerçekten rassal sayılar üretebiliriz. Örnekleme olarak da bilinen bu gürültüyü ölçtüğümüzde rakamlar elde edebiliriz.

Bir, iki, üç, dört- Örneğin, zamanla statik TV'nin elektrik akımını ölçersek, gerçekten rastgele bir dizi oluştururuz. Bu rasgele diziyi, rastgele bir yürüyüş olarak bilinen her sayıya göre yön değiştiren bir yol çizerek görselleştirebiliriz. Tüm ölçeklerde desen eksikliğine dikkat edin.

Sekansın her noktasında bir sonraki hareket her zaman öngörülemeyecektir. Rasgele süreçler önceden belirlenemediğinden kararsızdırlar. Makineler ise deterministiktir. Onların çalışması öngörülebilir ve tekrarlanabilir.

John Von Neumann 1946'da ordu için hesaplamalar yapmakla görevlendirildi; özellikle hidrojen bombasının tasarımında yer aldı. ENIAC adlı bir bilgisayar kullanarak, nükleer fisyonla ilgili süreçlerin tahminlerini tekrar tekrar hesaplamayı planladı.

Ancak, bu, gerekirse tekrarlanabilecek rasgele üretilen sayılara hızlı erişim gerektiriyordu. Bununla birlikte, ENIAC'in dahili belleği çok sınırlıydı; uzun rastgele sekansların saklanması mümkün değildi. Böylece, Neumann mekanik olarak rasgele seçme yönünü aşağıdaki gibi taklit etmek için bir algoritma geliştirdi: Önce, "tohum" olarak adlandırılan gerçekten rastgele bir sayı seçin.

Bu sayı, gürültünün ölçülmesinden veya milisaniye cinsinden mevcut zamandan gelebilir. Sonra, bu tohum basit bir hesaplamaya giriş olarak sağlanır. Tohumu tek başına çarpın ve sonra bu sonucun ortasında çıktılar. Sonra bu çıktıyı bir sonraki tohum olarak kullanıp işlemi gerektiği kadar tekrarlayın.

Bu, orta kareler yöntemi olarak bilinir ve sahte rasgele sayı üreteçlerinin uzun bir satırındaki sadece birincisidir. Dizinin rassallığı, yalnızca başlangıç ​​tohumunun rasgelelik derecesine bağlıdır. Aynı tohum, aynı sıra. Peki, rasgele üretilen ile sahte ve rastgele oluşturulmuş dizi arasındaki farklar nelerdir? Her diziyi rastgele bir yürüyüş olarak temsil edelim.

İşleri hızlandırana kadar benzer görünüyorlar. Sahte rasgele sıralama tekrar tekrarlanmalıdır. Bu, algoritma, daha önce kullandığı bir tohum ulaştığında ve döngü yinelenen oluşur. Sözde rastgele bir sekans tekrarlanmadan önce uzunluk "dönem" olarak adlandırılır.

Dönem başlangıç ​​tohumunun uzunluğu ile sınırlıdır. Örneğin, iki haneli bir tohum kullanırsak, bir tohum tekrar kullanılmadan ve döngüyü tekrarlamadan önce bir algoritma en fazla 100 sayı üretebilir. Üç basamaklı bir tohum, döngüsünü tekrarlamadan önce 1, 000 rakamı geçemez ve yinelenmeden önce dört basamaklı bir tohum 10, 000 rakamını geçemez.

Yeterli büyüklükte bir tohum kullansak da, dizi tekrarlamadan önce trilyonlarca ve trilyonlarca basamak gösterebilir. Anahtar fark önemli olsa da. Yalancı rasgele sayılar ürettiğinizde, gerçekleşemeyen birçok dizi vardır.

Örneğin, Alice, 20 kaymanın gerçekten rasgele bir dizisini üretirse, olası tüm kaymalar dizisinden tek biçimli bir seçime eşdeğerdir. Bu yığın, astronomik boyutta 26 sayfalık 20 sayfalık bir güç içeriyor. Altta durup yukarı doğru bir ışık parlattıysak, üstteki bir kişi ışığı yaklaşık 200, 000 000 yıl boyunca göremezdi.

Alice ile dört haneli rasgele bir tohum kullanarak 20 basamaklı bir sahte rastgele sıralama üretin. Şimdi, bu 10 000 olası başlangıç ​​tohumlarından tek biçimli bir seçime eşdeğerdir, yani olası tüm dizilerin çok küçük bir kısmı olan yalnızca 10 000 farklı diziyi üretebilir.

Rastgele olan yerine rastgele rasgele geçişler yaparken, anahtar alanını çok daha küçük tohumluk alanına küçültürüz. Dolayısıyla, sözde rastgele bir dizinin rastgele oluşturulmuş diziden ayırt edilemez olması için, bir bilgisayar için tüm tohumları denemek ve bir eşleşme aramak pratik olmamalıdır.

Bu, mümkün olanı, makul bir sürede mümkün olanı karşı bilgisayar bilimi alanında önemli bir ayrım yapmaktadır. Bisiklet kilidini alırken aynı mantığı kullanırız. Bir maç bulana kadar açabilecekleri tüm kombinasyonları deneyebileceğini biliyoruz.

Fakat bunu yapmak günlerce sürer. Yani, sekiz saat boyunca pratik olarak güvenli olduğunu varsayıyoruz. Sahte rasgele jeneratörler ile tohumun uzunluğu arttıkça güvenlik artar. En güçlü bilgisayar, tüm tohumların arasından kaçmak için yüzlerce yıl sürecekse, o zaman, güvenli bir şekilde değil, pratik olarak güvenli olduğunu varsayabiliriz.

Bilgisayarlar daha hızlı hale geldiğinde tohumluk boyutu buna göre artmalıdır. Sahte raslantı, Alice ve Bob'un tüm rastgele vardiya sırasını önceden paylaşmalarını gerektirmez. Bunun yerine, nispeten kısa rastgele bir tohum paylaşıyorlar ve gerektiğinde onu aynı rastgele görünümlü sekansa genişletiyorlar. Ancak bu rastgele tohumları paylaşmak için hiçbir zaman bir araya gelemiyorsa ne olur?