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

Pil teknolojilerinde devrim mi?

elrond

Motorola pil endüstrisinde büyük bir devrim sayılabilecek yeni teknlojisinin başarılı tanıtımını yaptı.
Metan gazı kullanarak pil hücrelerinden üretilen yeni piller cep telefonlarında ay mertebesinde kullanma süresi sağlıyor. Bu teknolojide önemli endişelerden biri ısı problemi idi. Tanıtımlarda Motorola'nın bu problemi aştığı gözlenmiş. Hücrelerdeki Metan kimyasal reaksyonlar sonucunda oksijen, ısı ve elektrik enerjisi açığa çıkarıyor. Bu enerji direkt kullanılabileceği gibi Motorola'nın case'inde olduğu gibi telefona elektrik sağlayan diğer pilleri şarj etmek içinde kullanılabiliniyor.

BurningMan.com

sundance

Bir arkadaşımın tavsiyesi ile girdiğim ve gözlerime inanamadığım bir site BurningMan.com

BurningMan 1986`da Larry Harvey tarafından Baker Beach`de başlatılan bir installasyon. 2,5 metre yüksekliğinde tahtadan bir adam yapıp onun yakılması, yaklaşık 20 kadar insanın etrafta toplanması, o an çıkan bir synerjik kıvılcımla bunun senelik bir toplantı haline gelmesi ve en sonunda 2000 yılında 12 metre yüksekliğinde bir burningman ve 25,400 katılımcı ile muazzam bir birliktelik halini alması...

Internet yönü de önemli olan bu etkinliği diğerlerinden ayıran bazı yanları var...

Bilgi Üniversitesi Araştırma Görevlisi Kadrosu

vst

Bilgi Üniversitesi, Bilgisayar Bilimleri Bölümü için araştırma görevlisi arıyor.

Bilgi Üniversitesi Bilgisayar Bilimleri Bölümü teoriye önem veren bir bölümdür. Bunun yanında, Türkiye'de Özgür ve Açık Kaynak Kodlu Yazılımı desteklemek ve geliştirmek üzere çalışmalar yapmaktadır.

Başvurularda aranan temel özellikler:

  • Bilgisayar bilimlerine yoğun ilgi,
  • Zor bir konuyu öğretme konusunda istekli olmak,
  • İlgili alanlardan iyi bir lisans derecesi,
  • Tümüyle İngilizce dilinde öğretebilecek seviyede İngilizce bilmek,
  • İlgili bir alanda yüksek öğrenim programına kayıtlı olmak veya bu konuda girişimlerde bulunmuş olmak.

Başvurular eposta aracılığıyla cs@cs.bilgi.edu.tr adresine, özgeçmiş ekiyle yapılacaktır.

RIAA P2P ağlarını zehirlemiş!

murat09

Geçtiğimiz günlerde dili çözülen Matt Warne adlı bir bilgisayar uzmanı, müzik ve film endüstrisi hakkında uzun zamandır dillendirilen bir iddiayı doğruladı. Matt Warne, itirafında 76 ülkeden bin 500 müzik şirketini temsil eden RIAA (Recording Industry Association of America) adına takas ağlarını 'zehirlediğini' kabul etti.

www.freelance-tr.org açıldı

kefukar

freelance-tr.org siz programcı ve webmaster'ları Türkiye'deki firma sahipleri ve özel çözüm arayan yöneticilerle buluşturmak için aracı bir portal olarak hizmetinizde.