Polinomsal Sürede Çalışan Deterministik Asallık Testi

0
FZ
Hintli Profesör Manindra Agarwal ve onunla çalışan iki doktora öğrencisi Nitin Saxena ve Neeraj Kayal girilen bir sayının asal sayı olup olmadığını polinomsal sürede determenistik olarak tespit edebilen bir algoritma geliştirdiler. Yüzlerce yıldır pek çok araştırmacı asallık testi için polinomsal sürede çalışabilen bir algoritma arıyorlardı ve çoğu araştırmacıya göre bu algoritma önem bakımından rahatlıkla 70'lerde geliştirilmiş P-süreli Lineer Programlama çözümü ile kıyaslanabilir.
Bu sonucun en önemli özelliklerinden biri ispatın uzun ya da karışık olmaması (sadece 9 sayfa) ve sayılar teorisindeki bazı teoremlerin sonuçlarını dahiyene olarak kullanması.

FZ'nin notu: Bu algoritmayı saymazsak şimdiye kadar geliştirilen algoritmalar olasılıksal algoritmalardı yani size kısa sürede sayının asal olup olmadığını söylüyorlardı ama bunu %99.9 gibi kesinlikle söylüyorlardı, %100 değil. %100 söyleyebilen algoritmalar ise sayı büyüdükçe bu büyümeden çok daha yüksek bir oranda yavaşlıyorlardı (yani polinomsal sürede çalışmıyorlardı, daha uzun sürede çalışıyorlardı). Peki bütün bunların manası ne, şu: Günümüzde yaygın olarak kullanılan açık anahtar şifreleme sistemleri çok büyük asal sayılar isterler girdi olarak, artık bu girdinin asal olduğundan çok kısa sürede %100 emin olabileceğiz (bu işin teknolojik boyutu, matematiksel ve ileriye yönelik yorumları da yazanlar olursa sevinirim.

FZ'nin ikinci notu: "Japonlar yapmış abi" kategorisine bir cümle daha ekliyoruz ve "Hintliler yapmış abi" diyoruz.

Görüşler

0
conan
Tek kelime! OMFG!

Supersin FZ!
0
FZ
Ben değil, Hintliler süper, aşağılık kompleksine kapılmak tasvip ettiğim bir şey değildir ama... yani... ;-)

Bu arada, OMFG ne demek? Hani Oh My ... God diyesim geliyor da F tam olarak neye karşılık geliyor, onu çözemedim ;-)
0
cartman
Oh My Fine God ;-)
0
anonim
Olasılıkla Mükemmel Fazlamesai Getirisi

yuh bana oha bana bu kadar mı zorlanır bir laf
0
cadas
Peki sifrelerin cozulmesinde de ise yarayacak mi bu algoritma, yani daha hizli cozulmesinde?

Yoksa alakasiz bir sey mi soruyorum.
Görüş belirtmek için giriş yapın...

İlgili Yazılar

FreeBSD Çekirdek (Core) Geliştirme Ekibi ile Röportaj

FZ

Karşınızda çekirdek FreeBSD yazılım uzmanları ile yapılmış bir röportaj. Wes Peters, Greg Lehey and M. Warner Losh ve Scott Long ile konuşulan konular arasında şunlar var: Sun Microsystems tarafından desteklenen Java port´u, Linux ile rekabet, 5.x sürümü ve diğer UNIX sistemlerle kıyaslamalar, yeni dosya sistemi UFS2, XFree86 uygulaması, SCO ve UNIX ile ilgili fikri mülkiyet meseleleri. Eğer öyle ya da böyle UNIX uyumlu herhangi bir işletim sistemi ile muhatapsanız (ya da MS Windows üzerinde TCP/IP kullanıyorsanız :-P) bu röportajı mutlaka okumalısınız.

Üniversite Adayları için `Bilgisayar Bilimleri Test Sürüşü 2010´

butch

“ÖSS bitti, sırada üniversite ve bölüm seçme telaşı var. Doğru kararı vermek için pek çok etkeni göz önünde bulundurmak gerekli. Gelecekteki kariyerini bilgisayar bilimleri üzerine kurmayı düşünen gençlerimizi 22, 29 Temmuz ve 5 Ağustos Perşembe günleri test sürüşüne bekliyoruz. Bilgisayar bilimlerinin büyüleyici dünyasında kısa bir yolculuğa çıkmaya ve maceraya hazır mısınız?”

mySQL 4.0.12 hazır

redial

Resmi açıklama: 4.0 sürümü standart download sürümü olmuş.

Editörün Notu: Nedense aklıma sundance arkadaşımızın Serbest Yazılımlar Yetersiz mi? konu başlıklı makalesi geldi ;-)

Microsoft`un ikiye bölünmesi kararına iptal

mostra

Ve ulu Birlesik Devletler adaleti Hürriyet`te yazan habere göre kararından vaz geçti. Aslında bölünse daha iyi olmaz mıydı? Kesinlikle tartışılır bir durum. Birbirleri ile danışıklı dövüşte mi olurlardı yoksa gerçekten mükemmel bir rekabet ortamı mı ortaya çıkardı ? Keşke yaşasaydık da görseydik.. Neyse siz okuyun karar verin, atın tutun yakalayın, iş görün ;-)(unutmadan bu microsaft'a karşı olmak bir virus gibi yayılıyor mu ne {;-p)

İstanbul parmaklarımın altında:Büyükşehir Belediyesi tüm İstanbul`u nete taşıdı

sidar

İstanbul Büyükşehir Belediyesi, tüm İstanbul'u sokaklarına kadar incelemek isteyenler için İnternet'te yeni bir sayfa açtı. Tüm sokak, mahalle ve caddelerin dahil olduğu bu ayrıntılı İnternet Haritasi şu an beta olsa da çok güzel iş görüyor. url: http://212.174.15.14