integer factorization

Menyambung soal pemrograman kemarin dulu, sekarang saya sedang mencari algoritma yang bagus untuk memfaktorkan sebuah bilangan (integer factorization). Diketahui sebuah bilangan x, berikan bilangan prima yang menjadi faktor dari bilangan tersebut. (Sebetulnya saya mencari bilangan prima terbesar.)

Ada beberapa algoritma yang sudah saya lihat, tetapi mereka hanya bisa digunakan untuk bilangan yang kecil. Algoritma tersebut tidak jalan untuk bilangan yang besar, misalnya:

x = 230023525003339439329862001182693967063150646

Berapa faktornya? Jawabannya (dengan menggunakan PARI atau Wolfram alpha) adalah:

{2, 331, 9351779, 7311032480779, 5082077886580529086513}

Masih mencari algoritma yang bisa menemukan itu secara efisien. Ada yang tahu? Saya buat kode dengan algoritma yang tidak efisien, jalan untuk angka yang kecil. Untuk angka yang besar seperti di atas, mungkin 10 tahun baru selesai 🙂

(Baca paper Arjen Lenstra dulu ah.)

Iklan

10 pemikiran pada “integer factorization

  1. IIRC PARI menggunakan Quadratic Sieve. Untuk implementasi C yang public domain, tinggal lihat msieve.sf.net. Yang dari Lenstra itu rasanya elliptic curve factorization (tapi saya asing sekali dengan yang ini).

  2. Wah ariya … Anda bikin “gara-gara”!

    Setelah mengunjungi situs msieve itu, saya langsung download programnya. Di dalamnya ada “Readme” yang berisi latar belakang dan bahan bacaan. Gila! Bahan bacaannya menarik semua. Jadi pengen cari buku / paper / thesis yang ada di daftar referensi di sana. Pengen baca! Ini distraction!

    Saya hanya butuh librarynya dan cara menggunakannya, tapi kok malah tertarik dengan ilmu di belakanganya. Ini memang terkait dengan bidang security (khususnya bagian attack).

    Haduh … more things to read and study!

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google

You are commenting using your Google account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s