Çarpanlara Ayırma

Çarpanlarına ayırmamız için bir tamsayı verildiğinde akla gelen ilk yöntemlerden biri küçükten büyüğe doğru asal çarpanlarını ayıklamak olacaktır. Örneğin 1320 tamsayısı verilsin. Bu sayıyı sırasıyla 2, 2, 2, 3 ve 5 sayılarına böldüğümüzde 660, 330, 165, 55 ve 11 elde eder ve aşağıdaki sonuca ulaşırız:

1320=2^3\cdot 3\cdot 5\cdot 11

Yalnız bu metod her zaman bu kadar iyi çalışmaz. Rastgele büyük bir tamsayı aldığımızda, bu büyük tamsayının büyük asal çarpanlarının da olmasını bekleyebiliriz. Örneğin aynı metodu 1363 = 29\cdot 47 sayısına uygulamak isteseydik 29 sayısına kadar bölmemiz gerekecekti ve bu oldukça çok zaman alacaktı.

Şimdi işin içine birazcık matematik katalım ve modüler sayıları kullanalım. Modüler aritmetik yaparken farkında olmamız gereken en temel özelliklerden biri sıfırı bölen sayılardır. Mod n’de bu tür elemanların varlığı n sayısının asal olup olmamasına bağlıdır. Örneğin mod 35’te çalışıyorsanız ne 10 ne de 21 sıfır olmamalarına rağmen

10\cdot 21 = 0 \pmod{35}

olacaktır. Kendileri sıfır olmadığı halde çarpımları sıfır olan bu tür sayılara sıfırı bölen sayılar denir. Diyelim ki  n bileşik (asal olmayan) bir tam sayı olsun. Ve diyelim ki sıfırı bölen ama sıfır olmayan a ve b tam sayıları bulduk. O zaman bilgisayarların çok hızlı çalıştırabildiği OBEB algoritmasını kullanarak, n’nin bir çarpanını bulmak çok kolay olacaktı. Mesela yukardaki örnekte 35 sayısının bir çarpanın OBEB(10,35)=5 olduğunu bulmanın çok kolay olduğu gibi.

Bu yüzden çarpanlara ayırma sorusu yerine şu soruyu düşünebiliriz: Verilen bir n bileşik sayısı için mod n’de sıfırı bölen ama sıfır olmayan sayılar bulma işini ne kadar hızlı yapabiliriz? İşte burada devreye ikinci dereceden kalbur (quadratic sieve) giriyor. İkinci derece polinomlarını sağladığı x^2-y^2=(x-y)(x+y) eşitliğini kullanarak mod n’de sıfırı bölen sayılar üretebiliyoruz.

Örneğin geçen yazıda bahsettiğimiz 33499 sayısını düşünelim. 100’e kadar olan asal sayıların bu sayıyı bölmediğini deneyerek bulabiliriz. Ayrıca Fermat’ın küçük teoremini uyguladığımızda da bu sayının asal olmadığından da emin olabiliyoruz. Peki ama çarpanlarını nasıl bulacağız?

Verilen bir n tamsayısı için ikinci dereceden kalbur metodu bize öyle x ve y sayıları üretiyor ki x^2-y^2\equiv 0 \pmod{n} denkliği sağlanıyor. Yukarıda bahsettiğimiz sıfırı bölen ama sıfır olmayan x-y ve x+y sayıları sayesinde n sayısının çarpanlarını bulabiliyoruz.

Örneğin ikinci dereceden kalburu kullanarak 2206^2 - 1650^2 \equiv 0 \pmod{33499} denkliğini bulduğumuzu varsayalım. Bu denklik sayesinde OBEB(2206-1650,33499) = 139 ve OBEB(2206+1650,33499) = 241 sayılarının 33499 sayısını böldüğünü görmek çok kolay olacaktı.

Peki ama bu metod bütün sayılar için çalışmak zorunda mı? Yani verilen bir n tamsayısı için x ve y değerlerini makul bir süre aralığında bulabiliyor muyuz? Bu konuda cevaplanmamış bir çok teorik soru var ama deneysel olarak 100 basamağa kadar olan sayılarda bu metodun en iyi opsiyonumuz olduğunu söyleyebiliriz. En azından daha iyisi çıkana kadar.

Konunun biraz daha detaylı ele alınmış şekli ve referanslar için Wikipedia’nın quadratic sieve başlığına bakabilirsiniz. Ayrıca şöyle bir Türkçe sayfa da mevcut.

Reklamlar
Bu yazı Kriptografi, Sayılar Teorisi içinde yayınlandı ve , , , olarak etiketlendi. Kalıcı bağlantıyı yer imlerinize ekleyin.

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Connecting to %s