Algoritma Berlekamp–Rabin - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T03:02:44Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 03.02
Baris 1:		Baris 1:
	[[File:Elwyn_R_Berlekamp_2005.jpg\|thumb\|right\|280px\|Elwyn Berlekamp]]		[[File:Elwyn_R_Berlekamp_2005.jpg\|thumb\|right\|280px\|Elwyn R Berlekamp 2005]]

	Dalam [[teori bilangan]], '''algoritma Berlekamp–Rabin''' adalah metode [[Algoritma teracak\|probabilistik]] [[Algoritma pencarian akar\|pencarian akar]] dari [[polinomial]] pada [[medan berhingga\|medan]] <math>\mathbb Z_p</math>. Metode ini ditemukan oleh [[Elwyn Berlekamp]] pada tahun 1970<ref name=":0">E. R Berlekamp. [https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ Factoring polynomials over large finite fields]. ''Mathematics of Computation''. 1970. Vol. 24 (111). hlm. 713–735. doi:10.1090/S0025-5718-1970-0276200-X.</ref> sebagai tambahan [[algoritma Berlekamp\|algoritma]] untuk [[faktorisasi]] polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh [[Michael O. Rabin\|Rabin]] untuk medan berhingga sebarang pada tahun 1979.<ref name=":1">M. Rabin. ''Probabilistic Algorithms in Finite Fields''. ''SIAM Journal on Computing''. 1980. Vol. 9 (2). hlm. 273–280. doi:10.1137/0209024.</ref> Sebelum Berlekamp, metode ini juga ditemukan secara terpisah oleh peneliti lain.<ref>Donald E Knuth. ''The art of computer programming. Vol. 2 Vol. 2''. 1998. ISBN 978-0201896848.</ref>		Dalam [[teori bilangan]], '''algoritma Berlekamp–Rabin''' adalah metode [[Algoritma teracak\|probabilistik]] [[Algoritma pencarian akar\|pencarian akar]] dari [[polinomial]] pada [[medan berhingga\|medan]] <math>\mathbb Z_p</math>. Metode ini ditemukan oleh [[Elwyn Berlekamp]] pada tahun 1970<ref name=":0">E. R. Berlekamp. [https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ Factoring polynomials over large finite fields]. ''Mathematics of Computation''. 1970. Vol. 24 (111). hlm. 713–735. doi:10.1090/S0025-5718-1970-0276200-X.</ref> sebagai tambahan [[algoritma Berlekamp\|algoritma]] untuk [[faktorisasi]] polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh [[Michael O. Rabin\|Rabin]] untuk medan berhingga sebarang pada tahun 1979.<ref name=":1">M. Rabin. ''Probabilistic Algorithms in Finite Fields''. ''SIAM Journal on Computing''. 1980. Vol. 9 (2). hlm. 273–280. doi:10.1137/0209024.</ref> Sebelum Berlekamp, metode ini juga ditemukan secara terpisah oleh peneliti lain.<ref>Donald E Knuth. ''The art of computer programming. Vol. 2 Vol. 2''. 1998. ISBN 978-0201896848.</ref>

	== Sejarah ==		== Sejarah ==
Baris 13:		Baris 13:
	Misalkan <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. Menemukan semua akar polinomial ini sama saja dengan mencari faktorisasinya menjadi faktor [[Lincoln Near-Earth Asteroid Research\|linear]]. Untuk menemukan faktorisasi tersebut, cukup membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Lebih lanjut, misalkan polinomial <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math>, untuk <math>z</math> setiap anggota <math>\mathbb Z_p</math>. Jika polinomial tersebut dinyatakan sebagai hasilkali <math>f_z(x)=p_0(x)p_1(x)</math>, maka dalam bentuk polinomial awal, mengartikan bahwa <math>f(x) =p_0(x+z)p_1(x+z)</math>. Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari <math>f(x)</math>.<ref name=":0" /><ref name=":2" />		Misalkan <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. Menemukan semua akar polinomial ini sama saja dengan mencari faktorisasinya menjadi faktor [[Lincoln Near-Earth Asteroid Research\|linear]]. Untuk menemukan faktorisasi tersebut, cukup membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Lebih lanjut, misalkan polinomial <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math>, untuk <math>z</math> setiap anggota <math>\mathbb Z_p</math>. Jika polinomial tersebut dinyatakan sebagai hasilkali <math>f_z(x)=p_0(x)p_1(x)</math>, maka dalam bentuk polinomial awal, mengartikan bahwa <math>f(x) =p_0(x+z)p_1(x+z)</math>. Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari <math>f(x)</math>.<ref name=":0" /><ref name=":2" />

	=== Klasifikasi elemen Zₚ ===		=== Klasifikasi elemen Z_p ===
	Menurut [[kriteria Euler]], untuk setiap [[monomial]] <math>(x-\lambda)</math>, berlaku tepat salah satu dari sifat-sifat berikut:<ref name=":0" />		Menurut [[kriteria Euler]], untuk setiap [[monomial]] <math>(x-\lambda)</math>, berlaku tepat salah satu dari sifat-sifat berikut:<ref name=":0" />

Baris 69:		Baris 69:

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma_Berlekamp%E2%80%93Rabin&oldid=25986958 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.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma_Berlekamp%E2%80%93Rabin&oldid=25986958 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.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Penyederhanaan sumber dan atribusi

2026-08-23T02:55:42Z

Penyederhanaan sumber dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 02.55
Baris 68:		Baris 68:
	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	~~Sebagian konten~~ artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=~~Algoritma_Berlekamp–Rabin~~&oldid=25986958 Wikipedia bahasa Indonesia], revisi 25986958 (2024-07-03T05:23:51Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA).		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma_Berlekamp%E2%80%93Rabin&oldid=25986958 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.

	Gambar ~~yang ditampilkan berasal~~ dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. ~~Infobox, templat navigasi, kategori sumber,~~ dan ~~elemen teknis Wikipedia lainnya tidak diimpor ke Wiki Unissula~~.

Maintenance script: Perbaikan presentasi: sitasi, referensi, caption, dan atribusi

2026-08-23T02:51:42Z

Perbaikan presentasi: sitasi, referensi, caption, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 02.51
Baris 1:		Baris 1:
	[[File:Elwyn_R_Berlekamp_2005.jpg\|thumb\|right\|280px\|Elwyn R Berlekamp ~~2005~~]]		[[File:Elwyn_R_Berlekamp_2005.jpg\|thumb\|right\|280px\|Elwyn Berlekamp]]

	Dalam [[teori bilangan]], '''algoritma Berlekamp–Rabin''' adalah metode [[Algoritma teracak\|probabilistik]] [[Algoritma pencarian akar\|pencarian akar]] dari [[polinomial]] pada [[medan berhingga\|medan]] <math>\mathbb Z_p</math>. Metode ini ditemukan oleh [[Elwyn Berlekamp]] pada tahun 1970 sebagai tambahan [[algoritma Berlekamp\|algoritma]] untuk [[faktorisasi]] polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh [[Michael O. Rabin\|Rabin]] untuk medan berhingga sebarang pada tahun 1979. Sebelum Berlekamp, metode ini juga ditemukan secara terpisah oleh peneliti lain.		Dalam [[teori bilangan]], '''algoritma Berlekamp–Rabin''' adalah metode [[Algoritma teracak\|probabilistik]] [[Algoritma pencarian akar\|pencarian akar]] dari [[polinomial]] pada [[medan berhingga\|medan]] <math>\mathbb Z_p</math>. Metode ini ditemukan oleh [[Elwyn Berlekamp]] pada tahun 1970<ref name=":0">E. R Berlekamp. [https://www.ams.org/mcom/1970-24-111/S0025-5718-1970-0276200-X/ Factoring polynomials over large finite fields]. ''Mathematics of Computation''. 1970. Vol. 24 (111). hlm. 713–735. doi:10.1090/S0025-5718-1970-0276200-X.</ref> sebagai tambahan [[algoritma Berlekamp\|algoritma]] untuk [[faktorisasi]] polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh [[Michael O. Rabin\|Rabin]] untuk medan berhingga sebarang pada tahun 1979.<ref name=":1">M. Rabin. ''Probabilistic Algorithms in Finite Fields''. ''SIAM Journal on Computing''. 1980. Vol. 9 (2). hlm. 273–280. doi:10.1137/0209024.</ref> Sebelum Berlekamp, metode ini juga ditemukan secara terpisah oleh peneliti lain.<ref>Donald E Knuth. ''The art of computer programming. Vol. 2 Vol. 2''. 1998. ISBN 978-0201896848.</ref>

	== Sejarah ==		== Sejarah ==
	Metode ini diusulkan oleh [[Elwyn Berlekamp]] dalam karyanya tahun 1970 tentang faktorisasi polinomial pada medan berhingga. Karya aslinya tidak memiliki bukti [[Kebenaran (ilmu komputer)\|kebenaran]] formal dan kemudian disempurnakan dan dimodifikasi untuk medan berhingga sebarang oleh [[Michael O. Rabin\|Michael Rabin]]. Pada tahun 1986, René Peralta mengusulkan algoritma serupa untuk mencari akar kuadrat <math>\mathbb Z_p</math>. Perumuman metode Peralita untuk persamaan kubik dibuat pada tahun 2000.		Metode ini diusulkan oleh [[Elwyn Berlekamp]] dalam karyanya tahun 1970<ref name=":0" /> tentang faktorisasi polinomial pada medan berhingga. Karya aslinya tidak memiliki bukti [[Kebenaran (ilmu komputer)\|kebenaran]] formal<ref name=":1" /> dan kemudian disempurnakan dan dimodifikasi untuk medan berhingga sebarang oleh [[Michael O. Rabin\|Michael Rabin]].<ref name=":1" /> Pada tahun 1986, René Peralta mengusulkan algoritma serupa<ref>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.</ref> untuk mencari akar kuadrat <math>\mathbb Z_p</math>.<ref>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.</ref> Perumuman metode Peralita untuk persamaan kubik dibuat pada tahun 2000.<ref>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.</ref>

	== Pernyataan masalah==		== Pernyataan masalah==
	Misalkan <math>p</math> adalah [[bilangan prima]] ganjil, dan misalkan pula polinomial <math display="inline">f(x) = a_0 + a_1 x + \cdots + a_n x^n</math> atas medan <math>\mathbb Z_p</math> dari modulo sisa <math>p</math>. Tujuan pernyataan masalah ini adalah bahwa algoritma Berlekamp harus menemukan semua <math>\lambda</math> di <math>\mathbb Z_p</math> sehingga <math display="inline">f(\lambda)= 0</math> di <math>\mathbb Z_p</math>.		Misalkan <math>p</math> adalah [[bilangan prima]] ganjil, dan misalkan pula polinomial <math display="inline">f(x) = a_0 + a_1 x + \cdots + a_n x^n</math> atas medan <math>\mathbb Z_p</math> dari modulo sisa <math>p</math>. Tujuan pernyataan masalah ini adalah bahwa algoritma Berlekamp harus menemukan semua <math>\lambda</math> di <math>\mathbb Z_p</math> sehingga <math display="inline">f(\lambda)= 0</math> di <math>\mathbb Z_p</math>.<ref name=":1" /><ref name=":2">Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone. [https://www.springer.com/gp/book/9780792392828 Applications of Finite Fields]. Springer US. 1993. ISBN 9780792392828.</ref>

	== Algoritma ==		== Algoritma ==
	=== Pengacakan ===		=== Pengacakan ===
	Misalkan <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. Menemukan semua akar polinomial ini sama saja dengan mencari faktorisasinya menjadi faktor [[Lincoln Near-Earth Asteroid Research\|linear]]. Untuk menemukan faktorisasi tersebut, cukup membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Lebih lanjut, misalkan polinomial <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math>, untuk <math>z</math> setiap anggota <math>\mathbb Z_p</math>. Jika polinomial tersebut dinyatakan sebagai hasilkali <math>f_z(x)=p_0(x)p_1(x)</math>, maka dalam bentuk polinomial awal, mengartikan bahwa <math>f(x) =p_0(x+z)p_1(x+z)</math>. Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari <math>f(x)</math>.		Misalkan <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. Menemukan semua akar polinomial ini sama saja dengan mencari faktorisasinya menjadi faktor [[Lincoln Near-Earth Asteroid Research\|linear]]. Untuk menemukan faktorisasi tersebut, cukup membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Lebih lanjut, misalkan polinomial <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math>, untuk <math>z</math> setiap anggota <math>\mathbb Z_p</math>. Jika polinomial tersebut dinyatakan sebagai hasilkali <math>f_z(x)=p_0(x)p_1(x)</math>, maka dalam bentuk polinomial awal, mengartikan bahwa <math>f(x) =p_0(x+z)p_1(x+z)</math>. Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari <math>f(x)</math>.<ref name=":0" /><ref name=":2" />

	=== Klasifikasi elemen Zₚ ===		=== Klasifikasi elemen Zₚ ===
	Menurut [[kriteria Euler]], untuk setiap [[monomial]] <math>(x-\lambda)</math>, berlaku tepat salah satu dari sifat-sifat berikut:		Menurut [[kriteria Euler]], untuk setiap [[monomial]] <math>(x-\lambda)</math>, berlaku tepat salah satu dari sifat-sifat berikut:<ref name=":0" />

	# Monomial sama dengan <math>x</math> jika <math>\lambda = 0</math>,		# Monomial sama dengan <math>x</math> jika <math>\lambda = 0</math>,
Baris 20:		Baris 20:
	# Pembagian monomial <math display="inline">g_1(x)=(x^{(p-1)/2}+1)</math> jika <math>\lambda</math> adalah non-residul kuadrat modulo <math>p</math>.		# Pembagian monomial <math display="inline">g_1(x)=(x^{(p-1)/2}+1)</math> jika <math>\lambda</math> adalah non-residul kuadrat modulo <math>p</math>.

	Jadi, jika <math>f_z(x)</math> tidak habis dibagi <math>x</math>, yang dapat diperiksa secara terpisah, maka <math>f_z(x)</math> sama dengan hasilkali dari [[faktor persekutuan terbesar polinomial\|faktor persekutuan terbesar]] <math>\operatorname{FPB}(f_z(x);g_0(x))</math> dan <math>\operatorname{FPB}(f_z(x);g_1(x))</math>.		Jadi, jika <math>f_z(x)</math> tidak habis dibagi <math>x</math>, yang dapat diperiksa secara terpisah, maka <math>f_z(x)</math> sama dengan hasilkali dari [[faktor persekutuan terbesar polinomial\|faktor persekutuan terbesar]] <math>\operatorname{FPB}(f_z(x);g_0(x))</math> dan <math>\operatorname{FPB}(f_z(x);g_1(x))</math>.<ref name=":2" />

	=== Metode Berlekamp ===		=== Metode Berlekamp ===
	Sifat-sifat di atas mengarah pada algoritma berikut:		Sifat-sifat di atas mengarah pada algoritma berikut:<ref name=":0" />

	# Hitung secara eksplisit koefisien <math>f_z(x) = f(x-z)</math>,		# Hitung secara eksplisit koefisien <math>f_z(x) = f(x-z)</math>,
Baris 40:		Baris 40:
	# FPB sama dengan <math>(x-t)</math>, yang berarti tepat salah satu dari bilangan tersebut merupakan residu kuadrat.		# FPB sama dengan <math>(x-t)</math>, yang berarti tepat salah satu dari bilangan tersebut merupakan residu kuadrat.

	Pada kasus ketiga, FPB sama dengan <math>(x-z-\beta)</math> atau <math>(x-z+\beta)</math>. Hal ini memungkinkan untuk menulis solusi sebagai <math display="inline">\beta = (t - z) \pmod{p}</math>.		Pada kasus ketiga, FPB sama dengan <math>(x-z-\beta)</math> atau <math>(x-z+\beta)</math>. Hal ini memungkinkan untuk menulis solusi sebagai <math display="inline">\beta = (t - z) \pmod{p}</math>.<ref name=":0" />

	=== Contoh ===		=== Contoh ===
Baris 51:		Baris 51:

	== Bukti kebenaran ==		== Bukti kebenaran ==
	Algoritma menemukan faktorisasi <math>f_z(x)</math> dalam semua kasus, kecuali ketika semua bilangan <math>z+\lambda_1, z+\lambda_2, \ldots, z+\lambda_n</math> adalah residu kuadrat atau non-residu secara bersamaan. Menurut [[teori siklotomi]], peluang kejadiannya untuk kasus ketika <math>\lambda_1, \ldots, \lambda_n</math> juga merupakan semua residu atau non-residu secara bersamaan (yaitu, ketika <math>z=0</math> tidak berhasil) diestimasi sebagai <math>2^{-k}</math>, untuk <math>k</math> adalah jumlah nilai yang berbeda dalam <math>\lambda_1, \ldots, \lambda_n</math>. Dengan cara ini, bahkan untuk kasus galat <math>k=1</math> dan <math>f(x)=(x-\lambda)^n</math>, maka estimasi peluang galatnya adalah <math>1/2</math>, dan untuk kasus [[akar kuadrat]] modular, probabilitas galat setidaknya bernilai <math>1/4</math>.		Algoritma menemukan faktorisasi <math>f_z(x)</math> dalam semua kasus, kecuali ketika semua bilangan <math>z+\lambda_1, z+\lambda_2, \ldots, z+\lambda_n</math> adalah residu kuadrat atau non-residu secara bersamaan. Menurut [[teori siklotomi]],<ref>Marshall Hall. [https://books.google.com/books?id=__JCiiCfu2EC&q=Combinatorial+Theory+hall&pg=PA1 Combinatorial Theory]. John Wiley & Sons. 1998. ISBN 9780471315186.</ref> peluang kejadiannya untuk kasus ketika <math>\lambda_1, \ldots, \lambda_n</math> juga merupakan semua residu atau non-residu secara bersamaan (yaitu, ketika <math>z=0</math> tidak berhasil) diestimasi sebagai <math>2^{-k}</math>, untuk <math>k</math> adalah jumlah nilai yang berbeda dalam <math>\lambda_1, \ldots, \lambda_n</math>.<ref name=":0" /> Dengan cara ini, bahkan untuk kasus galat <math>k=1</math> dan <math>f(x)=(x-\lambda)^n</math>, maka estimasi peluang galatnya adalah <math>1/2</math>, dan untuk kasus [[akar kuadrat]] modular, probabilitas galat setidaknya bernilai <math>1/4</math>.

	== Kompleksitas ==		== Kompleksitas ==
Baris 61:		Baris 61:
	# Mengambil <math>\operatorname{FPB}</math> dari dua polinomial melalui [[algoritma Euklides]] yang bekerja di <math>O(n^2)</math>.		# Mengambil <math>\operatorname{FPB}</math> dari dua polinomial melalui [[algoritma Euklides]] yang bekerja di <math>O(n^2)</math>.

	Jadi, seluruh prosedur dapat dilakukan di <math>O(n^2 \log p)</math>. Dengan menggunakan [[transformasi Fourier cepat]] dan algoritma setengah-FPB, maka kompleksitas algoritmanya dapat ditingkatkan menjadi <math>O(n \log n \log pn)</math>. Untuk kasus akar kuadrat modular, derajatnya adalah <math>n = 2</math>, sehingga seluruh kompleksitas algoritma dalam kasus tersebut dibatasi dengan <math>O(\log p)</math> per iterasi.		Jadi, seluruh prosedur dapat dilakukan di <math>O(n^2 \log p)</math>. Dengan menggunakan [[transformasi Fourier cepat]] dan algoritma setengah-FPB,<ref>Aho, Alfred V. [https://archive.org/details/designanalysisof00ahoarich The design and analysis of computer algorithms]. Addison-Wesley Pub. Co. 1974. ISBN 0201000296.</ref> maka kompleksitas algoritmanya dapat ditingkatkan menjadi <math>O(n \log n \log pn)</math>. Untuk kasus akar kuadrat modular, derajatnya adalah <math>n = 2</math>, sehingga seluruh kompleksitas algoritma dalam kasus tersebut dibatasi dengan <math>O(\log p)</math> per iterasi.<ref name=":2" />

	== Referensi ==		== Referensi ==
	<br />		<references />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==
	~~Artikel~~ ini diadaptasi ~~dalam mode teks~~ dari
	[https://id.wikipedia.org/w/index.php?title=~~Algoritma_Berlekamp%E2%80%93Rabin~~&oldid=25986958 Wikipedia bahasa Indonesia],		Sebagian konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma_Berlekamp–Rabin&oldid=25986958 Wikipedia bahasa Indonesia], revisi 25986958 (2024-07-03T05:23:51Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA).
	revisi 25986958 (2024-07-03T05:23:51Z).
	~~Gambar~~, ~~media, infobox, templat navigasi, dan kategori sumber~~		Gambar yang ditampilkan berasal dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Infobox, templat navigasi, kategori sumber, dan elemen teknis Wikipedia lainnya tidak diimpor ke Wiki Unissula.
	~~tidak diimpor ke Wiki Unissula.~~
	~~Atribusi dan~~ lisensi ~~mengikuti ketentuan~~ Creative Commons
	Atribusi-BerbagiSerupa (CC BY-SA) ~~pada~~ sumber Wikipedia.

Maintenance script: Perbaikan presentasi: gambar Commons dan heading matematika

2026-08-23T02:42:25Z

Perbaikan presentasi: gambar Commons dan heading matematika

← Revisi sebelumnya		Revisi per 23 Agustus 2026 02.42
Baris 1:		Baris 1:
			[[File:Elwyn_R_Berlekamp_2005.jpg\|thumb\|right\|280px\|Elwyn R Berlekamp 2005]]

	Dalam [[teori bilangan]], '''algoritma Berlekamp–Rabin''' adalah metode [[Algoritma teracak\|probabilistik]] [[Algoritma pencarian akar\|pencarian akar]] dari [[polinomial]] pada [[medan berhingga\|medan]] <math>\mathbb Z_p</math>. Metode ini ditemukan oleh [[Elwyn Berlekamp]] pada tahun 1970 sebagai tambahan [[algoritma Berlekamp\|algoritma]] untuk [[faktorisasi]] polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh [[Michael O. Rabin\|Rabin]] untuk medan berhingga sebarang pada tahun 1979. Sebelum Berlekamp, metode ini juga ditemukan secara terpisah oleh peneliti lain.		Dalam [[teori bilangan]], '''algoritma Berlekamp–Rabin''' adalah metode [[Algoritma teracak\|probabilistik]] [[Algoritma pencarian akar\|pencarian akar]] dari [[polinomial]] pada [[medan berhingga\|medan]] <math>\mathbb Z_p</math>. Metode ini ditemukan oleh [[Elwyn Berlekamp]] pada tahun 1970 sebagai tambahan [[algoritma Berlekamp\|algoritma]] untuk [[faktorisasi]] polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh [[Michael O. Rabin\|Rabin]] untuk medan berhingga sebarang pada tahun 1979. Sebelum Berlekamp, metode ini juga ditemukan secara terpisah oleh peneliti lain.

Baris 8:		Baris 10:

	== Algoritma ==		== Algoritma ==

	=== Pengacakan ===		=== Pengacakan ===
	Misalkan <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. Menemukan semua akar polinomial ini sama saja dengan mencari faktorisasinya menjadi faktor [[Lincoln Near-Earth Asteroid Research\|linear]]. Untuk menemukan faktorisasi tersebut, cukup membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Lebih lanjut, misalkan polinomial <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math>, untuk <math>z</math> setiap anggota <math>\mathbb Z_p</math>. Jika polinomial tersebut dinyatakan sebagai hasilkali <math>f_z(x)=p_0(x)p_1(x)</math>, maka dalam bentuk polinomial awal, mengartikan bahwa <math>f(x) =p_0(x+z)p_1(x+z)</math>. Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari <math>f(x)</math>.		Misalkan <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. Menemukan semua akar polinomial ini sama saja dengan mencari faktorisasinya menjadi faktor [[Lincoln Near-Earth Asteroid Research\|linear]]. Untuk menemukan faktorisasi tersebut, cukup membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Lebih lanjut, misalkan polinomial <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math>, untuk <math>z</math> setiap anggota <math>\mathbb Z_p</math>. Jika polinomial tersebut dinyatakan sebagai hasilkali <math>f_z(x)=p_0(x)p_1(x)</math>, maka dalam bentuk polinomial awal, mengartikan bahwa <math>f(x) =p_0(x+z)p_1(x+z)</math>. Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari <math>f(x)</math>.

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

Baris 63:		Baris 64:

	== Referensi ==		== Referensi ==


	<br />		<br />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Artikel ini diadaptasi dalam mode teks dari		Artikel ini diadaptasi dalam mode teks dari
	[https://id.wikipedia.org/w/index.php?title=Algoritma_Berlekamp%E2%80%93Rabin&oldid=25986958 Wikipedia bahasa Indonesia],		[https://id.wikipedia.org/w/index.php?title=Algoritma_Berlekamp%E2%80%93Rabin&oldid=25986958 Wikipedia bahasa Indonesia],

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 25986958; atribusi sumber disertakan.

2026-08-23T02:28:14Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 25986958; atribusi sumber disertakan.

Halaman baru

Dalam [[teori bilangan]], '''algoritma Berlekamp–Rabin''' adalah metode [[Algoritma teracak|probabilistik]] [[Algoritma pencarian akar|pencarian akar]] dari [[polinomial]] pada [[medan berhingga|medan]] <math>\mathbb Z_p</math>. Metode ini ditemukan oleh [[Elwyn Berlekamp]] pada tahun 1970 sebagai tambahan [[algoritma Berlekamp|algoritma]] untuk [[faktorisasi]] polinomial pada medan berhingga. Algoritma kemudian dimodifikasi oleh [[Michael O. Rabin|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 (ilmu komputer)|kebenaran]] formal dan kemudian disempurnakan dan dimodifikasi untuk medan berhingga sebarang oleh [[Michael O. Rabin|Michael Rabin]]. Pada tahun 1986, René Peralta mengusulkan algoritma serupa untuk mencari akar kuadrat <math>\mathbb Z_p</math>. Perumuman metode Peralita untuk persamaan kubik dibuat pada tahun 2000.

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

== Algoritma ==

=== Pengacakan ===
Misalkan <math display="inline">f(x) = (x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_n)</math>. Menemukan semua akar polinomial ini sama saja dengan mencari faktorisasinya menjadi faktor [[Lincoln Near-Earth Asteroid Research|linear]]. Untuk menemukan faktorisasi tersebut, cukup membagi polinomial menjadi dua pembagi non-trivial dan memfaktorkannya secara rekursif. Lebih lanjut, misalkan polinomial <math display="inline">f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \cdots (x-\lambda_n-z)</math>, untuk <math>z</math> setiap anggota <math>\mathbb Z_p</math>. Jika polinomial tersebut dinyatakan sebagai hasilkali <math>f_z(x)=p_0(x)p_1(x)</math>, maka dalam bentuk polinomial awal, mengartikan bahwa <math>f(x) =p_0(x+z)p_1(x+z)</math>. Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari <math>f(x)</math>.

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

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

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

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

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

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

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

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

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

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

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

Hasil pemeriksaan yang dilakukan secara [[Transmisi manual|manual]] memperlihatkan bahwa <math display="inline">7^2 \equiv 49 \equiv 5\pmod{11}</math> dan <math display="inline">4^2\equiv 16 \equiv 5\pmod{11}</math>.

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

== Kompleksitas ==
Misalkan suatu polinomial merupakan polinomial berderajat <math>n</math>, maka kompleksitas algoritma dapat diturunkan sebagai berikut:

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

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

== Referensi ==

<br />

== Sumber dan atribusi ==

Artikel ini diadaptasi dalam mode teks dari
[https://id.wikipedia.org/w/index.php?title=Algoritma_Berlekamp%E2%80%93Rabin&oldid=25986958 Wikipedia bahasa Indonesia],
revisi 25986958 (2024-07-03T05:23:51Z).
Gambar, media, infobox, templat navigasi, dan kategori sumber
tidak diimpor ke Wiki Unissula.
Atribusi dan lisensi mengikuti ketentuan Creative Commons
Atribusi-BerbagiSerupa (CC BY-SA) pada sumber Wikipedia.