[1] Hu Weiqun, Yue Qin,. Fast algorithm for determining the minimal polynomialof upnn-periodic sequence [J]. Journal of Southeast University (English Edition), 2012, 28 (3): 367-371. [doi:10.3969/j.issn.1003-7985.2012.03.020]

Copy

Fast algorithm for determining the minimal polynomialof upⁿn-periodic sequence()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

28

Issue:

2012 3

Page:

367-371

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2012-09-30

Info

Title:

Fast algorithm for determining the minimal polynomialof upⁿn-periodic sequence

Author(s):

Hu Weiqun¹;  Yue Qin²

¹College of Science, Nanjing Forestry University, Nanjing 210037, China
²College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Keywords:

minimal polynomial;  linear complexity;  periodic sequence

PACS:

O236.2

DOI:

10.3969/j.issn.1003-7985.2012.03.020

Abstract:

A fast algorithm for determining the minimal polynomial and linear complexity of a upⁿ-periodic sequence over a finite field F_qq is given. Let p, q, and u be distinct primes, q a primitive root modulo p², m the smallest positive integer such that q^m≡1 mod u, and gcd(m, p(p-1))=1. An algorithm is used to reduce a periodic upⁿ sequence over F_qq to several pⁿ-periodic sequences over F_qq(ζ), where ζ is a u-th primitive root of unity, and an algorithm proposed by Xiao et al. is employed to obtain the minimal polynomial of each pⁿn-periodic sequence.

References:

[1] Blackburn S R. A generalization of the discrete Fourier transform: determining the minimal polynomial of a period sequence[J]. IEEE Trans Inf Theory, 1994, 40(5): 1702-1704.
[2] Chen H. Fast algorithms for determining the linear complexity of sequences over GF(p^m)with period 2^tntn[J]. IEEE Trans Inf Theory, 2005, 51(5): 1854-1856.
[3] Chen H. Reducing the computation of linear complexities of periodic sequences over GF(p^m)[J]. IEEE Trans Inf Theory, 2006, 52(12): 5537-5539.
[4] Ding C. A fast algorithm for the determination of linear complexity of sequences over GF(p^m)with period pⁿ[C]//Lecture Notes in Computer Science. Berlin: Springer-Verlag, 1991: 141-144.
[5] Ding C, Xiao G, Shan W. The stability theory of stream ciphers(Lecture Notes in Computer Science 561)[M]. Berlin: Springer-Verlag, 1991.
[6] Games R A, Chan A H. A fast algorithm for determining the complexity of a binary sequence with period 2ⁿn[J]. IEEE Trans Inf Theory, 1983, 29(1): 144-146.
[7] Lidl R, Niederreiter H. Finite fields[M]. Addison-Wesley Publishing Company, 1983.
[8] Massey J L. Shift register synthesis and BCH decoding[J]. IEEE Trans Inf Theory, 1969, 15(1): 122-127.
[9] Wei S, Xiao G, Chen Z. A fast algorithm for determining the minimal polynomial of a sequence with 2pⁿ over GF(q)[J]. IEEE Trans Inf Theory, 2002, 48(10): 2754-2758.
[10] Xiao G, Wei S, Lam K Y, et al. A fast algorithm for determining the linear complexity of a sequence with pⁿ over GF(q)[J]. IEEE Trans Inf Theory, 2000, 46(6): 2203-2206.

Memo

Memo:

Biography: Hu Weiqun(1958—), female, professor, huweiqun@njfu.edu.cn.
Foundation item: The National Natural Science Foundation of China(No. 10971250, 11171150).
Citation: Hu Weiqun, Yue Qin. Fast algorithm for determining the minimal polynomial of upⁿ-periodic sequence[J].Journal of Southeast University(English Edition), 2012, 28(3):367-371.[doi:10.3969/j.issn.1003-7985.2012.03.020]

Common functions