Yazan : Şadi Evren ŞEKER

Pollard’s rho çarpanlara ayırma metodu (factorization), büyük asal sayıların hızlı bir şekilde çarpanlara ayırılmasını amaçlamaktadır. Veri güvenliği (kriptoloji) açısından oldukça önemli olan bu yöntemin çalışması aşağıdaki adımlardan oluşur:

  • Çarpanlarına ayrılmak istenen sayının n olduğunu kabul edelim.
  • Bulacağımız çarpan d olarak isimlendirilecektir ve d sayısı d | n şartını sağlayacaktır (tam bölecektir)
  • Algoritma sırasında kullanılacak iki değişken olan a ve b değerlerine 2 atayarak başlıyoruz. a 2, b ←2
  • Bir döngü içerisinde, sonucu bulana kadar aşağıdaki adımları takip ediyoruz:
  • aa2+1 mod n, bb2+1 mod n, bb2+1 mod n
  • Yukarıdaki satırdan anlaşılacağı üzere a sayısının 1 kere karesi alınıp arttırılıyorken, b sayısı iki kere aynı fonksiyona tabi tutulmaktadır. Dolayısıyla b sayısı, a’ya göre daha hızlı ilerlemektedir.
  • d = gcd (a-b, n) değeri hesaplanır.
  • Şayet 1<d<n şartını sağlayan bir d değeri bulunuyorsa başarıyla tamamlanmıştır ve işlem bitirilir.
  • Şayet d=n durumu oluşursa algoritmayı başarısız bir şekilde sonlandırıp daha fazla devam etmiyoruz.
  • Yukarıdaki iki durum dışında döngümüze devam ediyoruz.

Yukarıdaki algoritmayı bir örnek sayı üzerinde test edelim.

Çarpanlarına ayırmak istediğimiz sayı 187 olsun.

n ← 187

a←2, b←2

a22+1 mod 187, b22+1 mod 187, b52+1 mod 187 ( bu satırdan sonra a = 5, b = 26 olur. )

d = gcd (a-b, n) , d= gcd ( 5-25 , 187) =1 , dolayısıyla henüz sonuç bulamadık işleme devam ediyoruz. Bu adımı ve sonraki adımları aşağıdaki tabloda gösterelim:

a b a-b gcd(a-b,n)
22+1 mod 187 (22+1) 2+1 mod 187=26 -21 1
52+1 mod 187=26 (262+1) 2+1 mod 187=180 -154 11

 

Yukarıdaki tabloda görüldüğü üzere sayının çarpanlarından birisinin 11 olduğu bulunmuştur.

Farklı bir örnek yapıp aynı durumu görmeye çalışalım. Örneğin çarpanlara ayırmak istediğimiz sayımız n = 87463 olsun.

a b a-b d
5 26 -21 1
26 21015 -20989 -1
677 21634 -20957 1
21015 5536 15479 1
29539 26558 2981 1
21634 4917 16717 1
15444 65711 -50267 -1
5536 -48077 53613 1
35247 -23506 58753 1
26558 79715 -53157 -1
25733 38437 -12704 -1
4917 -21802 26719 1
37102 -11916 49018 1
65711 33219 32492 1
52920 78001 -25081 1
-48077 20372 -68449 1
-83452 57576 -141028 -1
-23506 78754 -102260 -1
28266 12329 15937 1
79715 -22519 102234 1
22669 -37328 59997 1
38437 72544 -34107 1
65437 -41348 106785 1
-21802 43017 -64819 -1
53263 19222 34041 1
-11916 45450 -57366 1
38608 31967 6641 1
33219 -63715 96934 1
68754 44914 23840 149

 

Sonuç 149 olarak bulunmuştur.

Yukarıdaki bu işlemleri yapan kodu aşağıdaki şekilde C dilinde yazabiliriz:

Yukarıdaki kodda kullanılan obeb() fonksiyonu, daha önce sitede yayınlanan ilgili yazıdaki koddan alınabilir.

Ayrıca yukarıdaki kodda da f() olarak görülen fonksiyonun değiştirilerek sistemin hızlandırılması mümkündür. Bu örnek kapsamında aa2+1 mod n fonksiyonu kullanılmıştır.

Bir Cevap Yazın

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


1 × = dört