Frequency characteristics of coordinate sequences of linear recurrences over Galois rings

O. V. Kamlovskii

Izvestiya. Mathematics , Tome 77 (2013) no. 6, pp. 1130-1154.

Résumé

We consider some properties of the coordinate sequences of linear recurrences over Galois rings which characterize the possibility of regarding them as pseudo-random sequences. We study the periodicity properties, linear complexity and frequency characteristics of these sequences. Up to now, these parameters have been studied mainly in the case when the linear recurring sequence has maximal possible period. We investigate the coordinate sequences of linear recurrences of not necessarily maximal period. We obtain sharpened and generalized estimates for the number of elements and $r$-patterns on the cycles and intervals of these sequences.

Détail

Keywords: Galois rings, linear recurring sequences, distribution of elements in sequences, coordinate sequences, exponential sums.

Bibliographie

[1] A. A. Nechaev, “Kerdock code in a cyclic form”, Discrete Math. Appl., 1:4 (1991), 365–384 | MR | Zbl | Zbl

[2] B. R. McDonald, Finite rings with identity, Dekker, New York, 1974 | MR | Zbl

[3] A. S. Kuzmin, A. A. Nechaev, “Linear recurring sequences over Galois rings”, Algebra and Logic, 34:2 (1995), 87–100 | DOI | MR | Zbl

[4] A. S. Kuzmin, V. L. Kurakin, A. A. Nechaev, “Psevdosluchainye i polilineinye posledovatelnosti”, Trudy po diskretnoi matematike, v. 1, TVP, M., 1997, 139–202 | MR | Zbl

[5] V. L. Kurakin, A. S. Kuzmin, A. V. Mikhalev, A. A. Nechaev, “Linear recurring sequences over rings and modules”, J. Math. Sci., 76:6 (1995), 2793–2915 | DOI | MR | Zbl

[6] A. S. Kuzmin, G. B. Marshalko, A. A. Nechaev, “Vosstanovlenie lineinoi rekurrenty nad primarnym koltsom vychetov po ee uslozhneniyu”, Matem. vopr. kriptogr., 1:2 (2010), 31–56

[7] V. L. Kurakin, “The first coordinate sequence of a linear recurrence of maximal period over a Galois ring”, Discrete Math. Appl., 4:2 (1994), 129–141 | MR | Zbl

[8] D. N. Bylkov, “A class of injective compressing maps on linear recurring sequences over a Galois ring”, Problems Inform. Transmission, 46:3 (2010), 245–252 | DOI | MR | Zbl

[9] O. V. Kamlovskii, “Metod trigonometricheskikh summ dlya issledovaniya chastot $r$-gramm v starshikh koordinatnykh posledovatelnostyakh lineinykh rekurrent nad koltsom $\mathbb{Z}_{2^n}$”, Matem. vopr. kriptogr., 1:4 (2010), 33–62

[10] L. Lathtonen, S. Ling, P. Solé, D. Zinoviev, “$\mathbb{Z}_8$-Kerdock codes and pseudorandom binary sequences”, J. Complexity, 20:2–3 (2004), 318–330 | DOI | MR | Zbl

[11] P. Solé, D. Zinoviev, “The most significant bit of maximum-length sequences over $\mathbb Z_{2^l}$: autocorrelation and imbalance”, IEEE Trans. Inform. Theory, 50:8 (2004), 1844–1846 | DOI | MR

[12] P. Solé, D. Zinoviev, “Distribution of $r$-patterns in the most significant bit of a maximum length sequence over $\mathbb Z_{2^l}$”, Sequences and their applications – SETA 2004 (Seoul, Korea, 2004), Lecture Notes in Comput. Sci., 3486, Springer-Verlag, Berlin, 2005, 275–281 | DOI | Zbl

[13] P. Solé, D. Zinoviev, “Galois rings and pseudo-random sequences”, Cryptography and coding, Lecture Notes in Comput. Sci., 4887, Springer-Verlag, Berlin, 2007, 16–33 | DOI | MR | Zbl

[14] S. Fan, W. Han, “Random properties of the highest level sequences of primitive sequences over $\mathbb Z_{2^e}$”, IEEE Trans. Inform. Theory, 49:6 (2003), 1553–1557 | DOI | MR | Zbl

[15] Z.-D. Dai, D. Ye, P. Wang, G. Fang, “Distribution of $R$-patterns in the highest level of $p$-adic expansion of some linear recursion sequences over Galois rings”, Mathematical properties of sequences and other combinatorial structures (Los Angeles, CA, USA, 2002), Kluwer Acad. Publ., Dordrecht, 2003, 77–83 | MR | Zbl

[16] H. Hu, D. Feng, W. Wu, “Incomplete exponential sums over galois rings with applications to some binary sequences derived from $\mathbb Z_{2^l}$”, IEEE Trans. Inform. Theory, 52:5 (2006), 2260–2265 | DOI | MR

[17] W. Qi, J. Zhou, “Distribution of 0 and 1 in the highest level of primitive sequences over $\mathbb Z_{2^e}$”, Sci. China Ser. A, 40:6 (1997), 606–611 | DOI | MR | Zbl

[18] Q. X. Zheng, W. F. Qi, “Distribution properties of compressing sequences derived from primitive sequences over $\mathbb{Z}_{p^e}$”, IEEE Trans. Inform. Theory, 56:1 (2010), 555–563 | DOI | MR

[19] O. V. Kamlovskii, “Frequency characteristics of linear recurrence sequences over Galois rings”, Sb. Math., 200:4 (2009), 499–519 | DOI | DOI | MR | Zbl

[20] N. M. Korobov, “Raspredelenie nevychetov i pervoobraznykh kornei v rekurrentnykh ryadakh”, Dokl. AN SSSR, 88:4 (1953), 603–606 | MR | Zbl

[21] N. M. Korobov, Trigonometricheskie summy i ikh prilozheniya, Nauka, M., 1989 | MR | Zbl

[22] A. S. Kuz'min, “The distribution of elements on cycles of linear recurrents over rings of residues”, Russian Math. Surveys, 47:6 (1992), 219–221 | DOI | MR | Zbl

[23] A. A. Nechaev, “Cycle types of linear substitutions over finite commutative rings”, Russian Acad. Sci. Sb. Math., 78:2 (1994), 283–311 | DOI | MR | Zbl

[24] M. M. Glukhov, V. P. Elizarov, A. A. Nechaev, Algebra: uchebnik, v. 2, Gelios ARV, M., 2003

[25] T. Cochran, “On a trigonometric inequality of Vinogradov”, J. Number Theory, 27:1 (1987), 9–16 | DOI | MR | Zbl

[26] V. I. Solodovnikov, “Bent functions from a finite abelian group into a finite abelian group”, Discrete Math. Appl., 12:2 (2002), 111–126 | DOI | MR | Zbl

[27] G. M. Fikhtengol'ts, Differential- und Integralrechnung, v. II, VEB, Berlin, 1986 | MR | Zbl | Zbl