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

Türkiye'de Site Kapatmalarının Hukuki Altyapısı

FZ

Az önce bize önce telefon ile ulaşan ve ardından e-posta yazan bir Türk Telekom haberleşme mühendisi FM okurunun mesajını olduğu gibi paylaşıyoruz.

"Türkiye’de Site Kapatmalarının Hukuki Altyapısı

18 Yaşında Belediye Başkanı Oldu

melitical

ABD'nin Michigan eyaletine bağlı küçük bir kasabada yapılan belediye başkanlığı seçimini 18 yaşındaki Michael Sessions kazandı. 9000 nüfuslu ilçeyi kapı kapı dolaşan Michael seçim masrafları için yazın biriktirdiği 700 doları kullanmış.

Dünya´nın En Hızlı Ticari Treni Hizmete Giriyor

conan

Şangay'ın 30 km kuzeyinde bulunan Pudong uluslararası havaalanını şehre bağlayacak olan yeni manyetik tren şu ana kadar hizmete girmiş en hızlı ticari tren ünvanını alacak gibi gözüküyor. Trafikte şanslıysanız yaklaşık 40 dakikada alabileceğiniz bu mesafeyi yeni tren yaklaşık 7 dakikada alıyor. Trenin yaptığı maksimum hız 430 km/h. Tren bu hıza yaklaşık iki dakika içerisinde ulaşıyor. Manyetik trenlerle ilgili güzel bilgileri ve de evde nasıl manyetik tren yapabileceğinizi anlatan yazıyı buradan okuyabilirsiniz.

e-bergi Temmuz Sayısı Çıktı!

anonim

ODTÜ Bilgisayar Topluluğu olarak, bilgisayar bilimi alanındaki Türkçe kaynak sıkıntısını gidermek amacıyla yayınlamakta olduğumuz elektronik dergi e-bergi , Temmuz 2008 sayısıyla bu ay da sizlerle...

TÜBİTAK Elektrikli Otomobil Üretti: Elit-1

FZ

Türkiye'nin ilk elektrikli otomobili, TÜBİTAK Marmara Araştırma Merkezi'nce (MAM) üretildi. 'ELİT-1' adı verilen taşıt, çalışıp çalışmadığı anlaşılmayacak kadar sessiz ve yüksek miktarda yakıt tasarrufu sağlıyor. Hem benzin hem de elektrikle çalışan 'hibrid elektrikli taşıt', şu anki düzeneğiyle 90 kilometre hıza ulaşıyor. Elektriği yakıt olarak kullanarak 130 kilometre mesafe kat ediyor. Benzinle çalışan araçlardan yüzde 50 tasarruflu.