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:
- a←a2+1 mod n, b←b2+1 mod n, b←b2+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
a←22+1 mod 187, b←22+1 mod 187, b←52+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 a←a2+1 mod n fonksiyonu kullanılmıştır.