Sözderastlantısal Sayı Üreteci

Sözderastsal sayı üreteci (pseudorandom number generator, PRNG), öğ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 Algoritma Alm Algorithmus (m), Fr Algoritme (m), İng Algorithm Matematikte sayılarla yapılan her türlü hesaplamanın sistematik metoduna verilen genel isim

rastsal değildir, bu tür algoritmalar gerçek rastsal sayı dizilerinin bazı özelliklerini yaklaşık olarak taşır bkz Rastlantısal

John von Neumann`ın da belirttiği gibi Aritmetik yöntemlerle rastsal sayılar üretmeye çalışan biri büyük günah işliyordurrefNot1 Her ne kadar rastsal sayılar 1921 yılından 1923 yılına kadar Berlin Üniversitesinde kimya tahsili gördü İki yıl sonra İsviçre'de Teknik Yüksek Okulu'ndan kimya mühendisliği diploması aldı Nihayet 1926 yılında Budapeşte Üniversitesi'nden matematik doktorası aldı Budapeşte'deki çalışmalarını bitirir bitirmez, genç matematikçiye Göttingen Üniversitesi'nde Rockofeller bursu verilmişti Burada, 23 yaşındayken ilk şaheser eseri "Kuantum Mekaniğinin Matematik Temelleri"ni yayınladı

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 Resim:Casino at nightJPGMonte Carlo`daki *****evlerinden bir görünüşMonte Carlo Monako`nun *****evleriyle ünlü en zengin semtidir 35500 nüfuslu Monako`nun 25000`i bu semtte yaşar

Oak Ridge National Laboratory`den Robert R Coveyou`nun Rastsal sayıların üretimi rastgele gerçekleştirilemeyecek kadar önemlidirrefNot2 cümlesinde belirttiği gibi üretilmiş olan sayıların rastsallığı ciddi ve dikkatli bir matematik analiz gerektirmektedir

Bu kategorideki pek çok algoritma, Algoritma Alm Algorithmus (m), Fr Algoritme (m), İng Algorithm Matematikte sayılarla yapılan her türlü hesaplamanın sistematik metoduna verilen genel isim

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 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 periyodlarKötü boyutsal dağılımBirbirini takip eden değerlerin bağımsız olmamasıBazı bitlerin diğerlerinden `daha rastsal` olabilmesiTekbiç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 2<sup>19937</sup>-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==
# notNot1 Various techniques used in connection with random digits, Applied Mathematics Series, no 12, 36-38 (1951)
# notNot2 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) [http://wwwacsacorg/2003/papers/79pdf J Viega, ``Practical Random Number Generation in Software``], in Proc 19th Annual Computer Security Applications Conference, Dec 2003

==Harici bağlantılar== [http://wwwgnuorg/software/gsl/ The GNU Scientific Library] Birkaç sözderastsal sayı üreteci içeren özgür ( GPL) C fonksiyon kitaplığı


Bu makale, online kullanıcı topluluğu tarafından oluşturulan ve düzenlenen özgür ansiklopedi projesi Wikipedia'nın Türkçe versiyonu Vikipedi'deki Sözderastlantısal sayı üreteci maddesinden kopyalanmıştır Bu makale, GNU Özgür Belgeleme Lisansı ilkeleri kapsamında özgürce kullanılabilir