Kalkulator Faktorisasi Fermat

Tentang kalkulator ini

Metode faktorisasi Fermat memanfaatkan fakta bahwa setiap bilangan bulat ganjil N dapat ditulis sebagai selisih dua kuadrat, N = a² − b² = (a−b)(a+b). Algoritma ini dimulai dari a = ⌈√N⌉ dan menaikkan a sebesar 1 pada setiap langkah, memeriksa apakah a² − N itu sendiri merupakan kuadrat sempurna (b²); begitu terpenuhi, N langsung terfaktor menjadi (a−b)(a+b). Kalkulator ini menjalankan perulangan tersebut dan menampilkan setiap langkah yang ditempuh untuk menemukan faktornya.

Metode ini konvergen dalam sangat sedikit langkah ketika kedua faktor N berdekatan — kelemahan utamanya sekaligus merupakan kegunaan dunia nyata yang terpenting: mahasiswa kriptografi dan peneliti keamanan memakai faktorisasi Fermat untuk menunjukkan mengapa modulus RSA harus dibangun dari bilangan prima yang berjauhan, karena bilangan prima yang dipilih terlalu berdekatan membuat modulusnya sangat mudah dipecahkan. Metode ini juga merupakan latihan standar dalam perkuliahan teori bilangan untuk menggambarkan penalaran selisih kuadrat.