BILANGAN 155 DIGIT DIPECAH DI KARTU GRAFIS

Memecah bilangan besar menjadi faktor-faktor primanya itu sulit, dan kesulitan itu penting bagi kriptografi — itulah sebabnya makalah ini berhati-hati menyebutkan apa yang tidak terancam oleh hasilnya. Bilangan publik “tantangan RSA” berfungsi sebagai tolok ukur untuk metode faktorisasi. RSA-155 adalah salah satunya: 155 digit, atau 512 bit.

Dua saringan, masing-masing satu rekor

Dua keluarga algoritme mendominasi. Saringan medan bilangan (number field sieve) adalah juara untuk bilangan yang sangat besar: algoritme ini sudah memecah RSA-155 pada 1999, dan menurut makalah ini, rekor umumnya kini berada pada bilangan 270 digit, RSA-896, pada 2026. Saringan kuadratik (quadratic sieve) yang lebih tua secara asimtotik lebih lambat dan, menurut kata-kata para penulis sendiri, “alat yang salah” untuk rekor umum. Namun ia punya daftar rekornya sendiri: bilangan terbesar yang dipecah dengannya adalah RSA-150, pada Juni 2025, dengan 11.664 jam-inti CPU.

Saringan kuadratik memburu banyak bilangan kecil yang dapat difaktorkan sepenuhnya atas sekumpulan bilangan prima kecil, lalu memakai aljabar linear untuk menggabungkannya menjadi dua kuadrat x² dan y² yang sama dalam modulo N. Faktor persekutuan terbesar kemudian mengungkap sebuah faktor. Di komputer, ini adalah mimpi buruk bagi prosesor grafis (GPU): akses memori tersebar jauh melampaui cache mana pun, pengujiannya penuh percabangan, dan aljabar akhirnya bekerja dalam aritmetika biner yang tidak didukung pustaka vendor mana pun. Upaya GPU sebelumnya hanya mempercepat langkah-langkah tertentu.

Semuanya di kartu grafis

Fabian Januszewski dan Christoph Heinrichs, dari institut matematika Universitas Paderborn di Jerman, membangun CUDA-MPQS, saringan kuadratik sumber terbuka yang setiap tahapnya — menyiapkan polinomial, menyaring, memeriksa kandidat, mencocokkan hasil parsial, menyusun matriks, menyelesaikannya, dan mengambil akar kuadrat akhir — berjalan di GPU. Prosesor biasa hanya mengatur, menyiapkan, dan menangani masukan serta keluaran; para penulis mencantumkan secara eksplisit beberapa langkah yang masih tersisa di sisi host. Pada uji 100 digit, GPU sibuk 99,9% dari waktu penyaringan, tanpa jeda untuk menunggu prosesor.

Peningkatan skala memunculkan sebuah bug yang halus. Pada ukuran RSA-155, penghitung 8 bit yang dipakai selama penyaringan meluap tepat pada kandidat yang paling berharga, diam-diam membuang 98 hingga 99,5% di antaranya. Tim menggantinya dengan penghitung jenuh (saturating counter) yang terbukti, menurut mereka, memberikan hasil identik.

RSA-155 dalam sekitar satu hari

Pada 14 Juli 2026, alur kerja ini memecah RSA-155 menjadi dua bilangan prima yang masing-masing 78 digit, yang diperiksa di GPU maupun di host:

Penyaringan: 64 GPU NVIDIA H100 di 16 node, 10,8 jam, mengumpulkan sekitar 17,3 juta relasi.
Aljabar linear: satu H100 selama 10,9 jam, pada matriks dengan 16,7 juta baris dan 684 juta entri tak nol.
Total: 700,6 GPU-jam dan 242 kilowatt-jam, kira-kira 24 jam dari awal hingga faktor ditemukan. Penyaringan menyumbang 98,4% biaya.

Sejauh pengetahuan para penulis, ini adalah bilangan bulat terbesar yang pernah difaktorkan dengan saringan kuadratik, lima digit melampaui rekor sebelumnya — dan dicapai dengan varian metode yang paling sederhana, yang hanya menyimpan satu “bilangan prima besar” per relasi, sementara rekor-rekor terbaru memakai tiga.

Lebih cepat daripada prosesor terbaik

Pada bilangan 100 digit, satu H100 selesai dalam 29,2 detik, dan RTX 5070 Ti kelas konsumen dalam 51 detik. Dalam perbandingan terkendali pada bilangan yang sama, dengan konsumsi energi diukur di kedua sisi, satu H100 3,6 hingga 4,2 kali lebih cepat daripada saringan kuadratik CPU tercepat yang berjalan di 96 inti prosesor AMD EPYC, dan sekitar sembilan hingga sepuluh kali lebih cepat daripada paket standar lain. Mereka juga memfaktorkan ulang RSA-150 dalam 302,9 GPU-jam, dibandingkan 11.664 jam-inti pada rekor sebelumnya — rasio yang, tegas para penulis, bukanlah percepatan yang setara dan sebanding.

Tak ada ancaman bagi enkripsi

Para penulis berterus terang: RSA-155 sudah pernah difaktorkan, ini bukan rekor faktorisasi umum, dan “tidak ada di sini yang mempersempit margin keamanan”. Kodenya juga sengaja dibatasi pada sekitar 155 digit. Minat mereka ada di tempat lain: menunjukkan bahwa algoritme yang tidak teratur dan penuh percabangan dapat sepenuhnya berjalan di GPU. Mereka menunjuk penyaring kisi (lattice siever) berbasis GPU, inti dari saringan medan bilangan, sebagai sasaran alami berikutnya — pekerjaan yang, catat mereka, sudah mulai dilakukan pihak lain, dengan memfaktorkan RSA-260 dan RSA-896 memakai porting GPU dari sebuah paket yang sudah ada, yang terakhir dibuat dengan Claude.

Konflik kepentingan. Para penulis menyatakan bahwa alat AI generatif dan alat pemrograman agentik digunakan: model Claude dari Anthropic (melalui Claude Code) bersama model GPT dari OpenAI dan Gemini dari Google untuk pengembangan perangkat lunak, serta model Claude untuk persiapan data dan naskah. Mereka menyatakan bahwa semua keluaran AI telah ditinjau dan diverifikasi secara manual. Claude juga menulis artikel ini.