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

Google Maps Navigation

auselen

Google'ın yeni navigasyon uygulaması Android için duyuruldu.

Buraya kadar herşey klasik bir Google haberi gibi, fakat burada verilen bilgiyi gördüğünüzde teknoloji devinin diğer şirketlerin oyun planını nasıl bozduğunu anlıyorsunuz. Bu durumu normal karşılayanlara Garmin'in aynı gün için de 1.2 milyar dolardan olduğunu ve hisse sahiplerinin bu gibi durumlara ne kadar kısa sürede tepki verebildiğini hatırlatmak isterim.

Eğer aklınızda süper bir fikir varsa ve bunun üzerinden uzun süre yüklü meblağlar kazanacağınızı umuyorsanız, unutmayın! Google sizi her zaman yanıltabilir... Tıpkı diğer alanlarda yaptığı gibi...

Symantec Büyümeye Devam Ediyor

parsifal

Bünyesine kattığı firmalarla büyümeye ve gelişmeye devam eden Symantec, en son Vontu'yu da Symantec ailesine dahil etti.

PostgreSQL 7.3 duyuruldu

madness

PostgreSQL Global Development Group, nesne-ilişkisel (object-relational) Veritabanı Yönetim Sistemi (ORDBMS) olan PostgreSQL’ in 7.3 sürümünü duyurdu.

Dünyanın en gelişmiş açık kaynak kodlu veritabanı yönetim sistemi olan PostgreSQL, firmalara ve devlet kurumlarına günümüzde kullanımda olan ve çok gereksinim duyulan uygulamalar için çözümler sunar ve her yıl milyonlarca doların kurumların kasasında kalmasını sağlar.

Aşağıda, PostgreSQL kullanıcılarından bazılarını bu teknoloji hakkında söylediklerini bulabilirsiniz:

Küba Açık Kaynak Peşinde

ali_deren

Venezüella'nın lideri Hugo Chavez, ilginç muhalefet tarzıyla unutturduğu Küba Başkanı Fidel Castro'ya da ilham kaynağı oldu. Chavez'in ülkesini uluslararası yazılım tekellerinden kurtarmak için başlattığı açık kaynaklı yazılım ve sistemlere dönüş hamlesine Küba da destek vereceğini açıkladı.

gOS: Yeni Bir Kavram

erika

Birçok Web 2.0 uygulamasını içeren alternatif bir işletim sistemi üretilmiş, adı ''gOS'', Ubuntu tabanlı. Şuradan indirebilirsiniz. Sitede Google ile bir alakalarının olmadığı belirtilmiş. Bu işletim sistemi özellikle Google uygulamalarının ve diğer bedava yazılımların daha geniş kitlelere ulaşması için yapılmış. WalMart'da 199$'a çıkan gPC'de bu işletim sistemi yüklü. Yok satmış. :-) Türkiye'de 199$'a satılan bir laptop olsa ne iyi olur.