中文

Journal of Shanghai University >

2020 , Vol. 26 >Issue 2: 189 - 196

DOI: https://doi.org/10.12066/j.issn.1007-2861.2026

Research Articles

Factorization of xn-1 over finite field Fp

Expand
  • College of Sciences, Shanghai University, Shanghai 200444, China

Received date: 2018-04-04

  Online published: 2020-04-29

Fold

Abstract

Let p be an odd prime number. This paper presents an algorithm for the factorization of xn-1 over prime field Fp, where n=d(p+1), d|(p-1) and d＜p-1. As is suggested, the factorization problem can be solved by Dickson polynomials based on a primitive polynomial over Fp. Some examples are provided for the explanation of this algorithm.

Key words： Dickson polynomials; primitive polynomials; factorization of polynomial

Cite this article

DING Yang, WANG Yongchao . Factorization of xn-1 over finite field Fp[J]. Journal of Shanghai University, 2020 , 26(2) : 189 -196 . DOI: 10.12066/j.issn.1007-2861.2026

References

[1] Berlekamp E R . Factoring polynomials over large finite fields[J]. Mathematics of Computation, 1970,24(111):713-735.
[2] Lidl R, Niederreiter H. Finite fields [M]. Cambridge: Cambridge University Press, 1996: 125-126.
[3] Meyn H . Factorization of the cyclotomic polynomial x2n+1 over finite fiels[J]. Finite Fields and Their Applications, 1996,2:439-442.
[4] Stichtenoth H, Topuzoglu A . Factorization of a class of polynomials over finite fields[J]. Finite Fields and Their Applications, 2012,18:108-122.
[5] Ling S, Solé P . On the algebraic structure of quasi-cyclic codesⅠ: finite fields[J]. IEEE Trans Inform Theory, 2001,47:2751-2760.
[6] Ling S, Solé P . On the algebraic structure of quasi-cyclic codesⅡ: chain rings[J]. Design Codes Cryp, 2003,30:113-130.
[7] Chou W S . The factorization of Dickson polynomials over finite fields[J]. Finite Fields and Their Applications, 1997,3:84-96.
[8] Fitzgerald R W, Yucas J L . Factors of Dickson polynomials over finite fields[J]. Finite Fields and Their Applications, 2005,11:724-737.
[9] Fitzgerald R W, Yucas J L . Generalized reciprocals, factors of Dickson polynomials and generalized cyclotomic polynomials over finite fields[J]. Finite Fields and Their Applications, 2007,13:492-515.
[10] Huffman W C, Pless V. Fundamentals of error-correcting codes [M]. New York: Cambridge University Press, 2003: 122-123.
[11] Mullen G L, Panarlo D. Handbook of finite fields [M]. Boca Raton: CRC Press, 2013: 282-283.
Options
Outlines

/

〈 〉