Yazan : Şadi Evren ŞEKER

Fermat’ın çarpanlara ayırmak için (fermat factorisation) kullandığı yöntem iki kare farkı elde etmeye dayanır. Basitçe bir sayı şayet iki kare farkı şeklinde yazılabilirse

N = a2b2

Bu durumda N sayısını veren çarpanlar (a + b)(ab) şeklinde bulunmuş olur.

Bu teoriyi ilerletirsek

N = [(c + d) / 2]2 − [(cd) / 2]2

Şeklinde yazılmasını sağlayan bir N=cd elde edilmiş olur. Yani ilk denklemde c=a+b ve d= a-b yazılacak olursa yukarıdaki bölümlerle elde edilen yeni sayılarda çarpan olarak elde edilebilir. Ancak çarpanlara ayırmak için genellikle ilk denklemden elde edilen (a+b) ve (a-b) çifti yeterli kabul edilebilir.

Örneğin çarpanlarına ayırmak istediğimiz sayı : 2919 olsun. Bu sayının karekökünden başlayarak sayıya kadar bütün ihtimallerin farkını alıp bir kare farkı elde edip edemeyeceğimizi kontrol edelim.

örneğin 59,80 ikilisi bu iki kare farkını elde edebildiğimiz sayılardır.

592 = 3481 ve 802 = 6400 olur ve 6400-3481 = 2919 sayısı bulunur. O halde

2919 = 802-592 şeklinde yazılabilir ve 2919 = (59+80) (80-59) =  139 x 21 olarak iki çarpanı bulunmuş olur.

Fermat teoremi özellikle şifreleme işlemleri sırasında çarpanlara ayırmaya dayalı zorluğa sahip RSA gibi yöntemlere saldırı için kullanışlıdır.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Fermat çarpanlara ayırma teoremi basitçe bir sayıyı iki kare farkı şeklinde yazmaya dayanır. Daha basit olarak anlatacak olursak çarpanlarına ayırmak istediğimiz bir sayıyı (a-b) (a+b) şeklinde yazmaya çalışırız. Bu iki sayı, yani (a-b) ve (a+b) de çarpanlarına ayırmak istediğimiz sayının çarpanları olmuş olur.
    O halde a2-b2 şeklinde bir yapı elde etmek için çarpanlara ayırlacak olan sayının karekökünden başlanarak arama yapılır. Bu arama yukarıdaki örnekte detaylıca gösterilmiştir.
    Belki de anlaşılamayan kısmı yazarsanız daha detaylı anlatabilirim.

    Başarılar

  2. Şadi Evren ŞEKER Article Author

    RSA metodunda n değeri umumi anahtardır (public key, açık anahtar) ve iki asal sayının çarpımından oluşur (RSA başlıklı yazıda p ve q olarak belirtilmiştir). Şayet bu asal sayıları bulabilirsek totient fonksiyonunu da bulabiliriz ( yine RSA başlıklı yazıdan φ(n) = (p-1)(q-1) olduğunu hatırlayınız).

    Ayrıca açık anahtar (public key) ile gizli anahtarın (private key, hususi anahtarın), birbirinin φ(n) değerine göre tersi olduğunu hatırlayınız. yani ed = 1 mod φ(n) dekliği söz konusudur.

    O halde açık anahtarları ve φ(n) değerini bilen bir kişi hususi anahtarı bulabilir. φ(n) değerini ise n değerini çarpanlara ayırarak bulabilir. Kısacası RSA sistemindeki n değerinin çarpanlara ayırılabilmesi güvenliğini tehdit eder. En azından benim ulaştığım kaynaklarda durum bu şekilde ama elbette bilmediğim bir nokta varsa ve paylaşırsanız sevinirim.

    başarılar

  3. Süha

    Hocam,
    Müsaadeniz olursa bu konuya bir katkıda bulunmak isterim. Malumunuz, çözümün dayandığı temel mantık, bir sayının iki kare farkı şeklinde yazılabiliyor olması. Özetle:
    N=x2 – y2 Buradan: y2 = x2 – N ifadesini yazabiliriz. Eşitliğin sol tarafının pozitif olabilmesi için x2 değerinin N’den büyük olması gerektiği açıktır. Bu nedenle x’in en küçük değeri x=int(sqrt(N))+1 (Nsayısının karekökünün 1 fazlası) olmalıdır. Bu değerden başlayıp x sayısını birer birer arttırarak, elde edilen y2 değerinin tam kare olup olmadığına bakmalıyız. İşte zorluk burada başlıyor. Eğer sayı yeteri kadar büyükse ve çarpanlar birbirine yeteri kadar uzaksa, yani biri nispeten çok küçük ve diğeri çok büyükse, yani bir çarpan karekökten çok uzaksa çözümü bulmak için çok fazla denemeye gerek vardır. Mesela 641*4114997=2637713077 eşitliğini ele alalım. En küçük x değeri 51359, çözümü sağlayan x değeri ise 2057819 sayısıdır. Kolayca anlaşılacağı gibi, klasik yöntemle bu x değerine ulaşılması için 2057819-51359=2006460 (iki milyon altıbin dörtyüz altmış) deneme gerekir. Halbuki yaptığımız iyileştirme sayesinde 401293 deneme ile sonuca ulaşılmaktadır. Demekki işlem sayısı klasik yöntemin yaklaşık 1/5 i kadardır.

    Malumunuz, bir sayının son rakamı o sayının tam kare olup olmadığı hakkında bir fikir verebilir. Son rakamı 2-3-7-8 olan sayılar tamkare olamazlar. (Bu husus, son rakamı bunlar olmayan diğer sayıların kesinlikle tamkare olacağı anlamına gelmiyor elbette. Keşke bir sayının tamkare olduğunu bir bakışta anlamayı sağlayacak bir yöntem olsaydı! Herhalde bazı kripto sistemleri çöpe giderdi.) Böyle bir y2 değeri elde edildiği zaman, bunun karekökünü almakla zaman harcamayıp, hemen diğer x sayısına geçebiliriz. Burada şöyle bir soru ortaya çıkıyor: Acaba hangi x değerleri, kesin geçersiz y2 değerlerini değil, sadece tam kare olabilecek (ama kesin değil) y2 değerlerini üretebilir? Bunu yapabilmek için sayının son bir değil iki rakamına bakmak daha fazla doğruluk sağlayabilir. Tamkare olan bir sayının son iki rakamı neler olabilir?

    Bunu bulabilmek için 1 den 99(dahil) a kadar sayıların karelerini aldım, ayıkladım ve şöyle bir dizi ortaya çıktı: “00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96” Ben buna “tamkare dizisi” diyorum (kare alma işlemini 100 den büyük sayılara uygulamaya gerek yok, bulacağımız değerler bu dizinin tekrarı olacaktır). Bir sayının (bu arada y2 sayısının) son iki rakamı 00-99 arasında olabilir. Biz, y2 nin tamkare olmasını sağlayabilecek x2 ve x değerlerini arıyoruz. O halde ana formülden:
    x2 = y2 + N yazalım. Bir örnek olarak, N sayımız 319 (11*29) olsun. Son iki rakamı 19. Bunu, formüle uygun olarak, tam kare dizisinin son iki rakamı ile topluyoruz. Sonuçlar:

    00+19=19 25+19=44 61+19=80
    01+19=20 29+19=48 64+19=83
    04+19=23 36+19=55 69+19=88
    09+19=28 41+19=60 76+19=95
    16+19=35 44+19=63 81+19=1(00)
    21+19=40 49+19=68 84+19=1(03)
    24+19=43 56+19=75 89+19=1(08)
    96+19=1(15)

    Şimdi, elde ettiğimiz bu son iki rakamların hangilerinin tam kare dizisinde bulunduğuna bakalım: 44 ve 00. Yani elde ettiğimiz x2 değerlerinin son iki rakamı bunlar olmalı. Yani x değerinin karesi alındığında sadece 44 ve 00 ile biten xkare değerleri çözümü sağlayabilir, bütün x değerlerinin sırayla karesini alıp, bu x2 kare değerlerinden N sayısını çıkarıp, karekökünü alıp, tamkare olup olmadığına bakmak gereksizdir. Peki, hangi x sayılarının kareleri 44 ve 00 ile biter? Bir sayının son iki rakamı 0-99 arasında olabilir, bu sayıları yazıp karelerini alalım (yani 0 dan 100 e kadar sayıların karesini alıp son iki rakama bakalım)
    00>>>sonu sıfır olan bütün sayıların karesi “00” ile biter,
    44>>>son rakamları 12-38-62-88 olan sayıların karesi “44” ile biter. Birleştirelim:
    x değerlerinin son iki rakamı 00-10-20-30-40-50-60-70-80-90-12-38-62-88 ile bitmelidir. Ben buna “x dizisi” diyorum. Son iki rakamı 00-99 arasında olabilen bütün sayıları denemektense bunlarla biten sayıları denemek daha iyi. (Bu değerleri bir dosyaya yazın, tekrar tekrar hesaplamayın, ben öyle yaptım. Gerektiğinde program içinde dosyadan okuturuz). Eğer 100-200 arasındaki sayılar denenecekse, klasik yöntemle deneme sayısı 101 dir. Bu yöntemle denenecek sayılar:
    100-200-110-120-130-140-150-160-170-180-190-112-138-162-188 olmak üzere 15 adet. Yani klasik yöntemin yaklaşık%15 – %20 si kadar işlemle sonuca ulaşabiliriz. Mesela, 17*641=10897 sayısının çarpanlara ayrılmasında klasik olarak 224 adet x değeri denenirken bu yöntemle işleme alınan x sayısı 45 adettir.
    Bu hususları gözönünde tutarak, gerek vb6 ve gerekse python ile yazdığım programların kaynak kodlarını paylaşmaktan (eğer bir mahzuru yoksa) zevk duyacağım.

    Kişisel yorumum:
    Hangi yöntem uygulanırsa uygulansın, büyük teksayıların çarpanlara ayrılması problemi zorluğunu korumaktadır. Fermat yöntemini büyük sayılarda uyguladığımızda karşımıza denenmesi gereken katrilyonlarca sayı çıkmaktadır ve bu durum karşısında herhangibir iyileştirme, denizde bir damla gibi kalmaktadır. Bu arada, katrilyon mertebesindeki bir sayının sadece 18 haneden oluşabileceğini, 150-200 haneli RSA sayılarının yanında esamesi bile okunmayacağını belirtmek gerek! Böyle bir hesaplama yükü süper bilgisayarları bile zorlamaktadır.
    Sorunun çözümü için, şimdiye kadar icadedilen ve uygulanan tüm yöntemlerin dışında, çok değişik yaklaşımlara gerek vardır. Çarpanlara ayırma konusunda olmasa bile böyle değişik yaklaşımlara iki örnek vermek isterim:

    1. Belirli bir aralıktaki asalların bulunması: Şimdiye kadar rastladığım en hızlı algoritma, “Eratosten kalburu” dur. Epey eski olmasına rağmen, denediğim tüm yöntemlerden hızlı olmasının en büyük nedeni, sayıları tek tek ele alıp herbirinin üzerinde birtakım işlemler yapmaması. Sadece bir dizideki sayıları üçer üçer, beşer beşer, yedişer yedişer…ilh. sayıp denk gelen sayıların üzerine “0” yazması. Bu kadar basit. Kendisinden sonra gelen ve daha gelişmiş olduğu söylenen Atkin kalburundan bile hızlı. Ukalalık demezseniz, zaten basit algoritmalar daima en iyileridir, kişisel kanaatim budur.

    2. Belirli bir aralıktaki sayıların toplamını hesaplamak: Örneğin 1- 1.000.000 arasındaki sayıların toplamını klasik yöntemle bulmaya çalışırsanız birmilyon toplama işlemi yapmak zorundasınız. Neyse ki, ünlü matematikçi Gauss bu probleme çok değişik biçimde yaklaşarak kendi adıyla bilinen formülü buldu. Sayı adedi*(son sayı+ilk sayı)/2>>>t=n(n+1)/2 Bu formüle göre yapacağınız işlem sayısı; bir toplama, bir çarpma ve bir bölme olmak üzere sadece 3 adet.

    Çarpanlara ayırma sorununun ancak böyle değişik yaklaşımlarla çözülebileceğini sanıyorum, bir gün mutlaka…

  4. Şadi Evren ŞEKER Article Author

    Katkınız için teşekkürler, kodlarınızı da içeren bu bilgileri bir word dosyası halinde email il yollarsanız isminizle sitede yayınlamaktan mutluluk duyarım.

    Başarılar

Süha için bir cevap yazın Cevabı iptal et

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