Algoritma Berlekamp–Rabin

Dalam teori bilangan, **algoritma Berlekamp–Rabin** adalah metode probabilistik pencarian akar dari polinomial pada medan \mathbb Z_p. 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 \mathbb Z_p. Perumuman metode Peralita untuk persamaan kubik dibuat pada tahun 2000.

## Pernyataan masalah
Misalkan p adalah bilangan prima ganjil, dan misalkan pula polinomial f(x) = a_0 + a_1 x + \cdots + a_n x^n atas medan \mathbb Z_p dari modulo sisa p. Tujuan pernyataan masalah ini adalah bahwa algoritma Berlekamp harus menemukan semua \lambda di \mathbb Z_p sehingga f(\lambda)= 0 di \mathbb Z_p.

## Algoritma

### Pengacakan
Misalkan f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n). 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 f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z), untuk z setiap anggota \mathbb Z_p. Jika polinomial tersebut dinyatakan sebagai hasilkali f_z(x)=p_0(x)p_1(x), maka dalam bentuk polinomial awal, mengartikan bahwa f(x) =p_0(x+z)p_1(x+z). Fungsi  yang merupakan menyediakan faktorisasi dibutuhkan dari f(x).

### Klasifikasi elemen <math>\mathbb Z_p</math>
Menurut kriteria Euler, untuk setiap monomial (x-\lambda), berlaku tepat salah satu dari sifat-sifat berikut:

# Monomial sama dengan x jika \lambda = 0,
# Pembagian monomial g_0(x)=(x^{(p-1)/2}-1) jika \lambda adalah residu kuadrat modulo p,
# Pembagian monomial g_1(x)=(x^{(p-1)/2}+1) jika \lambda adalah non-residul kuadrat modulo p.

Jadi, jika f_z(x) tidak habis dibagi x, yang dapat diperiksa secara terpisah, maka f_z(x) sama dengan hasilkali dari faktor persekutuan terbesar \operatorname{FPB}(f_z(x);g_0(x)) dan \operatorname{FPB}(f_z(x);g_1(x)).

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

# Hitung secara eksplisit koefisien f_z(x) = f(x-z),
# Hitung sisa x,x^2, x^{2^2},x^{2^3}, x^{2^4}, \ldots, x^{2^{\lfloor \log_2 p \rfloor}} modulo f_z(x) dengan mengkuadratkan polinomial dan mengambil sisa modulo f_z(x),
# Menggunakan eksponensiasi yang dikuadratkan dan polinomial yang dihitung pada langkah sebelumnya, hitung sisa x^{(p-1)/2} modulo f_z(x),
# Jika x^{(p-1)/2} \not \equiv \pm 1 \pmod{f_z(x)}, maka \operatorname{FPB} yang disebutkan diatas memberikan faktorisasi non-trivial dari f_z(x),
# Jika tidak, maka semua akar f_z(x) adalah residu atau non-residu secara bersamaan dan harus memilih z yang lain.

Jika f(x) habis dibagi oleh setiap polinomial primitif g(x) atas \mathbb Z_p maka saat menghitung \operatorname{FPB} dengan g_0(x) dan g_1(x) akan diperoleh faktorisasi non-trivial dari f_z(x)/g_z(x), sehingga algoritma memungkinkan untuk menemukan semua akar polinomial sebarang atas \mathbb Z_p.

### Akar kuadrat modular
Misalkan persamaan x^2 \equiv a \pmod{p} mempunyai anggota \beta dan -\beta sebagai akarnya. Solusi persamaan ini ekuivalen dengan faktorisasi polinomial f(x) = x^2-a=(x-\beta)(x+\beta) atas \mathbb Z_p. Dalam masalah kasus istimewa ini, cukup hitung \operatorname{FPB}(f_z(x); g_0(x)) saja. Untuk polinomial tersebut, ada tepat satu dari sifat-sifat yang berlaku sebagai berikut:

# FPB sama dengan 1, yang berarti bahwa z+\beta dan z-\beta merupakan non-residu kuadratik,
# FPB sama dengan f_z(x), yang berarti kedua bilangan tersebut merupakan residu kuadratik,
# FPB sama dengan (x-t), yang berarti tepat salah satu dari bilangan tersebut merupakan residu kuadrat.

Pada kasus ketiga, FPB sama dengan (x-z-\beta) atau (x-z+\beta). Hal ini memungkinkan untuk menulis solusi sebagai \beta = (t - z) \pmod{p}.

### Contoh
Asumsi bahwa persamaan x^2 \equiv 5\pmod{11} dapat diselesaikan. Caranya adalah dengan memfaktorkan f(x)=x^2-5=(x-\beta)(x+\beta). Nilai z dapat dibagi menjadi beberapa kasus dengan memisalkannya sebagai berikut:

# Misalkan z=3, maka f_z(x) = (x-3)^2 - 5 = x^2 - 6x + 4. Jadi, \operatorname{FPB}(x^2 - 6x + 4 ; x^5 - 1) = 1. Karena bilangan 3 \pm \beta merupakan non-residu kuadrat, maka perlu dicari nilai z lain.
# Misalkan z=2, maka f_z(x) = (x-2)^2 - 5 = x^2 - 4x - 1. Jadi, \operatorname{FPB}( x^2 - 4x - 1 ; x^5 - 1)\equiv x - 9 \pmod{11}. Karena x - 9 = x - 2 - \beta, maka \beta \equiv 7 \pmod{11} dan -\beta \equiv -7 \equiv 4 \pmod{11}.

Hasil pemeriksaan yang dilakukan secara manual memperlihatkan bahwa 7^2 \equiv 49 \equiv 5\pmod{11} dan 4^2\equiv 16 \equiv 5\pmod{11}.

## Bukti kebenaran
Algoritma menemukan faktorisasi f_z(x) dalam semua kasus, kecuali ketika semua bilangan z+\lambda_1, z+\lambda_2, \ldots, z+\lambda_n adalah residu kuadrat atau non-residu secara bersamaan. Menurut teori siklotomi, peluang kejadiannya untuk kasus ketika \lambda_1, \ldots, \lambda_n juga merupakan semua residu atau non-residu secara bersamaan (yaitu, ketika z=0 tidak berhasil) diestimasi sebagai 2^{-k}, untuk k adalah jumlah nilai yang berbeda dalam \lambda_1, \ldots, \lambda_n. Dengan cara ini, bahkan untuk kasus galat k=1 dan f(x)=(x-\lambda)^n, maka estimasi peluang galatnya adalah 1/2, dan untuk kasus akar kuadrat modular, probabilitas galat setidaknya bernilai 1/4.

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

# Karena menurut teorema binomial mengatakan bahwa (x-z)^k = \sum\limits_{i=0}^k \binom{k}{i} (-z)^{k-i}x^i, maka dapat dilakukan transisi dari f(x) ke f(x-z) dalam waktu O(n^2).
# Perkalian polinomial dan mengambil sisa dari satu polinomial yang modulo dengan yang lain dapat dilakukan di O(n^2). Jadi, perhitungan x^{2^k} \bmod f_z(x) dilakukan di O(n^2 \log p).
# Eksponensial biner bekerja di O(n^2 \log p).
# Mengambil \operatorname{FPB} dari dua polinomial melalui algoritma Euklides yang bekerja di O(n^2).

Jadi, seluruh prosedur dapat dilakukan di O(n^2 \log p). Dengan menggunakan transformasi Fourier cepat dan algoritma setengah-FPB, maka kompleksitas algoritmanya dapat ditingkatkan menjadi O(n \log n \log pn). Untuk kasus akar kuadrat modular, derajatnya adalah n = 2, sehingga seluruh kompleksitas algoritma dalam kasus tersebut dibatasi dengan O(\log p) per iterasi.

## Referensi