Faktorisasi Polinomial Square-Free dan bukan Square-Free atas Lapangan Hingga Zp

Juli Loisiana Butar-butar, Ferdinand Sinuhaji

Abstract


Abstrak: Faktorisasi polinomial merupakan suatu proses penguraian suatu  polinomial berderajat n menjadi polinomial-polinomial lain yang berderajat lebih kecil dari n.  Faktorisasi polinomial atas lapangan hingga  merupakan suatu proses pengerjaan yang relative tidak mudah. Oleh karena itu, diperlukan suatu metode yang berupa algoritma untuk memproses faktorisasi polinomial. Algoritma Faktorisasi Berlekamp merupakan salah satu metode terbaik dalam memfaktorisasi polinomial atas lapangan hingga . Polinomial atas lapangan terbagi dua kategori berdasarkan faktorisasinya, yaitu polinomial square-free dan bukan square-free. Polinomial square-free adalah polinomial dimana setiap faktorisasi tak tereduksi tunggal. Sedangkan bukan square-free adalah sebaliknya. Penelitian ini bertujuan untuk membuat suatu algoritma untuk menfaktorkan polinomial square-free dan bukan square-free atas lapangan hingga. Adapun (Divasὀn, Joosten, Thiemann, & Yamada, 2017) yang menjadi referensi utama dalam penelitian ini adalah berdasarkan. Namun, dibatasi hanya untuk polinomial square-free saja. Untuk itulah dengan menggunakan konsep polinomial faktorisasi ganda. Pada bagian akhir penelitian akan mengimplementasikan algoritma baru yang telah disusun.

 

Abstract:  Polynomial factorization is a decomposition of a polynomial of degree n into other polynomials whose degree is less than n. Polynomial factorization over finite field  is a relatively easy in process. Therefore, it’s needed a method in the form of an algorithm to process polynomial factorization. Algorithm Factorization Berlekamp is one of the best methods in factoring polynomials over a finite field  . Polynomials over field are divided into two category based on its factorization, namely square-free and not square-free polynomials. Square-free polynomials are polynomials in which each irreducible factorization is single. When non square-free is the opposite. This research aims to set an algorithm for factoring square-free polynomials and non square-free polynomials over a finite field   . The main reference in this research is based on (Divasὀn, Joosten, Thiemann, & Yamada, 2017) (Saropah, 2012). However, it is restricted only  to square-free polynomials. For this reason, this research will use the concept of repeated factorization polynomials. At the end of the research will implement a new algorithm that has been set.

Keywords


Faktorisasi Polinomial; Lapangan Hingga; Algoritma Berlekamp.

Full Text:

PDF

References


Abdel-Ghaffar, K. (2012). Counting Matrices over Finite Field Having a Given Number of Rows of Unit Weight. Linear Algebra and its Applications, 436, 2665-2669.

Aransay, J., & Divasón, J. (2016). Formalisation of the computation of the echelon form of a matrix in Isabelle/HOL. Formal Aspects of Computing, 28, 1005–1026.

Batoul, A., Guenda, K., & Gulliver, T. A. (2015). Repeated-Root Isodual Cyclic Codes over Finite Fields. Springer International Publishing Switzerland 2015, 119–132.

Butar-butar, J. L. (2018). Menentukan Grup Galois Pada Polinomial Rasional Dengan Pengembangan Metode Stauduhar. Jurnal Curere, 2(2), 184-193.

Cao, Y., & Gao, Y. (2014). Repeated root cyclic F_q-linear codes over F_(q^l ). Journal Finite Fields and Their Applications, 31, 202–227.

Childs, L. N. (2009). A Concrete Introduction to Higher Algebra Third edition. New York: Springer.

Couveignes, J.-M., & Lercier, R. (2013). Fast Construction of Irreducible Polynomials over Finite Fields. Israel Journal of Mathematics, 194, 77–105.

Ding, C. (2017). A sequence construction of cyclic codes over finite fields. Cryptography and Communications, 10(2), 319–341.

Divasón, J., Joosten, S., Thiemann, R., & Yamada, A. (2019). A Verified Implementation of the Berlekamp–Zassenhaus Factorization Algorithm. Journal of Automated Reasoning, 63, 1-37. doi:https://doi.org/10.1007/s10817-019-09526-y

Divasὀn, J., Joosten, S., Thiemann, R., & Yamada, A. (2017). A Formalization of the Berlekamp–Zassenhaus Factorization Algorithm. CPP 2017 Proceeding of the 6th ACM SIGPLAN Conference on Certified Programs and Proofs, (pp. 17-29).

Grout, J. (2010). The minimum rank problem over finite fields. Electronic Journal of Linear Algebra, 20, 691-716.

Hanif, S., & Imran, M. (2011). Factorization Algorithms for Polynomials over Finite Fields. Linnæus University, Departement of Mathematics. Retrieved April 19, 2019, from http://www.diva-portal.org/smash/get/diva2:414578/FULLTEXT01.pdf

Iliev, A., & Kyurkchiev, N. (2018). A Note on Euclidean and Extended Euclidean Algorithms for Greatest Common Divisor for Polynomials. International Journal of Pure and Applied Mathematics, 118(3), 713-721.

Irwan, M. (2017). Pengantar Matlab Untuk Sistem Persamaan Linear. Jurnal MSA, 5(2), 48-53.

Lee, M. M.-D. (2013). Factorization of multivariate polynomials. Dissertation, Technischen Universitat Kaiserslautern, Mathematics, Kaiserslautern. Retrieved July 28, 2019, from https://d-nb.info/1036637972/34

Mursyidah, H. (2017). Algoritma Polinomial Minimum untuk Membentuk Matriks Diagonal dari Matriks Persegi. Aksioma Jurnal Pendidikan Matematika FKIP Univ. Muhammadiyah Metro, 6(2), 282-293.

Oktafia, R., Gemawati , & Endang. (2014). Faktorisasi Polinomial Aljabar dengan Menggunakan Metode Euclidean dan Faktor Persekutuan Terbesar. Jurnal Online Mahasiswa FMIPA UNRI, 1-5.

Saropah. (2012). Akar-Akar Polinomial Separable Sebagai Pembentuk Perluasan Normal Pada Ring Modulo. Jurnal Cauchy, 2(3), 148-153.

Syaharuddin, & Mandailina, V. (2017). Pengembangan Modul Pemrograman Komputer Berbasis Matlab. Jurnal Teori dan Aplikasi Matematika, 1(1), 1-4.

Temnhurne, J., & Sathe, S. R. (2016). New Modified Euclidean and Binary Greatest Common Divisor Algorithm., 62(6), 852-858. IETE Journal of Research, 62(6), 852-858.




DOI: https://doi.org/10.31764/jtam.v3i2.1079

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Jurnal Teori dan Aplikasi Matematika (JTAM)

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

_______________________________________________

Creative Commons License

JTAM (Jurnal Teori dan Aplikasi Matematika) is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License

_______________________________________________

_______________________________________________

JTAM (Jurnal Teori dan Aplikasi Matematika) Editorial Office: