The linear complexity of m-phase related prime sequences is investigated for the case when m is composite. For each relatively prime factor pik of m, the linear complexity and the characteristic polynomial of the shortest linear feedback shift register that generates the pik-phase version of the sequence can be deduced and these results can then be combined using the Chinese remainder theorem to derive the m-phase values. These values are shown to depend on the categories of the sequence length computed modulo each factor of m, rather than on the category of the length modulo m itself, and that these values depend on the primitive roots employed. For a given length, the highest values of linear complexity result from constructing the sequences using those values of primitive elements that lead to non-zero categories for each factor of m.
References
-
-
1)
-
D.H. Green ,
P.R. Green
.
Polyphase Power Residue sequences.
Proc. R. Soc. Lond. A, Math. Phys. Eng. Sci.
,
817 -
827
-
2)
-
C. Ding ,
T. Helleseth ,
W. Shan
.
On the linear complexity of Legendre sequences.
IEEE Trans. Inf. Theory
,
3 ,
1276 -
1282
-
3)
-
C. Ding ,
D. Pei ,
A. Salomaa
.
(1996)
Chinese remainder theorem.
-
4)
-
C. Ding ,
T. Helleseth
.
On cyclotomic generator of order r.
Inf. Process. Lett.
,
21 -
25
-
5)
-
D.H. Green ,
M.D. Smith ,
N. Martzoukos
.
Linear Complexity of polyphase Power Residue sequences.
IEE Proc., Commun.
,
4 ,
195 -
201
-
6)
-
D.H. Green ,
L.P. Garcia-Perera
.
Linear complexity of related prime sequences.
Proc. R. Soc. Lond. A, Math. Phys. Eng. Sci.
,
487 -
498
-
7)
-
J.A. Reeds ,
N.J.A. Sloane
.
Shift-register synthesis (modulo m).
SIAM J. Comput.
,
3 ,
505 -
513
-
8)
-
D.H. Green
.
Linear complexity of modulo-m power residue sequences.
IEE Proc., Comput. Digit. Tech.
,
6 ,
385 -
390
-
9)
-
C. Ding
.
Linear complexity of generalized cyclotomic sequences of order 2.
Finite Fields Appl.
,
159 -
174
-
10)
-
D.H. Green ,
P.R. Green
.
Modified Jacobi sequences.
IEE Proc., Comput. Digit. Tech.
,
4 ,
241 -
251
-
11)
-
V.M. Sidelnikov
.
Pseudo-random sequences and nearly equidistant codes.
Probl. Pereda. Inf.
,
1 ,
16 -
22
-
12)
-
D.H. Green ,
P.R. Green
.
Polyphase-related prime sequences.
IEE Proc., Comput. Digit. Tech.
,
53 -
62
-
13)
-
D.H. Green ,
J. Choi
.
Linear complexity of modified Jacobi sequences.
IEE Proc., Comput. Digit. Tech.
,
3 ,
97 -
101
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cdt_20045120
Related content
content/journals/10.1049/ip-cdt_20045120
pub_keyword,iet_inspecKeyword,pub_concept
6
6