Sözderastlantısal sayı üreteci

Sözderastsal (rastgele) sayı üreteci (pseudorandom number generator, PRNG, sözde rastgele), öğeleri arasında kolay kolay ilişki kurulamayacak bir sayı dizisi üreten algoritma türlerine verilen genel isimdir.

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 kriptolojiden 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ımdan 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ıdı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 periyot 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 dizi ş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:

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

Ş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:

Bkz.

Notlar

  1. ↑  "Various techniques used in connection with random digits", Applied Mathematics Series, no. 12, 36-38 (1951).
  2. ↑  Peterson. Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6

Kaynakça

Dış bağlantılar

This article is issued from Vikipedi - version of the 2/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.