Algoritma Berlekamp–Rabin

Dalam teori bilangan, algoritma Berlekamp–Rabin adalah metode probabilistik pencarian akar dari polinomial pada medan ${\displaystyle \mathbb {Z} _{p}}$. Metode ini ditemukan oleh Elwyn Berlekamp pada tahun 1970^[1] sebagai tambahan algoritma untuk faktorisasi polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh Rabin untuk medan berhingga sebarang pada tahun 1979.^[2] Sebelum Berlekamp, metode ini juga ditemukan secara terpisah oleh peneliti lain.^[3]

Metode ini diusulkan oleh Elwyn Berlekamp dalam karyanya tahun 1970^[1] tentang faktorisasi polinomial pada medan berhingga. Karya aslinya tidak memiliki bukti kebenaran formal^[2] dan kemudian disempurnakan dan dimodifikasi untuk medan berhingga sebarang oleh Michael Rabin.^[2] Pada tahun 1986, René Peralta mengusulkan algoritma serupa^[4] untuk mencari akar kuadrat ${\displaystyle \mathbb {Z} _{p}}$.^[5] Perumuman metode Peralita untuk persamaan kubik dibuat pada tahun 2000.^[6]

Misalkan ${\displaystyle p}$ adalah bilangan prima ganjil, dan misalkan pula polinomial ${\textstyle f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}}$ atas medan ${\displaystyle \mathbb {Z} _{p}}$ dari modulo sisa ${\displaystyle p}$. Tujuan pernyataan masalah ini adalah bahwa algoritma Berlekamp harus menemukan semua ${\displaystyle \lambda }$ di ${\displaystyle \mathbb {Z} _{p}}$ sehingga ${\textstyle f(\lambda )=0}$ di ${\displaystyle \mathbb {Z} _{p}}$.^[2][7]

Misalkan ${\textstyle 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 ${\textstyle f_{z}(x)=f(x-z)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\cdots (x-\lambda _{n}-z)}$, untuk ${\displaystyle z}$ setiap anggota ${\displaystyle \mathbb {Z} _{p}}$. Jika polinomial tersebut dinyatakan sebagai hasilkali ${\displaystyle f_{z}(x)=p_{0}(x)p_{1}(x)}$, maka dalam bentuk polinomial awal, mengartikan bahwa ${\displaystyle f(x)=p_{0}(x+z)p_{1}(x+z)}$. Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari ${\displaystyle f(x)}$.^[1][7]

Menurut kriteria Euler, untuk setiap monomial ${\displaystyle (x-\lambda )}$, berlaku tepat salah satu dari sifat-sifat berikut:^[1]

1. Monomial sama dengan ${\displaystyle x}$ jika ${\displaystyle \lambda =0}$,
2. Pembagian monomial ${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$ jika ${\displaystyle \lambda }$ adalah residu kuadrat modulo ${\displaystyle p}$,
3. Pembagian monomial ${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ jika ${\displaystyle \lambda }$ adalah non-residul kuadrat modulo ${\displaystyle p}$.

Jadi, jika ${\displaystyle f_{z}(x)}$ tidak habis dibagi ${\displaystyle x}$, yang dapat diperiksa secara terpisah, maka ${\displaystyle f_{z}(x)}$ sama dengan hasilkali dari faktor persekutuan terbesar ${\displaystyle \operatorname {FPB} (f_{z}(x);g_{0}(x))}$ dan ${\displaystyle \operatorname {FPB} (f_{z}(x);g_{1}(x))}$.^[7]

Sifat-sifat di atas mengarah pada algoritma berikut:^[1]

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

Jika ${\displaystyle f(x)}$ habis dibagi oleh setiap polinomial primitif ${\displaystyle g(x)}$ atas ${\displaystyle \mathbb {Z} _{p}}$ maka saat menghitung ${\displaystyle \operatorname {FPB} }$ dengan ${\displaystyle g_{0}(x)}$ dan ${\displaystyle g_{1}(x)}$ akan diperoleh faktorisasi non-trivial dari ${\displaystyle f_{z}(x)/g_{z}(x)}$, sehingga algoritma memungkinkan untuk menemukan semua akar polinomial sebarang atas ${\displaystyle \mathbb {Z} _{p}}$.

Misalkan persamaan ${\textstyle x^{2}\equiv a{\pmod {p}}}$ mempunyai anggota ${\displaystyle \beta }$ dan ${\displaystyle -\beta }$ sebagai akarnya. Solusi persamaan ini ekuivalen dengan faktorisasi polinomial ${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$ atas ${\displaystyle \mathbb {Z} _{p}}$. Dalam masalah kasus istimewa ini, cukup hitung ${\displaystyle \operatorname {FPB} (f_{z}(x);g_{0}(x))}$ saja. Untuk polinomial tersebut, ada tepat satu dari sifat-sifat yang berlaku sebagai berikut:

1. FPB sama dengan ${\displaystyle 1}$, yang berarti bahwa ${\displaystyle z+\beta }$ dan ${\displaystyle z-\beta }$ merupakan non-residu kuadratik,
2. FPB sama dengan ${\displaystyle f_{z}(x)}$, yang berarti kedua bilangan tersebut merupakan residu kuadratik,
3. FPB sama dengan ${\displaystyle (x-t)}$, yang berarti tepat salah satu dari bilangan tersebut merupakan residu kuadrat.

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

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

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

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

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

Misalkan suatu polinomial merupakan polinomial berderajat ${\displaystyle n}$, maka kompleksitas algoritma dapat diturunkan sebagai berikut:

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

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

Templat:Algoritma teori bilangan