Asal sayı Algoritması

Bir problem uzerinde calisirken aklima geldi. girilen bir sayinin asal olup olmadigini incelemek icin bir program yazmaya karar versek, nasil bir algoritma izlemek gerekir. yani bir sayi girildi, sayinin asal olup olmadigina bakilacak, once 2 sonra 3, sonra 5, 7, 11, 13, 17 gibi asal sayilara bolmeye basliyoruz. peki ama bolecegimiz son sayi kac olmali? yani bu bolme ne zamana kadar devam edecek? sayimiz cok buyuk olabilir, ve biz bir asal sayi data base'i olusturamayabiliriz, yani bolecegimiz asal sayilari da programin bulmasi gerekebilir, bu durumda isler zorlasiyor. yani 10 digit'e kadar database olusturulsa da 50 basamakli bir sayinin asal olup olmadigini test edemeyiz.

Eger bir sayinin asal olup olmadigini kesin olarak ogrenmek istiyorsaniz sayinin karekokune kadar tum olasiliklari tek tek denemeniz gerekiyor (daha iyi bir yontem bilinmedigini saniyorum. Var olup olamayacagi tartismalari konusunda bilgim yok). Ote yandan eger verilen bir sayi icin "bu sayi cok buyuk olasilikla asal / bu sayi kesinliklle asal degil" ikilisi tatmin edici bir yanit olacaksa, baska algoritmalar var. Gunumuzde pratikte kullanilan yontem de boyle birsey. Algoritma asal sayilarin su ozelligine dayaniyor. n asal olsun. Eger herhangi bir k sayisinin n'inci kuvvetini alip n'e boldugunuzde kalan kismina bakarsaniz yine k elde edersiniz (Sozgelimi 3^7 mod 7'de 3'tur. Deneyelim: 2187=7*312+3). Ote yandan n asal degilse boyle bir gereksinim yoktur, sans eseri arada bir k elde edebilirsiniz ancak bu hesap çogu zaman tutmaz. Simdi diyelim ki n'in asal olup olmadigini test etmek istiyoruz. Yapilan su:

rastgele sayilar alin, hepsinin n'inci kuvvetlerini alip n'e bolunce kalanlara bakin. Diyelim ki her seferinde basladiginiz sayiyi elde ediyorsunuz. Bir noktadan sonra diyorsunuz ki "cok sayi denedik, bu sayi asal olmasaydi muhtemelen bir noktada yanlis cevap alirdik. Oyleyse cok buyuk ihtimalle bu sayi asal". Eger k^n mod n sadece bir k icin bile k'ya esit degilse hemen "bu sayi asal degil" diyebiliyorsunuz. Elbette bu test size sayinin kesin kez asal oldugunu soyleyemiyor. Fakat karekok(n)'den cok cok daha az sayida deneme n'in asal olduguna deneyiciyi yeterince inandirabiliyor. (Bu tur algoritmalara probabilistik algoritma diyorlar, kesin cevap verenlere ise deterministik). Bir itiraz su olabilir: "n buyuk bir sayi ise k^n cok cok buyuk bir sayi olacak. Bilgisayar bu sayiyi hesaplayabilecek mi". k^n'i oylece hesaplamaya calisirsaniz ilk tahmin edilenden cok daha kucuk sayilar icin bile hicbir bilgisayarin buna yetmeyecegi gorulebilir. Ama bu sorunu soyle cozebiliriz: k^n'i hesaplayip mod n'de bakacagimiza her carpimdan sonra sonucu mod n'de indirgeyerek isleme devam etsek de ayni sonucu elde ederiz (neden?) Ornek olarak 2^2000 mod 3'u hesaplayalim: 2*2 mod 3=1. 2^2000=(2^2)^1000 oyleyse mod 3'te 1^1000=1. Bu sorunu boylece halledebiliriz. Hemen ekleyeyim, bu testin sonucu olarak denediginiz sayinin asal olmadigi yanitini alirsaniz ortaya baska bir sorun cikiyor: sayinin carpanlari nedir? karekok(n)'e kadar deneyerek carpanlari da bulabilirdik, bu testte bu sansi kaybettik. Gercekten de gunumuzde bir sayinin asal olup olmadigini anlamak eger asal degilse carpanlarini bulmaktan cok daha az zaman aliyor. Oyle ki bircok bankanin, askeri sistemlerin, hatta internet sayfalarinin kullandigi sifreler bu iki islemin yapilabilme hizlari arasinda cok buyuk fark oldugu gercegini kullanarak yapilmis. Yine probabilistik metodlarla karekok(n)'den cok daha iyi zamanda sayilari carpanlara ayirabilen algoritmalar var, ancak bunlar bile asallik testinden cok cok daha yavas. Bircok amator (ve profesyonel?) sifre kirma meraklisinin hizli bir carpanlara ayirma algoritmasi bulup ortaligi dagitmak icin cilginca ugrastigini tahmin etmissinizdir. 

Son olarak, gectigimiz yillarda eger uygulanabilirse carpanlara ayirma algoritmasini gercekten hizlandiracagi inandirici gozuken bir fikir ortaya atildi: kuantum hesaplama. Fiyakali bir isim, altinda yatan temel fikir ise su: Cok kucuk boyutlara indigimiz zaman maddenin davranisi buyuk boyutta gozlemledigimize benzemiyor, kullanilan ve en iyi sonuc veren model olan kuantum fizigine gore bir parca bir noktadan bir noktaya giderken mumkun olan her yolu izliyor, kucuk olcekte ise bunun ortalamasini goruyoruz (isigin duz cizgi uzerinde gittigini "zannettigimiz" gibi). Eh, bir parcacik birkac yolu birden ayni anda takip edebiliyorsa bunu akillica kullanip o parcaciga ayni anda bir suru is yaptirmak mumkun olmali. Tipki birden cok islemcinin ayni anda paralel islem yapmasi gibi. Tabi bunun nasil yapilacagi, yapilip yapilamayacagi tamamen muallakta. Ancak buyuk bir arastirma alani, fikir babasi da gectigimiz sene alanindaki en buyuk odulu aldi. Bilgisayarlarda devrim yaratacak pratik sonuclarini da gormemiz mumkun onumuzdeki senelerde...

Özgür Kişisel

Alıntı:http://www.yapay-zeka.org/modules/icontent/index.php?page=26