Apa Itu Algoritma Fermat?

Pengertian Algoritma Fermat

Algoritma Fermat adalah sebuah metode pencarian faktor prima dari sebuah bilangan bulat besar dengan menggunakan prinsip metode Fermat. Metode ini didasarkan pada identitas aljabar:

a b = (a + b)(a b)

Jika sebuah bilangan n dapat ditulis sebagai selisih dua kuadrat, maka n dapat difaktorkan menjadi (a + b) dan (a b). Algoritma Fermat berusaha menemukan representasi tersebut dengan cara mencari nilai a dan b yang memenuhi persamaan di atas.

Sejarah Singkat

Metode ini pertama kali diperkenalkan oleh Pierre de Fermat pada abad ke-17 dalam konteks teori bilangan. Pada masa itu, Fermat menulis tentang cara mengekspresikan bilangan ganjil sebagai selisih dua kuadrat, namun tidak mengembangkan algoritma yang dapat dijalankan secara komputasional. Hanya pada akhir abad ke-20, ketika komputer mulai banyak dipakai, algoritma ini diadaptasi menjadi prosedur praktis untuk faktorisasi bilangan.

Prinsip Kerja Algoritma

1. Inisialisasi: Mulai dengan nilai a = n, yaitu pembulatan ke atas akar kuadrat n.
2. Hitung b: Hitung b = a n.
3. Periksa apakah b adalah kuadrat sempurna:
   • Jika ya, maka b = b dan n = (a + b)(a b). Kedua faktor tersebut dapat diperas lebih lanjut bila belum prima.
   • Jika tidak, tambahkan 1 pada a (a = a + 1) dan ulangi langkah 2.
4. Berhenti: Jika a menjadi lebih besar dari n tanpa menemukan b kuadrat sempurna, maka n adalah prima (untuk angka ganjil) atau mengandung faktor 2.

Algoritma ini paling efisien bila n memiliki faktor yang dekat satu sama lain (misalnya n = pq dengan p dan q berdekatan). Jika faktor-faktornya jauh berjauhan, algoritma menjadi lambat karena harus mencoba banyak nilai a.

Aplikasi Praktis

Walaupun bukan algoritma faktorisasi tercepat dibandingkan metode modern seperti Quadratic Sieve atau General Number Field Sieve, Algoritma Fermat tetap memiliki tempat penting dalam:

• Pengajaran konsep faktorisasi dan identitas aljabar.
• Kriptografi klasik, khususnya dalam contohcontoh pendidikan RSA dengan angka kecil.
• Analisis kompleksitas algoritma; memberikan contoh kasus worstcase yang bergantung pada jarak antara faktor.

Selain itu, variasi algoritma Fermat, seperti Modified Fermat (menambahkan langkah pemotongan faktor 2) atau Incremental Fermat, sering dipakai sebagai komponen dalam program faktorisasi hibrida.

Contoh Implementasi dalam Python

def is_square(num):    root = int(num**0.5)    return root*root == numdef fermat_factor(n):    if n % 2 == 0:        return 2, n//2    a = int(n**0.5) + 1    b2 = a*a - n    while not is_square(b2):        a += 1        b2 = a*a - n    b = int(b2**0.5)    return a-b, a+b# contoh penggunaann = 5959   # 5959 = 59 * 101f1, f2 = fermat_factor(n)print("Faktor:", f1, f2)            

Penjelasan singkat:

• Fungsi is_square memeriksa apakah suatu bilangan merupakan kuadrat sempurna.
• Jika n genap, langsung mengembalikan 2 dan n/2.
• Inisialisasi a pada nilai n dan iterasi sampai b2 menjadi kuadrat sempurna.
• Setelah menemukan b, faktor n adalah (a-b) dan (a+b).

Kelebihan dan Kekurangan

Kesimpulan

Algoritma Fermat merupakan contoh klasik dari penerapan identitas aljabar dalam faktorisasi bilangan. Meskipun tidak secepat metode faktorisasi canggih yang ada saat ini, algoritma ini tetap bernilai edukatif dan historis. Memahami cara kerja Fermat membantu mengapresiasi evolusi teknik faktorisasi serta memberikan dasar yang kuat bagi mereka yang belajar kriptografi dan teori bilangan.