Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Sözde rassal (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özde rassal sayı üreteçlerinin çıktıları gerçek anlamda değildir, bu tür algoritmalar gerçek rassal sayı dizilerinin bazı özelliklerini yaklaşık olarak taşır. John von Neumann'ın da belirttiği gibi "Aritmetik yöntemlerle rassal sayılar üretmeye çalışan biri büyük günah işliyordur.[1]" Her ne kadar rassal sayılar ile üretiliyor olsa da, sözde rassal 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 "rassal sayıların üretimi rastgele gerçekleştirilemeyecek kadar önemlidir[2]" cümlesinde belirttiği gibi üretilmiş olan sayıların rassallığı ciddi ve dikkatli bir matematik analiz gerektirmektedir.
Bu kategorideki pek çok algoritma, bir örnek oluşturmaya çalışırlar. Bu iş için en sık kullanılan algoritma türleri , , ve . Yeni geliştirilmiş algoritmalar arasında ise Blum Blum Shub, Fortuna ve vardır.
Özü itibarıyla rassal olmama
Sözde rassal 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 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özde rassal 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özde rassal sayı üreteçleri inşa etmek mümkündür. Şifrebilimdeki cevaplanmamış sorulardan biri de iyi tasarlanmış bir sözde rassal sayı üretecinin çıktısını, çekirdeğini (başlangıç paramterlerini) bilmeden, gerçek rassal gürültüden ayırt etmenin mümkün olup olmayacağıdır. Şifrebilimdeki pek çok uygulama uygun bir sözde rassal 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ı, rassal sayı üretecinin çıktısı ile işlemine tabi tutar. Bu tür rassal sayı üreteçlerinin tasarımı bir hayli zordur ve çoğu program çok daha basit üreteçler kullanır.
Uygulamada, pek çok sözde rassal 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 rassal' olabilmesi
- Tekbiçimlilik eksikliği
Hatalı sözde rassal sayı üreteçlerinin problemleri kolay kolay tespit edilemeyecek türde olabileceği gibi saçma denecek kadar açık da olabilir. yıllarca kullanılmış 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 algoritması yukarıda bahsedilen pek çok problemden uzak güçlü bir sözde rassal sayı üretecidir. Bu üretecin periyodu 219937-1'dir ve 32 bitlik değerler için 623 boyutta 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 rassal sayı üreteci olmaya başlamıştır.
Bununla birlikte Mersenne Twister algoritmasının çıktısını analiz edip sayıların rassal olmadıklarını anlamak mümkündür (Berlekamp-Massey algoritmasında veya bunun genişletilmiş hali olan 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 rassal sayı üreteçleri
Şifrebilimsel olarak uygun olan bir sözde rassal sayı üreteci rassallık testlerini geçmeye ek olarak bazı ek şifrebilimsel koşulları da sağlamak zorundadır.
Bazı şifrebilimsel olarak güvenli sözde rassal sayı üretici algoritmalar şunlardır:
- veya modunda çalışan dizi veya .
- 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özde rassal sayı üreteçleri. Örn. algoritması. Bu algoritma epey hızlıdır ve periyodu büyüktür.
Bkz.
Notlar
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 25 Eylül 2020 tarihinde Wayback Machine sitesinde ., in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
Dış bağlantılar
- The GNU Scientific Library 9 Haziran 2005 tarihinde Wayback Machine sitesinde .. Birkaç sözde rassal sayı üreteci içeren özgür (GPL) C fonksiyon kitaplığı.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Sozde rassal rastgele sayi ureteci pseudorandom number generator PRNG sozde rastgele ogeleri arasinda kolay kolay iliski kurulamayacak bir sayi dizisi ureten algoritma turlerine verilen genel isimdir Sozde rassal sayi ureteclerinin ciktilari gercek anlamda degildir bu tur algoritmalar gercek rassal sayi dizilerinin bazi ozelliklerini yaklasik olarak tasir John von Neumann in da belirttigi gibi Aritmetik yontemlerle rassal sayilar uretmeye calisan biri buyuk gunah isliyordur 1 Her ne kadar rassal sayilar ile uretiliyor olsa da sozde rassal sayilar modern bilgiislemin onemli bir bolumunu kapsamaktadir ve bunlar kriptolojiden tutun fiziksel sistemleri simule etmeye yarayan Monte Carlo yontemlerine dek pek cok yerde kullanilmaktadir Oak Ridge National Laboratory den Robert R Coveyou nun rassal sayilarin uretimi rastgele gerceklestirilemeyecek kadar onemlidir 2 cumlesinde belirttigi gibi uretilmis olan sayilarin rassalligi ciddi ve dikkatli bir matematik analiz gerektirmektedir Bu kategorideki pek cok algoritma bir ornek olusturmaya calisirlar Bu is icin en sik kullanilan algoritma turleri ve Yeni gelistirilmis algoritmalar arasinda ise Blum Blum Shub Fortuna ve vardir Ozu itibariyla rassal olmamaSozde rassal sayi uretecleri deterministik bir bilgisayarda calistiklari icin kuantum bilgisayari ile karsilastirin deterministik algoritmalardir ve bu tur bir algoritma ile uretilen sayi dizisinin gercek bir olmayan bir ozelligi olacaktir periyodiklik Surasi kesindir ki eger uretec sabit miktarda hafiza kullaniyorsa yeterli sayida dongu adimindan sonra ayni icsel duruma ikinci kez gelecektir ve ondan sonra da sonsuza dek tekrar edecektir Periyodik olmayan bir uretec tasarlanabilir ancak bu tur bir sistemin ihtiyac duydugu hafiza miktari sistem calistikca buyuyecektir Buna ek olarak bir sozde rassal sayi ureteci keyfi bir baslama noktasindan ya da cekirdek durumundan baslatilabilir ve o andan itibaren ozdes bir sayi dizisi uretir Periyodikligin pratik onemi sinirlidir Eklenen her bir hafiza biti ile maksimum periyot iki katina cikar Herhangi bir bilgisayarin evrenin beklenen yasam suresi boyunca hesaplayamayacagi kadar uzun periyoda sahip sozde rassal sayi uretecleri insa etmek mumkundur Sifrebilimdeki cevaplanmamis sorulardan biri de iyi tasarlanmis bir sozde rassal sayi uretecinin ciktisini cekirdegini baslangic paramterlerini bilmeden gercek rassal gurultuden ayirt etmenin mumkun olup olmayacagidir Sifrebilimdeki pek cok uygulama uygun bir sozde rassal sayi uretecinin ciktisinin gurultuden ayirt edilmeyecegi varsayimina dayanir En basit ornegi dizi sifresidir Bu algoritma gizli bir mesaji rassal sayi uretecinin ciktisi ile islemine tabi tutar Bu tur rassal sayi ureteclerinin tasarimi bir hayli zordur ve cogu program cok daha basit uretecler kullanir Uygulamada pek cok sozde rassal sayi ureteci istatistiksel olarak onemli testleri gecmelerini engelleyen bazi durumlar sergiler Bunlardan sadece birkacini soylemek gerekirse Bazi cekirdek baslangic durumlari icin beklenenden daha kisa periyodlar Kotu boyutsal dagilim Birbirini takip eden degerlerin bagimsiz olmamasi Bazi bitlerin digerlerinden daha rassal olabilmesi Tekbicimlilik eksikligi Hatali sozde rassal sayi ureteclerinin problemleri kolay kolay tespit edilemeyecek turde olabilecegi gibi sacma denecek kadar acik da olabilir yillarca kullanilmis isimli algoritma bu turden problemli bir algoritmadir ve o donemdeki pek cok calisma da guvenilir olmaktan uzaktir Mersenne twisterMakoto Matsumoto ve Takuji Nishimura tarafindan 1997 yilinda gelistirilen algoritmasi yukarida bahsedilen pek cok problemden uzak guclu bir sozde rassal sayi uretecidir Bu uretecin periyodu 219937 1 dir ve 32 bitlik degerler icin 623 boyutta oldugu ispatlanmis olup pek cok uretecten daha hizli calismaktadir Bu algoritma bir suredir istatistik simulasyonlarinda ve uretimsel modellemede tercih edilen rassal sayi ureteci olmaya baslamistir Bununla birlikte Mersenne Twister algoritmasinin ciktisini analiz edip sayilarin rassal olmadiklarini anlamak mumkundur Berlekamp Massey algoritmasinda veya bunun genisletilmis hali olan oldugu gibi Mersenne Twister algoritmasinin bu bilinen olumsuz yonleri simdilik onu sifrebilim uygulamalarinda kullanilamaz kilmakla birlikte baska acilardan sorun teskil etmemektedir modelleme simulasyon vb alanlarda kullanilabilmektedir Sifrebilimsel olarak guvenli rassal sayi uretecleriSifrebilimsel olarak uygun olan bir sozde rassal sayi ureteci rassallik testlerini gecmeye ek olarak bazi ek sifrebilimsel kosullari da saglamak zorundadir Bazi sifrebilimsel olarak guvenli sozde rassal sayi uretici algoritmalar sunlardir veya modunda calisan dizi veya Guvenlik kaniti olan ozel tasarimlar Orn Blum Blum Shub algoritmasinin guclu bir kosullu guvenlik kaniti vardir ancak yavas calismaktadir Sifrebilimsel olarak guvenlige dikkat ederek tasarlanmis ozel sozde rassal sayi uretecleri Orn algoritmasi Bu algoritma epey hizlidir ve periyodu buyuktur Bkz Donanimsal rassal sayi ureteci rassallikNotlar 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 6KaynakcaDonald 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 25 Eylul 2020 tarihinde Wayback Machine sitesinde in Proc 19th Annual Computer Security Applications Conference Dec 2003 Dis baglantilarThe GNU Scientific Library 9 Haziran 2005 tarihinde Wayback Machine sitesinde Birkac sozde rassal sayi ureteci iceren ozgur GPL C fonksiyon kitapligi