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

Csound, HPKComposer, Videolar, Sesler ve İkili Evren

FZ

http://avsynthesis.blogspot.com/ ses ve hareketli görüntü sentezleme ile ilgili eğlenceli videoların yer aldığı bir site. Sitedeki videolar HPKComposer ile gerçekleştirilmiş ve müzikler herhangi bir ses örneklemi (sample) ya da nota tabanlı olmayıp tamamen csound ses üreteçleri kullanılmış.

Noam Chomsky İstanbul Bilgi Üniversitesi´nde

FZ

Özgürlükleri teftiş için 13 Şubat’ta Türkiye’ye gelen Noam Chomsky, İstanbul Bilgi Üniversitesi’nde konferans veriyor ve Üniversite bu vesileyle, çağımızın en önemli entellektüellerinden Chomsky üzerine yapılmıs bir belgeseli 10 Şubat’ta gösteriyor.

Dünyaca ünlü Amerikalı düşünür ve dilbilimci Noam Chomsky 13 Şubat Çarşamba günü saat 16.00-18.00 arasında İstanbul Bilgi Üniversitesi Dolapdere Kampüsü’nde, “11 Eylül ve İletişim” konulu bir konuşma yapacak.

HP SnoSoft`u DMCA kurallarına gore dava edecek.

conan

HP, dün işletim sistemi Tru64de bir guvenlik açığı bulan ve bu açığı kullanarak root access elde edilmesini sağlayan bir programı Bugtraq`da yayınlayan SnoSoft`u Digital Millennium Copyright Act (DMCA) yasalarına dayanarak dava edeceğini açıkladı. HP`nin Baskan Yardımcısının demecine göre SnoSoft`un her bir üyesi 500.000`er bin $ ve 5 yıla kadar mahkum olabilecekler.

Konu ile ilgili ilginç tartışmalar Slashdot`da alevlendi bile. Özellikle Bruce Perens`in bu konudaki yorumları ve tutumu oldukça ilginç. (Kendisi HP`nin Open Source departmanında Senior Strategist olarak görev almakta)

Turkcell yine coştu

kuzen

Sağolsun turkcell tarifelerini yeniden değiştirmiş. Bakalım ne yapmış...
Turkcell'den Turkcell, Hazır Kart ve Muhabbet Hat'tı arama BizbizeCell tarifesinde 150 bin lira oldu. Turkcell'den yapılan açıklamada, Turkcell tarifelerinde bugünden itibaren geçerli olmak üzere değişiklik yapıldığı belirtildi. Açıklamada belirtilen tarifeler şöyle: "Aylık sabit ücret, StandartCell'de 2 milyon 565 bin 217 bin, BizbizeCell'de 958 bin lira. Turkcell'den, Turkcell, Hazır Kart ve Muhabbet Hat'tı aramak StandartCell'de 289 bin 790, BizbizeCell'de 150 bin lira. Hazır Kart ve Muhabbet Hat'tan, Turkcell, Hazır Kart ve Muhabbet Hat'tı aramak StandartCell'de 519 bin 860, BizbizeCell'de 207 bin 944 lira." Açıklamada, Turkcell'den diğer operatörleri ve sabit telefonları arama bedelinin StandarCell'de 371 bin 711, BizbizeCell'de 449 bin lira olarak belirlendiği kaydedildi. Hazır Kart ve Muhabbet Hat'tan diğer operatörleri ve sabit telefonları arama bedeli ise StandartCell tarifesinde 519 bin 860 lira, BizbizeCell tarifesinde ise 623 bin 832 bin lira olarak belirlenmiştir.
Tüm türkcell abonelerine yorumsuz olarak duyurulur,ama yorum yapmanız serbest......

Sendo - Micros~1 anlaşmazlığının iç yüzü.

conan

Sendo ve Microsoft arasında halen süregelmekte olan dava ve olayların iç yüzünü anlatan bu yazıya bugün /.'da rastladım. Gerçi geçenlerde çok tartıştığımız o habere yorum olarak attım, ama bu ikinci bir haber yazılası kadar önemli bir köşeyazısı bence.

Yazi kısaca M$`un ortağına verdiği sözleri nasıl tutmadığını, StingerOS isimli cep telefonu işletim sistemini geciktirerek ortağının batmasını nasıl hazırladığını güzelce gösteriyor. Artı, şirketin board'unda bir yonetim hakkı olması ve şirketin 12 milyon dolarlık hissesine sahip olmasına rağmen şirketi ugradıgı zarardan bilinçli bir şekilde kurtarmaması, iki şirket arasında yapılan anlaşmadaki ilginç maddeler gibi yan fikirleri de aynı yazıdan okuyup öğrenebilirsiniz.