Yazan : Şadi Evren ŞEKER
Bir sayının asal çarpanlarına ayrılması için kullanılan yöntemlerden birsidir. Yöntemin ismi kalbur probleminden (sieving problem) gelmektedir.
Sayı alan kalburu (NFS), yapı olarak bir Ferma’nın çarpanlara ayırma sistemine dayanan (Fermat’s Factorization) bir denklik elde etmek ister. Buna göre amacımız a2 = b2 mod n şeklinde bir denklik yakalamaktır. Bu denklik elde edilebilirse obeb(x-y, n) şeklinde bir çarpan bulunabilir.
NFS sisteminin çalışmasını bir örnek üzerinden anlamaya çalışalım. Örneğin çarpanlarına ayıracağımız sayı n = 20437 olsun.
Öncelikle bu sayıyı veren bir çok terimli (polinom) üretmeye çalışıyoruz. Çok terimlinin özelliği bir m E Z için p(m) = 0 mod n vermesi olacaktır. Bu polinom aynı zamanda mod n için bir halka oluşturacaktır. Polinomu üretmeye m-taban yöntemi ile başlayabiliriz (base-m method).
Öncelikle sayımızın küp kökünü alarak başlayalım. Bu kök alma işlemleri sırasında sürekli olarak taban (Floor) fonksiyonu kullanacağız çünkü kalan değerlere ihtiyacımız var. Sayımızın küp kökünün tabanı 27 yapmaktadır. M-taban yöntemi gereği bu sayının bir eksiğini alarak başlıyoruz:
Elde edeceğimiz polinomun ilk terimini bulduk. Bu terimin çarpanı bulunmayacaktır. Diğer terimleri ise daha düşük üstlerden çarpanlar ile yazacağız.
Buna göre ( 20437 – 263 ) / 262 = 4 bulunur.
Ardından (20437 – 263 – 4. 262 ) / 26 = 6 bulunur.
Son olarak 20437 – 263 – 4. 262 – 6 . 26 = 1 bulunur. Bu durumda aşağıdaki eşitliği yazabiliriz:
20437 = 263 + 4. 262 + 6 . 26 + 1
Bu eşitliği bir polinom şekline getirirsek:
x3 + 4 x2 + 6 x + 1
polinomunu elde etmiş oluruz.
Buradaki önemli bir nokta:
x3 = -( 4 x2 + 6 x + 1) olarak yazılabildiğidir. Bu denklemi ileride kullanacağız.
Artık problemimiz, 20437 sayısını çarpanlarına ayırmaktan, yukarıdaki polinomu çarpanlarına ayırmaya dönüşmüştür. Problemin bundan sonraki kısmında bir polinomu kalansız bölen farklı polinomlar olup olmadığına bakacağız.
Öncelikle polinomumuz 3. dereceden olduğu için, çarpanı varsa, bu çarpanların birisinin 1. dereceden olduğunu söyleyebiliriz. O halde polinomumuzun bir çarpanının ax + b yapısında olmasını bekliyoruz.
Tam bu noktada durup bir polinomun çarpanlara ayrılmasının, sayıları nasıl çarpanlara ayırdığını anlamaya çalışalım. Öncelikle asal sayı kümesinden belirli bir miktarda eleman alalım. Örneğin ilk 6 asal sayıyı alarak başlayalım :
P = {2,3,5,7,11,13 }
Yukarıdaki kümeye -1 değerini ekliyoruz. Bunun sebebi, polinomu çarpanlara ayırdığımızda eksi değerlerinde çıkabilmesidir.
Q= {-1,2,3,5,7,11,13}
Kümesini elde ettikten sonra rast gele polinomlardan oluşan (ve derecesi 2’den küçük olan) bir küme daha oluşturuyoruz:
A = {-x , -1 –x , 2-x + x2 , -2 + 3x + x2 , 3 + x , -5 -3x –x2 }
Şimdi yukarıdaki kümeleri kullanarak bir polinomu ve dolayısıyla bir sayıyı çarpanlarına ayıralım. Örneğin çarpanlarına ayırmak istediğimiz polinom 4+2x olsun.
4 + 2x = (-1 –x) (-5 -3x –x2) şeklinde yazılabilir. Bu gösterimde kullanılan iki polinom ise A kümesinin 2. ve 6. elemanlarıdır.
Yukarıdaki denklemin eşitlenmesi sırasında, basit bir soru nasıl olup 3. dereceden bir polinomun (eşitliğin sağ tarafı), 1. dereceden bir polinoma dönüştüğü şeklinde sorulabilir. Bunun sebebi, daha önce belirttiğimiz ve ileride kullanacağız dediğimiz x3 = -( 4 x2 + 6 x + 1) denklemini kullanarak polinomun sağ tarafını basitleştirmiş olmamızdır.
4 + 2x = (-1 –x ) (-5 -3x –x2) = A2A6
Şimdi m = 26 için yukarıdaki denklemi çözelim:
A2A6 (m) = 4+2m = 4+2.26 = 56 = 23. 7
Yukarıdaki denklemde görüldüğü üzere, sayının asal çarpanları bulunmaktadır (2 ve 7 asal sayılardır).
Bu durumda sayımızı kabul ediyoruz. Yani bizim için A2A6 (26) kabul edilen bir sayıdır çünkü 26 sayısının polinom gösteriminde çıkan değerleri yine Q kümesinin elemanları cinsinden yazılabilir. Burada dikkat edilecek bir husus, çıkan değerin sadece asal olmasının yetmediğidir.
Çıkan sayı kesin olarak Q kümesinin üyesi olmalıdır. Örneğin A5(m) polinomunu 26 sayısı için test edelim.
A5(m)=3+m = 3 + 26 = 29
Yukarıdaki sonuca göre, 29 sayısı asal bir sayıdır ancak bu sayıyı kabul etmiyoruz. Çünkü, başta tanımladığımız Q kümesinin elemanı değildir.
Neticede, inşa ettiğimiz Q ve A kümelerinden (asal sayılar kümesi ve polinomlar kümesinden) aşağıdaki gibi bir matris oluşturuyoruz :
Yukaırdaki matriste her satır, ilgili A ve Q kümesi açılımına işaret etmektedir.
Örneğin 3. satırı ele alalım.
1010100 020020
Bu satırın, sağ tarafının anlamı A2 ve A5 elemanlarının karelerinden oluşan polinomdur.
A22A52
(-1-x)2 (3+x)2 = 5-x olarak bulunur.
Sol tarafı ise Q kümesinin elemanlarıdır. Buna göre küme elemanlarından -1, 3 , 7 seçilmiştir. Bu değerlerin çarpımı ise -21 yapar.
Gerçekten A22A52(m)= 5-m denklemi m = 26 için A22A52(26)= 5-26 = -21 değeri Q matrisindeki değerlere eşit olarak bulunur.
Yukarıdaki matrisin ve denklemlerin tek amacı, a2=b2 mod n şeklinde bir denklem elde ederek Ferma’nın çarpanlara ayırma yöntemini kullanmak olduğunu hatırlarsak. Yukarıdaki matris ile elde etmek istediğimiz yapı, denklemin her iki tarafında da ikinin katları şeklinde bir denklik elde etmektir. Bu
Örneğin yukarıdaki matriste, 2. 3. 4. ve 6. satırların toplamıyla elde edilen sonuca bakalım:
1030000 010000
1010100 020020
0300100 010001
0100002 000201
———————-
2440202 040222
Yukarıdaki toplam, görüldüğü üzere çift sayılardan oluşmaktadır. O halde bu sayıların yarılarını elde ederek fermanın çarpma yöntemini uygulayabiliriz.
1220101 denkleminin açılımı (Q kümesindeki ilgili elemanların ilgili üstleri)
-1 . 22 . 32 . 7 . 13 = -3276
020111 gösteriminin açılımı (A kümesindeki ilgili elemanların ilgili üstleri alınarak)
B = (-1-x)2 (-2+3x+x2) (3+x) (-5-3x-x2) =26 + 30x + 16x2
B(m) = 26 + 30m + 16m2 olarak bulunur.
Bu denklemi m = 26 için çözersek :
26 + 30. 26 + 16.262 = 11622 olarak bulunur.
Kısacası ulaştığımız sonuç aşağıdaki şekilde özetlenebilir:
-32762 = 116222 mod 20437
Buradan sonra gcd(3276+11622, 20437) işlemi yapılarak çarpanlardan birisi bulunabilir. Bu değer 107 olarak bulunur.
20437 = 107 . 191 olarak bulunmuş olunur.