On cyclotomic generator of order \(r\). (English) Zbl 1078.94511

Summary: The cyclotomic generator of order \(r\) is studied in detail. Their linear complexity, minimal polynomial, and autocorrelation function of its output sequences are calculated. The decimation property of those sequences, the implementation and some applications are also considered.


94A60 Cryptography
65C10 Random number generation in numerical analysis
Full Text: DOI


[1] Boehmer, A. M., Binary pulse compression codes, IEEE Trans. Inform. Theory, IT-13, 156-166 (1967) · Zbl 0152.15409
[2] Chakrabarti, N. B.; Tomlinson, M., Design of sequences with specified autocorrelation and cross correlation, (IEEE Trans. Communications (November 1976)), 1246-1252 · Zbl 0344.94005
[3] Cusick, T. W.; Ding, C.; Renvall, A., Stream Ciphers and Number Theory (1998), North-Holland Mathematical Library, Elsevier/North-Holland: North-Holland Mathematical Library, Elsevier/North-Holland Amsterdam · Zbl 0930.11086
[4] Dickson, L. E., Cyclotomy, higher congruences, and Waring’s problem, Amer. J. Math., 57, 463-474 (1939), (Two references in one volume, but two issues.) · Zbl 0012.29004
[5] Ding, C., Binary cyclotomic generators, (Preneel, B., Fast Software Encryption. Fast Software Encryption, Lecture Notes in Comput. Sci., Vol. 1008 (1995), Springer: Springer Berlin), 29-60 · Zbl 0939.94512
[6] C. Ding, T. Helleseth, W. Shan, On the linear complexity of Legendre sequences, IEEE Trans. Inform. Theory, to appear.; C. Ding, T. Helleseth, W. Shan, On the linear complexity of Legendre sequences, IEEE Trans. Inform. Theory, to appear. · Zbl 0912.94014
[7] Ding, C.; Xiao, G.; Shan, W., The Stability Theory of Stream Ciphers, (Lecture Notes in Comput. Sci., Vol. 561 (1991), Springer: Springer Berlin) · Zbl 0762.94008
[8] Hauge, E. R.; Helleseth, T., DeBruijn sequences, irreducible codes and cyclotomy, Discrete Math., 159, 143-154 (1996) · Zbl 0878.94046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.