Cross-correlation coefficients for digit sequences of uniform linear recurrent sequences over the residue ring

O. V. Kamlovskiy

Matematičeskie voprosy kriptografii, Tome 11 (2020) no. 1, pp. 47-62

Résumé

We study the class of sequences over the prime field with $p$ elements formed by the most significant $p$-ary digits of linear recurrent sequences over the residue ring modulo $p^n$. We obtain absolute and nonabsolute bounds for the cross-correlation coefficients of such sequences. This results lead to some sufficient conditions for segments of digit sequences obtained from different initial sequences to be different.

Bibliographie

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

[2] Kuzmin A. S., Kurakin V. L., Nechaev A. A., “Psevdosluchainye i polilineinye posledovatelnosti”, Trudy po diskretnoi matematike, 1 (1997), 139–202 | Zbl

[3] Keipers L., Niderraiter G., Ravnomernoe raspredelenie posledovatelnostei, Nauka, M., 1985, 408 pp.

[4] Larin M. V., “Tranzitivnye polinomialnye preobrazovaniya kolets vychetov”, Diskretnaya matematika, 14:2 (2002), 20–32 | DOI | Zbl

[5] Anashin V. S., “Ravnomerno raspredelennye posledovatelnosti tselykh $p$-adicheskikh chisel”, Diskretnaya matematika, 14:4 (2002), 3–64 | DOI | MR | Zbl

[6] Herendi T., “Uniform distribution of linear recurring sequences modulo prime powers”, Finite Fields and Appl., 10:1 (2004), 1–23 | DOI | MR | Zbl

[7] Knight M. J., Webb W. A., “Uniform distribution of third order linear recurrence sequences”, Acta Arith., 36 (1980), 7–20 | DOI | MR | Zbl

[8] Narkiewicz W., Uniform distribution of sequences of integers in residue classes, Lect. Notes Math., 1087, 1984, 140 pp. | DOI | MR | Zbl

[9] Turnwald G., “Uniform distribution of second-order linear recurring sequences”, Proc. Amer. Math. Soc., 96 (1986), 189–198 | DOI | MR

[10] Kamlovskii O. V., “Raspredelenie $r$-gramm v odnom klasse ravnomernykh posledovatelnostei nad koltsami vychetov”, Problemy peredachi informatsii, 50:1 (2014), 98–115 | MR | Zbl

[11] Kamlovskii O. V., “Ravnomernye posledovatelnosti nad prostymi polyami, postroennye iz odnogo klassa lineinykh rekurrent nad koltsami vychetov”, Problemy peredachi informatsii, 50:2 (2014), 60–76 | MR | Zbl

[12] Kamlovskii O. V., “Chastotnye kharakteristiki razryadnykh posledovatelnostei lineinykh rekurrent nad koltsami Galua”, Izv. RAN. Ser. matem., 77:6 (2013), 71–96 | DOI | MR | Zbl

[13] Sole P., Zinoviev D., “Distribution of $r$-patterns in the most significant bit of a maximum length sequence over $\mathbb{Z}_{2^l}$”, Lect. Notes Comput. Sci., 3486, 2005, 275–281 | DOI | MR

[14] Sole P., Zinoviev D., “The most significant bit of maximum-length sequences over $\mathbb{Z}_{2^l}$: autocorrelation and imbalance”, IEEE Trans. Inf. Theory, 50:8 (2006), 1844–1846 | DOI | MR

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

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

[17] Lidl R., Niderraiter G., Konechnye polya, v. 1, 2, Mir, M., 1988, 822 pp. | MR

[18] Kamlovskii O. V., “Metod V. M. Sidelnikova dlya otsenki chisla znakov na otrezkakh lineinykh rekurrentnykh posledovatelnostei nad koltsami Galua”, Matem. zametki, 91:3 (2012), 371–382 | DOI | MR | Zbl

[19] Kamlovskii O. V., Kuzmin A. S., “Otsenki chastot poyavleniya elementov v lineinykh rekurrentnykh posledovatelnostyakh nad koltsami Galua”, Fundam. i prikl. matematika, 6:4 (2000), 1083–1094 | MR | Zbl