Bernstein çarpanlara ayırma algoritması Python ile modellendi
Öne çıkanlar
- Bernstein algoritması, 2020 yılında 795 bitlik RSA-240 anahtarının çarpanlara ayrılma süresini yüzde 25 düşürdü.
- Yöntem, klasik bölme işlemi yerine 2-adik bölme ve çarpım ağaçlarını kullanarak küçük çarpanları toplu halde buluyor.
- Geliştirilen Python uygulaması, CADO-NFS klonunda ayrık logaritma ve çarpanlara ayırma hesapları için modellendi.
LeetArxiv, Daniel J. Bernstein tarafından 2002 yılında geliştirilen ve RSA-240 anahtarının kırılmasında kritik rol oynayan toplu çarpanlara ayırma algoritmasını Python ile uyguladı. Sayı cismi kalburu (NFS) serisinin sekizinci bölümü olarak yayımlanan teknik rehber, verilen bir tamsayı listesindeki küçük asal çarpanların tespit edilmesini sağlayan süreci pratik kodlarla ortaya koydu. Çözüm, açık kaynaklı CADO-NFS yazılımının klonuna entegre edilecek biçimde uyarlandı.
Bernstein algoritması, literatürde toplu pürüzsüzlük tespiti (batch smoothness detection) olarak da adlandırılıyor. Yaklaşım, 2020 yılında 795 bit uzunluğundaki RSA-240 anahtarının çarpanlara ayrılması sürecinde harcanan hesaplama süresini yüzde 25 oranında düşürdü. Süreç, hedef tamsayıların çarpımı ile asal sayılardan oluşan bir çarpım ağacının eşleştirilmesi mantığına dayanıyor.
Yayımlanan uygulama, çarpım ağaçlarının oluşturulması, 2-adik bölme ve 2-adik ters alma adımlarını kapsayan algoritmik temelleri içeriyor. Büyük sayılarda standart bölme işlemlerinin getirdiği yüksek maliyet, ikili tabandaki bit kaydırma ve 2-adik matematiksel optimizasyonlar kullanılarak hafifletiliyor. Çalışmaya ait kaynak kodlar geliştiriciler için Google Colab üzerinden paylaşıldı.
Bu özet yapay zekâ ile hazırlanmıştır; ayrıntılar ve doğrulama için orijinal kaynağa başvurun.