Sözderastsal sayı üreteçlerinin çıktıları gerçek anlamda rastsal değildir, bu tür algoritmalar gerçek rastsal sayı dizilerinin bazı özelliklerini yaklaşık olarak taşır. John von Neumann`ın da belirttiği gibi "Aritmetik yöntemlerle rastsal sayılar üretmeye çalışan biri büyük günah işliyordur.}" Her ne kadar rastsal sayılar donanımsal rastsal sayı üreteçleri ile üretiliyor olsa da, sözderastsal sayılar modern bilgiişlemin önemli bir bölümünü kapsamaktadır ve bunlar şifrebilimden tutun fiziksel sistemleri simüle etmeye yarayan Monte Carlo yöntemlerine dek pek çok yerde kullanılmaktadır. Oak Ridge National Laboratory`den Robert R. Coveyou`nun "Rastsal sayıların üretimi rastgele gerçekleştirilemeyecek kadar önemlidir}" cümlesinde belirttiği gibi üretilmiş olan sayıların rastsallığı ciddi ve dikkatli bir matematik analiz gerektirmektedir.
Bu kategorideki pek çok algoritma, tekbiçimli dağılım bir örnek oluşturmaya çalışırlar. Bu iş için en sık kullanılan algoritma türleri doğrusal denklik üreteçleri, gecikmeli Fibonacci üreteçleri, doğrusal geribeslemeli kaydırma yazmaçları ve genelleştirilmiş geribeslemeli kaydırma yazmaçlarıır. Yeni geliştirilmiş algoritmalar arasında ise Blum Blum Shub, Fortuna ve Mersenne Twister vardır.
Özü itibariyle rastsal olmama
Sözderastsal sayı üreteçleri deterministik bir bilgisayarda çalıştıkları için (kuantum bilgisayarı ile karşılaştırın) deterministik algoritmalardır ve bu tür bir algoritma ile üretilen sayı dizisinin gerçek bir rastsal dizide olmayan bir özelliği olacaktır: periyodiklik. Şurası kesindir ki, eğer üreteç sabit miktarda hafıza kullanıyorsa yeterli sayıda döngü adımından sonra aynı içsel duruma ikinci kez gelecektir ve ondan sonra da sonsuza dek tekrar edecektir. Periyodik olmayan bir üreteç tasarlanabilir ancak bu tür bir sistemin ihtiyaç duyduğu hafıza miktarı sistem çalıştıkça büyüyecektir. Buna ek olarak bir sözderastsal sayı üreteci keyfi bir başlama noktasından, ya da çekirdek durumundan, başlatılabilir ve o andan itibaren özdeş bir sayı dizisi üretir. Periyodikliğin pratik önemi sınırlıdır. Eklenen her bir hafıza biti ile maksimum periyod iki katına çıkar. Herhangi bir bilgisayarın evrenin beklenen yaşam süresi boyunca hesaplayamayacağı kadar uzun periyoda sahip sözderastsal sayı üreteçleri inşa etmek mümkündür. Şifrebilimdeki cevaplanmamış sorulardan biri de iyi tasarlanmış bir sözderastsal sayı üretecinin çıktısını, çekirdeğini (başlangıç paramterlerini) bilmeden, gerçek rastsal gürültüden ayırt etmenin mümkün olup olmayacağıdır. Şifrebilimdeki pek çok uygulama uygun bir sözderastsal sayı üretecinin çıktısının gürültüden ayırt edilmeyeceği varsayımına dayanır. En basit örneği akış şifresidir. Bu algoritma gizli bir mesajı, rastsal sayı üretecinin çıktısı ile xor işlemine tabi tutar. Bu tür rastsal sayı üreteçlerinin tasarımı bir hayli zordur ve çoğu program çok daha basit üreteçler kullanır.Uygulamada, pek çok sözderastsal sayı üreteci istatistiksel olarak önemli testleri geçmelerini engelleyen bazı durumlar sergiler. Bunlardan sadece birkaçını söylemek gerekirse:
- Bazı çekirdek (başlangıç) durumları için beklenenden daha kısa periyodlar
- Kötü boyutsal dağılım
- Birbirini takip eden değerlerin bağımsız olmaması
- Bazı bitlerin diğerlerinden `daha rastsal` olabilmesi
- Tekbiçimlilik eksikliği
Hatalı sözderastsal sayı üreteçlerinin problemleri kolay kolay tespit edilemeyecek türde olabileceği gibi saçma denecek kadar açık da olabilir. ana çatı bilgisayarlarında yıllarca kullanılmış RANDU isimli algoritma bu türden problemli bir algoritmadır ve o dönemdeki pek çok çalışma da güvenilir olmaktan uzaktır.
Mersenne twister
Makoto Matsumoto ve Takuji Nishimura tarafından 1997 yılında geliştirilen Mersenne twister algoritması yukarıda bahsedilen pek çok problemden uzak güçlü bir sözderastsal sayı üretecidir. Bu üretecin periyodu 219937-1`dir ve 32 bitlik değerler için 623 boyutta eşdağılımlı olduğu ispatlanmış olup pek çok üreteçten daha hızlı çalışmaktadır. Bu algoritma bir süredir istatistik simülasyonlarında ve üretimsel modellemede tercih edilen rastsal sayı üreteci olmaya başlamıştır.Bununla birlikte Mersenne Twister algoritmasının çıktısını analiz edip sayıların rastsal olmadıklarını anlamak mümkündür (Berlekamp-Massey algoritmasında veya bunun genişletilmiş hali olan Reed-Sloane algoritmasında olduğu gibi). Mersenne Twister algoritmasının bu bilinen olumsuz yönleri şimdilik onu şifrebilim uygulamalarında kullanılamaz kılmakla birlikte başka açılardan sorun teşkil etmemektedir (modelleme, simülasyon, vb. alanlarda kullanılabilmektedir).
Şifrebilimsel olarak güvenli rastsal sayı üreteçleri
``Main article: Cryptographically secure pseudo-random number generator``
Şifrebilimsel olarak uygun olan bir sözderastsal sayı üreteci rastsallık testlerini geçmeye ek olarak bazı ek şifrebilimsel koşulları da sağlamak zorundadır.
Bazı şifrebilimsel olarak güvenli sözderastsal sayı üretici algoritmalar şunlardır:
- Counter modda veya çıktı besleme modunda çalışan akış veya blok şifreleri.
- Güvenlik kanıtı olan özel tasarımlar. Örn. Blum Blum Shub algoritmasının güçlü bir koşullu güvenlik kanıtı vardır ancak yavaş çalışmaktadır.
- Şifrebilimsel olarak güvenliğe dikkat ederek tasarlanmış özel sözderastsal sayı üreteçleri. Örn. ISAAC algoritması. Bu algoritma epey hızlıdır ve periyodu büyüktür.
Bkz.
- Sözderastsal ikili dizi
- Rastsallaştırılmış algoritma
- Rastsal sayı üreteci
- Rastsal sayı üreteç saldırısı
- Sözderastsal sayı üreteçleri listesi
- Donanımsal rastsal sayı üreteci
- Rastsallık
Notlar
- } "Various techniques used in connection with random digits", Applied Mathematics Series, no. 12, 36-38 (1951).
- } Peterson. Ivars. ``The Jungles of Randomness: A Mathematical Safari.`` Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6
Kaynakça
- Donald E. Knuth, ``The Art of Computer Programming, Volume 2: Seminumerical Algorithms``, 3rd edition (Addison-Wesley, Boston, 1998).
- J. Viega, ``Practical Random Number Generation in Software``, in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
Harici bağlantılar
- The GNU Scientific Library. Birkaç sözderastsal sayı üreteci içeren özgür (GPL) C fonksiyon kitaplığı.
