Algoritma Berlekamp–Rabin

Dalam teori bilangan, algoritma Berlekamp–Rabin adalah metode probabilistik pencarian akar dari polinomial pada medan $ℤ_{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]

Sejarah

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 $ℤ_{p}$ .^[5] Perumuman metode Peralita untuk persamaan kubik dibuat pada tahun 2000.^[6]

Pernyataan masalah

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

Algoritma

Pengacakan

Misalkan $f (x) = (x - λ_{1}) (x - λ_{2}) \dots (x - λ_{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 - λ_{1} - z) (x - λ_{2} - z) \dots (x - λ_{n} - z)$ , untuk $z$ setiap anggota $ℤ_{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)$ .^[1]^[7]

Klasifikasi elemen Zₚ

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

Monomial sama dengan $x$ jika $λ = 0$ ,
Pembagian monomial $g_{0} (x) = (x^{(p - 1) / 2} - 1)$ jika $λ$ adalah residu kuadrat modulo $p$ ,
Pembagian monomial $g_{1} (x) = (x^{(p - 1) / 2} + 1)$ jika $λ$ 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 $FPB (f_{z} (x); g_{0} (x))$ dan $FPB (f_{z} (x); g_{1} (x))$ .^[7]

Metode Berlekamp

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

Hitung secara eksplisit koefisien $f_{z} (x) = f (x - z)$ ,
Hitung sisa $x, x^{2}, x^{2^{2}}, x^{2^{3}}, x^{2^{4}}, \dots, x^{2^{⌊ \log_{2} p ⌋}}$ 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} \equiv̸ \pm 1 (\mod f_{z} (x))$ , maka $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 $ℤ_{p}$ maka saat menghitung $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 $ℤ_{p}$ .

Akar kuadrat modular

Misalkan persamaan $x^{2} \equiv a (\mod p)$ mempunyai anggota $β$ dan $- β$ sebagai akarnya. Solusi persamaan ini ekuivalen dengan faktorisasi polinomial $f (x) = x^{2} - a = (x - β) (x + β)$ atas $ℤ_{p}$ . Dalam masalah kasus istimewa ini, cukup hitung $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 + β$ dan $z - β$ 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 - β)$ atau $(x - z + β)$ . Hal ini memungkinkan untuk menulis solusi sebagai $β = (t - z) (\mod p)$ .^[1]

Contoh

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

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

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

Bukti kebenaran

Algoritma menemukan faktorisasi $f_{z} (x)$ dalam semua kasus, kecuali ketika semua bilangan $z + λ_{1}, z + λ_{2}, \dots, z + λ_{n}$ adalah residu kuadrat atau non-residu secara bersamaan. Menurut teori siklotomi,^[8] peluang kejadiannya untuk kasus ketika $λ_{1}, \dots, λ_{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 $λ_{1}, \dots, λ_{n}$ .^[1] Dengan cara ini, bahkan untuk kasus galat $k = 1$ dan $f (x) = (x - λ)^{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_{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}} {mod f}_{z} (x)$ dilakukan di $O (n^{2} \log p)$ .
Eksponensial biner bekerja di $O (n^{2} \log p)$ .
Mengambil $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,^[9] maka kompleksitas algoritmanya dapat ditingkatkan menjadi $O (n \log n \log p n)$ . Untuk kasus akar kuadrat modular, derajatnya adalah $n = 2$ , sehingga seluruh kompleksitas algoritma dalam kasus tersebut dibatasi dengan $O (\log p)$ per iterasi.^[7]

Referensi

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 ^1,5 ^1,6 E. R Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation. 1970. Vol. 24 (111). hlm. 713–735. doi:10.1090/S0025-5718-1970-0276200-X.
↑ ^2,0 ^2,1 ^2,2 ^2,3 M. Rabin. Probabilistic Algorithms in Finite Fields. SIAM Journal on Computing. 1980. Vol. 9 (2). hlm. 273–280. doi:10.1137/0209024.
↑ Donald E Knuth. The art of computer programming. Vol. 2 Vol. 2. 1998. ISBN 978-0201896848.
↑ Tsz-Wo Sze. On taking square roots without quadratic nonresidues over finite fields. Mathematics of Computation. 2011. Vol. 80 (275). hlm. 1797–1811. doi:10.1090/s0025-5718-2011-02419-1.
↑ R. Peralta. A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.). IEEE Transactions on Information Theory. November 1986. Vol. 32 (6). hlm. 846–847. doi:10.1109/TIT.1986.1057236.
↑ C Padró, G Sáez. Taking cube roots in Zm. Applied Mathematics Letters. August 2002. Vol. 15 (6). hlm. 703–708. doi:10.1016/s0893-9659(02)00031-9.
↑ ^7,0 ^7,1 ^7,2 ^7,3 Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone. Applications of Finite Fields. Springer US. 1993. ISBN 9780792392828.
↑ Marshall Hall. Combinatorial Theory. John Wiley & Sons. 1998. ISBN 9780471315186.
↑ Aho, Alfred V. The design and analysis of computer algorithms. Addison-Wesley Pub. Co. 1974. ISBN 0201000296.

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 25986958 (2024-07-03T05:23:51Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

[:0-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 ^1,5 ^1,6 E. R Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation. 1970. Vol. 24 (111). hlm. 713–735. doi:10.1090/S0025-5718-1970-0276200-X.

[:1-2] 2,0 ^2,1 ^2,2 ^2,3 M. Rabin. Probabilistic Algorithms in Finite Fields. SIAM Journal on Computing. 1980. Vol. 9 (2). hlm. 273–280. doi:10.1137/0209024.

[3] Donald E Knuth. The art of computer programming. Vol. 2 Vol. 2. 1998. ISBN 978-0201896848.

[4] Tsz-Wo Sze. On taking square roots without quadratic nonresidues over finite fields. Mathematics of Computation. 2011. Vol. 80 (275). hlm. 1797–1811. doi:10.1090/s0025-5718-2011-02419-1.

[5] R. Peralta. A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.). IEEE Transactions on Information Theory. November 1986. Vol. 32 (6). hlm. 846–847. doi:10.1109/TIT.1986.1057236.

[6] C Padró, G Sáez. Taking cube roots in Zm. Applied Mathematics Letters. August 2002. Vol. 15 (6). hlm. 703–708. doi:10.1016/s0893-9659(02)00031-9.

[:2-7] 7,0 ^7,1 ^7,2 ^7,3 Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone. Applications of Finite Fields. Springer US. 1993. ISBN 9780792392828.

[8] Marshall Hall. Combinatorial Theory. John Wiley & Sons. 1998. ISBN 9780471315186.

[9] Aho, Alfred V. The design and analysis of computer algorithms. Addison-Wesley Pub. Co. 1974. ISBN 0201000296.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]