Yazan : Şadi Evren ŞEKER

Verilen bir sayının asal sayı olup olmadığının bulunması, bilgisayar bilimlerinde, özellikle veri güvenliği (kriptoloji) konusunda oldukça önemlidir. AKS asallık testinin ismi, yöntemi geliştiren üç kişinin isimlerinden türetilmiştir. ( Agrawal, Kayal, Saxena)

Yöntemin dayandığı matematiksel yapı aşağıdaki denklemdir :

(x – a)n (xn – a) mod n

Aslında bu denklem, Fermat’ın küçük teoreminin genişletilmiş halidir ve n ile aralarında asal olan (coprime) a değerlerini bulmaya yarar.

Algoritmanın çalışması aşağıda verilmiştir:

  • Şayet a>0 ve b>1 için n = ab eşitliği sağlanıyorsa, n sayısı asal değildir.
  • or(n) > log2(n) denklemini sağlayan en küçük r değeri bulunur.
  • Şayet 1 < gcd(a,n) < n denklemini sağlayan bir ar değeri bulunabiliyorsa sayı asal değildir.
  • Şayet nr ise n asal sayıdır.
  • değerine kadar olan değerler için
  • Şayet (X+a)nXn+a (mod Xr − 1,n) eşitsizliği sağlanıyorsa sayı asal değildir.
  • Yukarıdaki şartlardan geçerse, sayı asaldır.

Yukarıdaki algoritmada kullanılan sembolü, Öyler’in Totem fonksiyonudur (Euler’s totient function). Aynı zamanda or(n)  fonksiyonu da çarpım derecesini (multiplicative order) belirtmektedir.

Yukarıdaki algoritmanın çalışmasını bir örnek sayı üzerinden anlatalım.

Örneğin asal olup olmadığını merak ettiğimiz sayı 119 olsun.

Sayımızın asal olup olmadığını kontrol etmek için öncelikle ihtiyaç duyduğumuz değişkenlere atama yapıyoruz.

r= 2’den başlayarak işlem yapacağız. Öncelikle log2(n) değerini hesaplayalım.

log2(119) = 6,89 olarak bulunur.

obeb(n,r) yani obeb(119,2) değeri 1’dir. Yani 119 ile 2’nin en büyük ortak böleni 1 olduğu için bu iki sayı aralarında asaldır (coprime).

r sayısının asal olup olmadığına bakıyoruz. Sayı asal olduğu için çarpım derecesi olan on(r)  hesaplanıyor. o119(2) =24 olarak bulunur.

Bulunan bu değer için en küçük r değeri hesaplanmak istenir ve on(n) > log2(n) büyüklüğündeki en küçük derece bulunana kadar işlem devam eder.

derece değeri önce 20 ardından 16’ya düşebilmektedir. Bunun için r değeri önce 3 ardından 5 olmaktadır. Diğer bir deyişle r = 3 için derece 20 ve r = 5 için derece 25 olmaktadır. r=4 değeri denenmemiştir çünkü yukarıda da belirtildiği üzere r asal sayı olmak zorundadır.

Bir sonraki adımda r = 7 için hesaplama yapılacak. Ancak tam bu noktada sayının asal olmadığını söyleyebiliriz çünkü obeb(119,7) = 7 dönmektedir.

Yukarıdaki algoritmanın kodlanmış hali aşağıda verilmiştir.

Bu kodda bulunan obeb fonksiyonunu, obeb (gcd) başlıklı yazıdan ve carpimDerecesi isimli fonksiyonu, çarpım derecesi (multiplicative order) başlıklı yazıdan alabilirsiniz.

 

 

 

 

Yorumlar

  1. Süha

    Hocam, cehaletimi mazur görün lütfen.
    1. Yazının en başındaki formülde yer alan “n” değeri herhalde ele aldığımız sayıyı temsil ediyor. Diğer x ve a değişkenlerinin neyi temsil ettiğini anlayamadım.
    2. Bu yöntemde logaritma kullanılıyor. Çok büyük sayıların, örneğin 150 haneli bir sayının logaritması nasıl hesaplanıyor? Programlamada “overflow” hatası alınmaması için bana bir yol gösterir misiniz?

  2. Şadi Evren ŞEKER Article Author

    1. x ve a sayıları herhangi bir tam sayıdır (arbitrary integer). Yani örneğin n = ab eşitliğini sağlayan en az bir tane a ve b ikilisi bulunabiliyorsa denmek istenmiştir. Dolayısıyla asal olmanın bir şartı olarak bütün a ve b ihtimallerinin elenmesi beklenir.
    2. aslında logaritma alınıyor olması hem iyi hem de kötü. Burada tam sayılar ile uğraşıldığını ve alınan logaritmanın aslında ayrık logaritma (discrete logarithm) olduğuna dikkat edelim. Daha önce bir iki yazı yazıp yayınlamıştım fikir verebilir:

    http://www.bilgisayarkavramlari.com/2011/02/11/bebek-ve-dev-adimi-baby-step-giant-step/
    http://www.bilgisayarkavramlari.com/2011/02/11/shank-algoritmasi/

    Başarılar

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir