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

Herkese Açık Tamamen Türkçe ve Video Destekli Programlama Eğitimi Başladı

FZ

Türkiye'de bir ilki gerçekleştiren İstanbul Bilgi Üniversitesi Bilgisayar Bilimleri bölümü herkese ama özellikle de hevesli ortaokul ve lise öğrencilerine açık, tamamen Türkçe, zengin video destekli bir "programlamaya giriş" ve "bilgisayar bilimleri" dersi hazırladı.

IBM tarafından global olarak verilen Fakülte Ödülü'ne layık görülen bu eşsiz uzaktan eğitim projesinden faydalanmak isteyen öğrencilerin tek yapması gereken http://kleene.cs.bilgi.edu.tr/learn/ adresindeki uzaktan eğitim sunucusuna bağlanıp Bilgisayar Kulüpleri bağlantısına tıklayıp sonra da Yeni Hesap Oluştur düğmesine basmak.

The Codebreakers: BBC'den Açık Kaynak ve Özgür Yazılım Belgeseli

FZ

BBC tarafından hazırlanan ve açık kaynak ile özgür yazılım dünyasına ışık tutmayı hedefleyen The Codebreakers Mayıs ayında yayınlanmıştı.

İki bölümlük belgeselin 40 dakikalık bir sürümü OGG (90MB), WMV (60MB), M4V (225MB) veya DVD ISO torrent (1.5GB) olarak indirmek mümkün.

Slackware GNU/Linux'un Babası Ağır Hasta!

FZ

Son haberlere göre Slackware GNU/Linux'un mimarı Patrick Volkerding tam olarak ne olduğu belli olmayan ve tedavisi aranan bir hastalığın pençesinde.

Volkerding'in kamuya son mesajını buradan okuyabilirsiniz. (Mesajın bir kopyası da burada.)

Telnet üzerinden Star Wars!

larweda

Hollandalı bazı amcamlar, (nedense böyle hikayeler hep hollandadan çıkıyor zaten) bir shell script'i ile Starwars Episode IV: A new Hope filmini ascii-art olarak yapımışlar, yani şuraya (towel.blinkenlights.nl) telnet yapıyorsunuz, başlıyor "A long time ago, in a galaxy far far away" kabilinden, ve filmin tüm sahneleri, prensesin gemisinin yakalanışı, ışın kılıcı savaşları, prensesin kurtuluşu, Luke'un eğitimi vs tamamiyle ascii-art olarak karşınıza çıkıyor, tamamiyle basit bir olay olmasına rağmen bir ya da bir kaç kişi epey zamanını almış. Bi göz atın, görmedim demezsiniz.

Eurovision´ı Kazandık!

SHiBuMi

Bu gece tarihi bir gece oldu. Yıllardır katılıp 3.lük dışında hep sonlarda kaldığımız Eurovision yarışmasını kazandık. Şarkı iyidir/kötüdür, ingilizcedir/türkçe olmalıdır vs. bir yana, bu işin lansmanını yapan, ekip ruhunu yarışmanın sonuna dek taşıyan, kabuğundan çıkıp kendini yenileme cesaretini göstermiş olan herkese emekleri için teşekkür etmek gerekiyor.