Algoritma Berlekamp–Rabin

Dalam teori bilangan, algoritma Berlekamp–Rabin adalah metode probabilistik pencarian akar dari polinomial pada medan . Metode ini ditemukan oleh Elwyn Berlekamp pada tahun 1970 sebagai tambahan algoritma untuk faktorisasi polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh Rabin untuk medan berhingga sebarang pada tahun 1979. Sebelum Berlekamp, metode ini juga ditemukan secara terpisah oleh peneliti lain.

Sejarah 
Metode ini diusulkan oleh Elwyn Berlekamp dalam karyanya tahun 1970 tentang faktorisasi polinomial pada medan berhingga. Karya aslinya tidak memiliki bukti kebenaran formal dan kemudian disempurnakan dan dimodifikasi untuk medan berhingga sebarang oleh Michael Rabin. Pada tahun 1986, René Peralta mengusulkan algoritma serupa untuk mencari akar kuadrat . Perumuman metode Peralita untuk persamaan kubik dibuat pada tahun 2000.

Pernyataan masalah
Misalkan  adalah bilangan prima ganjil, dan misalkan pula polinomial  atas medan  dari modulo sisa . Tujuan pernyataan masalah ini adalah bahwa algoritma Berlekamp harus menemukan semua  di  sehingga  di .

Algoritma

Pengacakan 
Misalkan . Menemukan semua akar polinomial ini sama saja dengan mencari faktorisasinya menjadi faktor linear. Untuk menemukan faktorisasi tersebut, cukup membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Lebih lanjut, misalkan polinomial , untuk  setiap anggota . Jika polinomial tersebut dinyatakan sebagai hasilkali , maka dalam bentuk polinomial awal, mengartikan bahwa . Fungsi  yang merupakan menyediakan faktorisasi dibutuhkan dari .

Klasifikasi elemen  
Menurut kriteria Euler, untuk setiap monomial , berlaku tepat salah satu dari sifat-sifat berikut:

 Monomial sama dengan  jika ,
 Pembagian monomial  jika  adalah residu kuadrat modulo ,
 Pembagian monomial  jika  adalah non-residul kuadrat modulo .

Jadi, jika  tidak habis dibagi , yang dapat diperiksa secara terpisah, maka  sama dengan hasilkali dari faktor persekutuan terbesar  dan .

Metode Berlekamp 
Sifat-sifat di atas mengarah pada algoritma berikut:

 Hitung secara eksplisit koefisien ,
 Hitung sisa  modulo  dengan mengkuadratkan polinomial dan mengambil sisa modulo ,
 Menggunakan eksponensiasi yang dikuadratkan dan polinomial yang dihitung pada langkah sebelumnya, hitung sisa  modulo ,
 Jika , maka  yang disebutkan diatas memberikan faktorisasi non-trivial dari ,
 Jika tidak, maka semua akar  adalah residu atau non-residu secara bersamaan dan harus memilih  yang lain.

Jika  habis dibagi oleh setiap polinomial primitif  atas  maka saat menghitung  dengan  dan  akan diperoleh faktorisasi non-trivial dari , sehingga algoritma memungkinkan untuk menemukan semua akar polinomial sebarang atas .

Akar kuadrat modular 
Misalkan persamaan  mempunyai anggota  dan  sebagai akarnya. Solusi persamaan ini ekuivalen dengan faktorisasi polinomial  atas . Dalam masalah kasus istimewa ini, cukup hitung  saja. Untuk polinomial tersebut, ada tepat satu dari sifat-sifat yang berlaku sebagai berikut:

 FPB sama dengan , yang berarti bahwa  dan  merupakan non-residu kuadratik,
 FPB sama dengan , yang berarti kedua bilangan tersebut merupakan residu kuadratik,
 FPB sama dengan , yang berarti tepat salah satu dari bilangan tersebut merupakan residu kuadrat.

Pada kasus ketiga, FPB sama dengan  atau . Hal ini memungkinkan untuk menulis solusi sebagai .

Contoh 
Asumsi bahwa persamaan  dapat diselesaikan. Caranya adalah dengan memfaktorkan . Nilai  dapat dibagi menjadi beberapa kasus dengan memisalkannya sebagai berikut:

 Misalkan , maka . Jadi, . Karena bilangan  merupakan non-residu kuadrat, maka perlu dicari nilai  lain.
 Misalkan , maka . Jadi, . Karena , maka  dan .

Hasil pemeriksaan yang dilakukan secara manual memperlihatkan bahwa  dan .

Bukti kebenaran 
Algoritma menemukan faktorisasi  dalam semua kasus, kecuali ketika semua bilangan  adalah residu kuadrat atau non-residu secara bersamaan. Menurut teori siklotomi, peluang kejadiannya untuk kasus ketika  juga merupakan semua residu atau non-residu secara bersamaan (yaitu, ketika  tidak berhasil) diestimasi sebagai , untuk  adalah jumlah nilai yang berbeda dalam . Dengan cara ini, bahkan untuk kasus galat  dan , maka estimasi peluang galatnya adalah , dan untuk kasus akar kuadrat modular, probabilitas galat setidaknya bernilai .

Kompleksitas 
Misalkan suatu polinomial merupakan polinomial berderajat , maka kompleksitas algoritma dapat diturunkan sebagai berikut:

 Karena menurut teorema binomial mengatakan bahwa , maka dapat dilakukan transisi dari  ke  dalam waktu .
 Perkalian polinomial dan mengambil sisa dari satu polinomial yang modulo dengan yang lain dapat dilakukan di . Jadi, perhitungan  dilakukan di .
 Eksponensial biner bekerja di .
 Mengambil  dari dua polinomial melalui algoritma Euklides yang bekerja di .

Jadi, seluruh prosedur dapat dilakukan di . Dengan menggunakan transformasi Fourier cepat dan algoritma setengah-FPB, maka kompleksitas algoritmanya dapat ditingkatkan menjadi . Untuk kasus akar kuadrat modular, derajatnya adalah , sehingga seluruh kompleksitas algoritma dalam kasus tersebut dibatasi dengan  per iterasi.

Referensi 

Algoritma
Aljabar
Algoritma teori bilangan
Polinomial