Pengguna:Klasüo/bak pasir/Arsip 40

Dalam teori bilangan, algoritma pencarian akar Berlekamp atau juga disebut 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 untuk algoritma untuk faktorisasi polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh Rabin untuk medan berhingga arbiter pada tahun 1979. Metode ini juga ditemukan secara independen sebelum Berlekamp 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 arbiter oleh Michael Rabin. Pada tahun 1986, René Peralta mengusulkan algoritma serupa untuk mencari akar kuadrat $\mathbb {Z} _{p}$. Pada tahun 2000, metode Peralta digeneralisasikan untuk persamaan kubik.

Pernyataan masalah

Maka $p$ adalah sebagai bilangan prima ganjil. Pertimbangkan polinomial ${\textstyle f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}}$ pada medan $\mathbb {Z} _{p}$ dari modulo sisa $p$. Algoritma seharusnya ditemukan semua $\lambda$ dalam $\mathbb {Z} _{p}$ sedemikian rupa ${\textstyle f(\lambda )=0}$ dalam $\mathbb {Z} _{p}$.

Algoritma

Pengacakan

Maka ${\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\cdots (x-\lambda _{n})}$. Temukan semua akar polinomial ini sama dengan mencari faktorisasinya menjadi faktor linear. Untuk menemukan faktorisasi tersebut, cukup untuk membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Untuk hal ini, pertimbangkan polinomial ${\textstyle f_{z}(x)=f(x-z)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\cdots (x-\lambda _{n}-z)}$ dimana $z$ adalah beberapa elemen $\mathbb {Z} _{p}$. Apabila seseorang dapat menyatakan polinomial ini sebagai produk $f_{z}(x)=p_{0}(x)p_{1}(x)$ maka dalam hal polinomial awal itu berarti bahwa $f(x)=p_{0}(x+z)p_{1}(x+z)$ yang merupakan menyediakan faktorisasi dibutuhkan dari $f(x)$.

Klasifikasi elemen $\mathbb {Z} _{p}$

Karena kriteria Euler, untuk setiap monomial $(x-\lambda )$ tepat satu dari sifat berikut ini:

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

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

Metode Berlekamp

Sifat di atas mengarah ke algoritma berikut:

1. Hitung secara eksplisit koefisien $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 $f_{z}(x)$ dengan mengkuadratkan polinomial dan mengambil sisa modulo $f_{z}(x)$,
3. Menggunakan eksponensial dengan kuadrat 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 $\operatorname {FPB}$ yang disebutkan diatas memberikan faktorisasi non-trivial dari $f_{z}(x)$,
5. Jika tidak, semua akar $f_{z}(x)$ adalah residu atau non-residu secara bersamaan dan harus memilih $z$ yang lain.

Jika $f(x)$ habis dibagi oleh beberapa 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 arbiter atas $\mathbb {Z} _{p}$.

Akar kuadrat modular

Pertimbangkan persamaan ${\textstyle x^{2}\equiv a{\pmod {p}}}$ yang memiliki elemen $\beta$ dan $-\beta$ sebagai akarnya. Solusi persamaan ini ekuivalen dengan faktorisasi polinomial ${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$ atas $\mathbb {Z} _{p}$. Dalam masalah kasus khusus ini cukup untuk menghitung hanya $\operatorname {FPB} (f_{z}(x);g_{0}(x))$. Untuk polinomial ini tepat satu dari sifat-sifat sebagai beriku:

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

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

Contoh

Kita harus asumsikan untuk menyelesaikan persamaan ${\textstyle x^{2}\equiv 5{\pmod {11}}}$. Untuk ini kita harus memfaktorkan $f(x)=x^{2}-5=(x-\beta )(x+\beta )$. Pertimbangkan beberapa kemungkinan nilai $z$:

1. Jikalau $z=3$. Maka $f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4$ sebagai $\operatorname {FPB} (x^{2}-6x+4;x^{5}-1)=1$. Kedua bilangan $3\pm \beta$ adalah non-residu kuadrat, jadi kita perlu mengambil beberapa $z$ lainnya.

1. Jikalau $z=2$. Maka $f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1$ sebagai ${\textstyle \operatorname {FPB} (x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}}$. Dari berikut ini ${\textstyle x-9=x-2-\beta }$ juga $\beta \equiv 7{\pmod {11}}$ dan ${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$.

Pemeriksaan manual menunjukkan bahwa memang ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11}}}$ dan ${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11}}}$.

Bukti kebenaran

Algoritma menemukan faktorisasi $f_{z}(x)$ dalam semua kasus kecuali kasus ketika semua bilangan $z+\lambda _{1},z+\lambda _{2},\ldots ,z+\lambda _{n}$ adalah residu kuadrat atau non-residu secara bersamaan. Menurut teori siklotomi, probabilitas tersebut terjadi sama halnya untuk kasus ketika $\lambda _{1},\ldots ,\lambda _{n}$ juga merupakan semua residu atau non-residu secara bersamaan (yaitu, ketika $z=0$ tidak berhasil) diperkirakan sebagai $2^{-k}$ dimana $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}$, probabilitas galat diperkirakan sebagai $1/2$ dan untuk kasus akar kuadrat modular, probabilitas galat paling banyak pada diantara $1/4$.

Kompleksitas

Apabila polinomial memiliki derajat $n$. Maka bisa menurunkan kompleksitas algoritma sebagai berikut:

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

Jadi seluruh prosedur dapat dilakukan oleh $O(n^{2}\log p)$. Menggunakan transformasi Fourier cepat dan algoritma setengah-FPB, kompleksitas algoritmanya dapat ditingkatkan menjadi $O(n\log n\log pn)$. Untuk kasus akar kuadrat modular pada derajatnya adalah $n=2$, sehingga seluruh kompleksitas algoritma dalam kasus tersebut dibatasi oleh $O(\log p)$ per iterasi.

Referensi

Templat:Algoritma teori bilangan