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

Be Inc. topu attı...

SHiBuMi

Aynı isimli işletim sisteminin (BeOS) yaratıcısı Be Inc, 15 Mart itibariyle dağılacağını ve hisselerinin Nasdaq piyasasından çekileceğini duyurdu. Karar halihazırda ekim ayında hissedarlar tarafından alınmış. Geçtiğimiz sene işletim sistemini Palm Inc.`e satan Be, Şubat ayında Microsofta karşı rekabete aykırı fiyat kırmak suçlamasıyla dava açmıştı.

Kaynak: Reuters Be sitesi: www.be.com

Türk Basını Marvin Minsky'yi Keşfediyor

FZ

Radikal gazetesi yazarlarından İsmet Berkan, Marvin Minsky'nin SOCIETY OF MIND isimli sıradışı ve önemli kitabından bahsetmeye başlamış ve bu hafta da devam ediyor.

Yeni bir kitap değil ancak yapay zekâ, felsefe, zihin felsefesi, düşünce, psikoloji gibi konularla ilgilenenlerin mutlaka okuması gereken türden. Benim de kısa süre önce okuduğum ve vakit bulunca bilişsel bilim bağlamında tekrar okumak istediğim ender kitaplardan.

LKD Yılın Penguenleri Ödülleri Sahiplerini Buldu

adervis

Şenlik ile birlikte geleneksel hale gelen, Linux Kullanıcıları Derneği Yılın Penguenleri Ödülleri, Şenliğin sonunda yapılan kapanış partisinde sahiplerine verildi. Özgür yazılım dünyasına yaptıkları katkılardan dolayı Yılın Penguenlerini tekrar kutluyoruz.

Almanya e-işçi arıyor

FZ

Avrupa'nın endüstri lideri olmasına rağmen aynı zamanda dev nüfusuyla en yüksek işsizlik oranına sahip Almanya'da çeşitli sebeplerle yurtdışına göç edenlerin sayısı 2. Dünya Savaşı rakamlarına yaklaştı. Ülke bu durumun en çok etkilediği bilişim alanında acil önlem kararı aldı.

Yeni Din `Jedi Knights´ resmileşti(mi?)

butch

Mart ayının başlarında Yeni Zelanda'da nüfus sayımı yapılacağı sıralarda ortalıkta dolanan bir e-posta hakkında Slashdot'da yayınlanan bir haber oldukça ilgimizi çekmişti. Mesaj Star Wars fanatiklerinin kurdukları yeni dine üye olmaları için insanlara bir çağrı niteliğindeydi. Yeni dinin adı "Jedi Knights" yani Jedi Şövalyeleri.
Yeni Zelanda'da neler oldu bilmiyorum ama İngiltere'de 2001 yılı nüfus sayımı formları ve getirdiği sonuçlar oldukça ilginç...