1024 Bit Asal Sayı Üretmenin Zorluğu

• Giriş
  • Asal sayılar kolay açıklanabilmesine rağmen muazzam bir karmaşıklık barındırır
  • Matematiksel kavramlarda, ilginç görselleştirmelerde, kriptografi gibi çeşitli alanlarda kullanılır
  • Kodlama ile asal sayı üretimini denemeye karar verildi
• Zorluk
  • RSA algoritması için kullanılabilecek asal sayı üretmek
  • Şu anda RSA anahtarı için uygun bit uzunluğu 2048 olduğu için 1024 bitlik iki asal sayıya ihtiyaç vardır
  • Kısıtlar:
    • Baştan sona doğrudan kod yazmak (harici bağımlılık olmadan)
    • Yalnızca dizüstü bilgisayarın AMD Ryzen 7 CPU’su ve 16 GB RAM’i kullanmak
    • “Mantıklı” sürede asal sayı üretmek
  • Rust dili seçimi
• 16 bit asal sayı üretimi
  • Rastgele sayı üretimi için /dev/urandom adlı yalancı rastgele sayı üreteci kullanımı
  • Basit bir asal test yöntemi olan deneme bölme (Trial Division) kullanımı
  • Ortalama 40 ms içinde 16 bit bir asal sayı üretmek mümkün oldu
• 64 bit asal sayı üretimi
  • Optimize edilmiş deneme bölme algoritması uygulandı
    • Yalnızca 6k±1 biçimindeki sayılar kontrol edildi
    • Küçük asal sayı listesini önceden oluşturarak kolayca bölünebilen sayılar önce elendi
  • Optimizasyondan sonra yaklaşık 6 saniye sürdü
  • Daha büyük sayılar için deterministik algoritmaların sınırları vardır
• Olasılıksal asal test yöntemleri
  • Fermat’ın Küçük Teoremi kullanıldı
    • Bileşik sayılar da koşulu sağlayabilen “Sahte Asallar” (Pseudoprimes) sorunu bulunur
  • Miller-Rabin Asal Testi
    • Fermat testinin geliştirilmiş bir olasılıksal çeşidi
    • Bileşik bir sayı hiçbir tabanda her zaman sahte asal olmaz
    • Hata olasılığı çok düşük olduğu için pratikte kullanılabilir
• 128 bit asal sayı üretimi
  • Miller-Rabin testiyle hızlıca üretim yapılabilir (ortalama 0.03 saniye)
  • u128 türünün sınırları nedeniyle 1024 bite kadar genişletmek zordur
• 1024 bit için BigInt uygulaması
  • Birkaç deneme ile kademeli olarak geliştirildi
    • Deneme 1: Sayının basamaklarını diziye kaydetme
    • Deneme 2: Sayıyı ikili biçimde saklama
    • Deneme 3: Sayıyı bayt bazlı parçalar halinde saklama
    • Deneme 4: Sayıyı u64 parça bazında saklama
    • Deneme 5: Dört işlem algoritmalarını optimize etme
  • Miller-Rabin testinin ve genel mantığın optimizasyonu
  • Paralel işleme için çoklu iş parçacığı kullanımı
• Nihai sonuç
  • Yaklaşık 40 ms içinde 1024 bitlik asal sayı üretimi mümkün oldu (8 ms ~ 800 ms)
  • Paralel işleme ile ortalama süre 0.04 saniyeye indi

GN⁺ Görüşü

• Deneme ve hatalardan öğrenerek kademeli iyileştirme sürecinin dikkat çekici olması
  • Basit bir uygulamayla başlayıp her adımda yeni fikirler uygulandı ve optimizasyonlar yapıldı
  • Başarısızlık yaşansa bile vazgeçmeden sorunun nedenini bulup çözüm arandı
• Yazarın matematiksel altyapısı sınırlı olmasına rağmen ilgili materyalleri bularak anlamaya çalışması öne çıkıyordu
  • Fermat’ın Küçük Teoremi, Miller-Rabin testi gibi gerekli matematiksel kavramlar öğrenildi
  • Zor içerikler bile uygulanabilir hale kadar anlaşılıp uygulanabilir kılındı
• Sabit uzunluklu tam sayı türlerinin limitini aşmak için doğrudan BigInt uygulanması dikkat çekiciydi
  • Sadece mevcut kütüphaneleri kullanmak yerine iç işleyişin mantığını anlayıp optimizasyon yapmak
  • Farklı fikirler denerek kademeli olarak ilerleme kaydedildi
• Çoklu iş parçacığı ile paralel işlemenin performansı büyük ölçüde artırmış olması ilgi çekiciydi
  • Bağımsız hesaplamalar yapan sorunun doğasını iyi yakalayıp kullandı
  • Sadece hızı artırmak yerine probleme göre etkili bir yaklaşım seçildi
• Proje, kriptografik olarak güvenli bir seviyeye çıkmasa da öğrenme ve keşif amacıyla büyük değer taşıyor
  • Pratik kullanımdan çok yazarın merakı ve meydan okuma ruhu öne çıkıyor
  • Bu süreçte kazanılan içgörüler ve deneyim, yazarın ileride büyümesine önemli katkı sağlayacak gibi görünüyor

[GN⁺]

Hacker News Yorumları

• İlgili olarak, bazı kripto para birimleri, iş kanıtı fonksiyonunun bir parçası olarak büyük asal sayılar bulmaya dair şeyler kullanır. Yaklaşık 8 yıl önce, çok hızlı bir asallık testi uygulamasıyla hayli para kazanmak mümkün olmuştu. Yazar bir süre Riecoin için madencilik yazılımının yazar ve yöneticisi oldu.

• Bu yazıda, hızlı asallık testleri için en iyi optimizasyon olan Montgomery çarpımı atlanmış. Bu da pratik ve hızlı bir modüler üs alma uygulamasının temelini oluşturuyor.

• Niall Emmart tarafından yayımlanan CGBN, gerçekten inanılmaz hızlı bir GPU bigint kütüphanesi. Hâlâ bildiğim en hızlı batch modexp uygulaması.

• Python, pow(x, y, m) → x^y % m hesaplayan oldukça iyi bir modüler üs (modexp) işlevini gömülü olarak sunuyor. Bu sayede Fermat veya Miller-Rabin asallık testini kolayca uygulayabilirsiniz.

• Başta olasılıksal asallık testi fikri tuhaftı; devasa sayılarla çalışabilen deterministik bir algoritma aradım ama APR-CL ve ECPP matematiksel olarak o kadar karmaşıktı ki anlamak zordu. RSA dâhil neredeyse her yerde olasılıksal algoritmalar kullanıldığını fark ettim.

• Belirli bir en üst sayı aralığı için Miller-Rabin'i deterministik yapmak açık bir durumdur. Verilen aralıkta tüm bileşik sayıları eleyen kanıtlı tabanları seçmek yeterli.

• Tek satır inline assembly ile büyük sayılar çarpımını epey basitleştirmek mümkün. C diline genişletilmiş çarpma fikrinin eklenmesini çok isterdim. Donanım desteği her yerde var.

• Fermat testi yeterliydi çünkü sayı gerçekten asal değilse algoritma çalışmıyordu. Ancak asal olmayan P/Q değerlerinin kriptolama/çözme mesajını başarılı şekilde yapabilecek olduğunu ispatlayıp ispatlayamayacağımı bilmiyorum.

• Projenin ne kadar sürdüğünü merak ediyorum. Yazar Karatsuba, Toom-Cook, kompleks FFT, NTT ve Schönhage–Strassen'i uygulamış. Silverman'ın "A Friendly Introduction to Number Theory" adlı kitabını önerdi.

• Büyük sayı çarpımı için kodu baştan yazarken, matematiksel bir makaledeki yüksek seviyeli anlatımı doğrudan hesaplamaya çevirmek ne kadar zor olduğuna katılıyorum. Rakam tabanı (radix) ile ilgili bölümde de biraz sorun var.

• Sayıyı yeniden üretmek yerine en sonda 2 ekleme optimizasyonu güvenliği biraz zedeliyor. Asallar eşit dağılmadığı için, bir büyük asal aralığından hemen sonraki asallara doğru önyargı olur.

• Fermat küçük teoremine dair küçük bir hata var: a^(p-1) ifadesinin pye bölünebildiği söylenmiş, oysa a^(p-1) - 1'in pye bölünebilmesi gerekiyor. Modüler aritmetik terimleriyle anlatım doğru.