sözde rastgelelik - Pseudorandomness

Bir rasgele uydurma sayı sırası gibi görünmektedir biridir istatistiksel rasgele bir tam üretilmiştir rağmen, belirleyici ve tekrarlanabilir süreç.

Arka plan

Rastgele sayıların üretilmesi, rastgele örnekleme , Monte Carlo yöntemleri , masa oyunları veya kumar gibi birçok kullanıma sahiptir . Ancak fizikte , yerçekimi ivmesi gibi çoğu süreç deterministiktir, yani aynı başlangıç ​​noktasından her zaman aynı sonucu üretirler. Bazı dikkate değer istisnalar, her ikisi de temel fizikte gerçekten rastgele süreçler olarak modellenen radyoaktif bozunma ve kuantum ölçümüdür . Bu süreçler rastgele sayıların pratik kaynakları olmadığından, insanlar deterministik bir süreç tarafından üretilmelerine rağmen ideal olarak gerçekten rastgele bir dizinin öngörülemezliğine sahip olan sahte rasgele sayıları kullanırlar.

Birçok uygulamada, deterministik süreç, ilk önce rastgele tohum adı verilen bir sayı ile sağlanması gereken, sözde rasgele sayı üreteci adı verilen bir bilgisayar algoritmasıdır . Aynı tohum her seferinde aynı diziyi vereceğinden, özellikle kalıbın öngörülemezliğinin kritik bir özellik olduğu güvenlik uygulamalarında tohumun iyi seçilmesi ve gizli tutulması önemlidir.

Dizinin açıkça öngörülemez olmasının önemli olduğu bazı durumlarda, insanlar radyoaktif bozunma, istasyonlar arasında ayarlanmış bir radyodan toplanan atmosferik elektromanyetik gürültü veya insanların tuş vuruşlarının birbirine karıştırılmış zamanlamaları gibi rastgele sayıların fiziksel kaynaklarını kullandılar . Bu sayıları elde etmek için gereken zaman yatırımı bir uzlaşmaya yol açar: bu fizik okumalarından bazılarını sahte rasgele sayı üreteci için bir tohum olarak kullanmak.

Tarih

Modern hesaplamadan önce, rasgele sayılara ihtiyaç duyan araştırmacılar, bunları çeşitli yollarla ( zarlar , kartlar , rulet çarkları , vb.) üretecek veya mevcut rasgele sayı tablolarını kullanacaklardı.

Araştırmacılara hazır rastgele rakamlar sağlamak için ilk girişim, Cambridge University Press'in LHC Tippett tarafından geliştirilen 41.600 basamaklı bir tablo yayınladığı 1927'de yapıldı . 1947'de RAND Corporation , bir rulet çarkının elektronik simülasyonu ile sayılar üretti; sonuçlar sonunda 1955'te 100.000 Normal Sapma ile Bir Milyon Rastgele Basamak olarak yayınlandı .

Hesaplama karmaşıklığında

Gelen teorik bilgisayar bilimleri , bir dağıtım olan yalancı rasgele sınıfından hiçbir hasım önemli avantaj tekdüze dağılım ayırt eğer düşmanlarının bir sınıf karşı. Bu sahte rastgelelik kavramı, hesaplama karmaşıklığı teorisinde incelenir ve kriptografiye uygulamaları vardır .

Biçimsel olarak, S ve T sonlu kümeler olsun ve F = { f : ST } bir fonksiyon sınıfı olsun. Bir dağıtım D fazla S ε- olan yalancı rasgele karşı F her için ise f olarak F , istatiksel mesafe dağılımları arasında ve örneklenen bir D ve ve örneklenen bir homojen dağılımı ile S , en £ değerinin olan .

Tipik uygulamalarda, F sınıfı , sınırlı kaynaklara sahip bir hesaplama modelini tanımlar ve biri, F'ye karşı sahte olan belirli özelliklere sahip D dağılımlarını tasarlamakla ilgilenir . D dağılımı genellikle bir psödo-rastgele üreticinin çıktısı olarak belirtilir .

Ayrıca bakınız

Referanslar

  1. ^ a b George Johnson (12 Haziran 2001). "Kaos Bilenler Değerli Bir Ürün Sunar: Rastgelelik" . New York Times .
  2. ^ SP Vadhan (2012). Sahte rastgelelik . yalancı rastgelelik, çok az veya hiç rastgelelik kullanılarak oluşturulmuş olmasına rağmen "rastgele görünen" nesneleri verimli bir şekilde üretme teorisi
  3. ^ Mark Ward (9 Ağustos 2015). "Web'in rastgele sayıları çok zayıf, araştırmacılar uyarıyor" . BBC'nin fotoğrafı .
  4. ^ Jonathan Knudson (Ocak 1998). "Javatalk: Nallar, el bombaları ve rastgele sayılar". Güneş Sunucusu . s. 16-17.
  5. ^ a b "Bir Milyon Rastgele Rakam" . RAND Şirketi . 30 Mart 2017'de alındı .
  6. ^ Oded Goldreich. Hesaplamalı Karmaşıklık: Kavramsal Bir Perspektif. Cambridge Üniversitesi Yayınları. 2008.
  7. ^ "Sahtecilik" (PDF) .

daha fazla okuma

Dış bağlantılar