Algoritma Berlekamp–Rabin

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

Foto Algoritma Berlekamp–Rabin

Sejarah

sunting

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  .[5] Perumuman metode Peralita untuk persamaan kubik dibuat pada tahun 2000.[6]

Pernyataan masalah

sunting

Misalkan   adalah bilangan prima ganjil, dan misalkan pula polinomial   atas medan   dari modulo sisa  . Tujuan pernyataan masalah ini adalah bahwa algoritma Berlekamp harus menemukan semua   di   sehingga   di  .[2][7]

Algoritma

sunting

Pengacakan

sunting

Misalkan  . 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  , untuk   setiap anggota  . Jika polinomial tersebut dinyatakan sebagai hasilkali  , maka dalam bentuk polinomial awal, mengartikan bahwa  . Fungsi yang merupakan menyediakan faktorisasi dibutuhkan dari  .[1][7]

Klasifikasi elemen  

sunting

Menurut kriteria Euler, untuk setiap monomial  , berlaku tepat salah satu dari sifat-sifat berikut:[1]

  1. Monomial sama dengan   jika  ,
  2. Pembagian monomial   jika   adalah residu kuadrat modulo  ,
  3. Pembagian monomial   jika   adalah non-residul kuadrat modulo  .

Jadi, jika   tidak habis dibagi  , yang dapat diperiksa secara terpisah, maka   sama dengan hasilkali dari faktor persekutuan terbesar   dan  .[7]

Metode Berlekamp

sunting

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

  1. Hitung secara eksplisit koefisien  ,
  2. Hitung sisa   modulo   dengan mengkuadratkan polinomial dan mengambil sisa modulo  ,
  3. Menggunakan eksponensiasi yang dikuadratkan dan polinomial yang dihitung pada langkah sebelumnya, hitung sisa   modulo  ,
  4. Jika  , maka   yang disebutkan diatas memberikan faktorisasi non-trivial dari  ,
  5. Jika tidak, maka semua akar   adalah residu atau non-residu secara bersamaan dan harus memilih   yang lain.

Jika   habis dibagi oleh setiap polinomial primitif   atas   maka saat menghitung   dengan   dan   akan diperoleh faktorisasi non-trivial dari  , sehingga algoritma memungkinkan untuk menemukan semua akar polinomial sebarang atas  .

Akar kuadrat modular

sunting

Misalkan persamaan   mempunyai anggota   dan   sebagai akarnya. Solusi persamaan ini ekuivalen dengan faktorisasi polinomial   atas  . Dalam masalah kasus istimewa ini, cukup hitung   saja. Untuk polinomial tersebut, ada tepat satu dari sifat-sifat yang berlaku sebagai berikut:

  1. FPB sama dengan  , yang berarti bahwa   dan   merupakan non-residu kuadratik,
  2. FPB sama dengan  , yang berarti kedua bilangan tersebut merupakan residu kuadratik,
  3. FPB sama dengan  , yang berarti tepat salah satu dari bilangan tersebut merupakan residu kuadrat.

Pada kasus ketiga, FPB sama dengan   atau  . Hal ini memungkinkan untuk menulis solusi sebagai  .[1]

Contoh

sunting

Asumsi bahwa persamaan   dapat diselesaikan. Caranya adalah dengan memfaktorkan  . Nilai   dapat dibagi menjadi beberapa kasus dengan memisalkannya sebagai berikut:

  1. Misalkan  , maka  . Jadi,  . Karena bilangan   merupakan non-residu kuadrat, maka perlu dicari nilai   lain.
  2. Misalkan  , maka  . Jadi,  . Karena  , maka   dan  .

Hasil pemeriksaan yang dilakukan secara manual memperlihatkan bahwa   dan  .

Bukti kebenaran

sunting

Algoritma menemukan faktorisasi   dalam semua kasus, kecuali ketika semua bilangan   adalah residu kuadrat atau non-residu secara bersamaan. Menurut teori siklotomi,[8] peluang kejadiannya untuk kasus ketika   juga merupakan semua residu atau non-residu secara bersamaan (yaitu, ketika   tidak berhasil) diestimasi sebagai  , untuk   adalah jumlah nilai yang berbeda dalam  .[1] Dengan cara ini, bahkan untuk kasus galat   dan  , maka estimasi peluang galatnya adalah  , dan untuk kasus akar kuadrat modular, probabilitas galat setidaknya bernilai  .

Kompleksitas

sunting

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

  1. Karena menurut teorema binomial mengatakan bahwa  , maka dapat dilakukan transisi dari   ke   dalam waktu  .
  2. Perkalian polinomial dan mengambil sisa dari satu polinomial yang modulo dengan yang lain dapat dilakukan di  . Jadi, perhitungan   dilakukan di  .
  3. Eksponensial biner bekerja di  .
  4. Mengambil   dari dua polinomial melalui algoritma Euklides yang bekerja di  .

Jadi, seluruh prosedur dapat dilakukan di  . Dengan menggunakan transformasi Fourier cepat dan algoritma setengah-FPB,[9] maka kompleksitas algoritmanya dapat ditingkatkan menjadi  . Untuk kasus akar kuadrat modular, derajatnya adalah  , sehingga seluruh kompleksitas algoritma dalam kasus tersebut dibatasi dengan   per iterasi.[7]

Referensi

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

Templat:Algoritma teori bilangan