Estimating the number of solutions of systems of nonlinear equations with linear recurring arguments by the spectral method

O. V. Kamlovskii

Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 27-43.

Résumé

A general approach is proposed for obtaining estimates of the number of solutions of systems of nonlinear equations. Final estimates are established in the case when the arguments of functions in the system are the signs of linear recurrent sequences over Galois rings.

Détail

Keywords: linear recurrent sequences, system of nonlinear equations, Galois rings, spectral method, cross-correlation coefficients.

Bibliographie

[1] Alferov A.P., Zubov A.Yu., Kuzmin A.S., Cheremushkin A.S., Osnovy kriptografii, Gelios ARV, M., 2001, 480 pp.

[2] Rueppel R.A., Analysis and design of stream ciphers, Springer-Verlag, Belrin, 1986, 244 pp. | MR | Zbl

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

[4] Nechaev V.I., “Raspredelenie znakov v posledovatelnosti pryamougolnykh matrits nad konechnym polem”, Trudy Matem. in-ta im. V.A.Steklova, 218 (1997), 335–342 | MR | Zbl

[5] Niederreiter H., “Distribution properties of feedback shift register sequences”, Probl. Control and Inform. Theory, 15:1 (1986), 19–34 | MR | Zbl

[6] Shparlinskii I.E., “O raspredelenii znachenii rekurrentnykh posledovatelnostei”, Problemy peredachi informatsii, 25:2 (1989), 46–53 | MR

[7] Sidelnikov V.M., “Otsenki dlya chisla $r$-gramm na otrezke lineinoi rekurrentnoi posledovatelnosti”, Diskretnaya matematika, 3:2 (1991), 87–95 ; Sidel'nikov V.M., “Estimates for the number of appearances of elements on an interval of a recurrent sequence over a finite field”, Discrete Math. Appl., 2:5 (1992), 473–481 | DOI | MR

[8] Kamlovskii O.V., “Kolichestvo poyavlenii elementov v vykhodnykh posledovatelnostyakh filtruyuschikh generatorov”, Prikl. diskretnaya matematika, 2013, no. 3(21), 11–25

[9] Kumar P.V., Helleseth T., Calderbank A.R., “An upper bound for Weil exponential sums over Galois rings and applications”, IEEE Trans. Inform. Theory, 41:2 (1995), 456–468 | DOI | MR | Zbl

[10] Shanbhag A.G., Kumar P.V., Helleseth T., “Upper bound for a hybrid sum over Galois rings with applications to aperiodic correlation of some $q$-ary sequences”, IEEE Trans. Inform. Theory, 42:1 (1996), 250–254 | DOI | MR | Zbl

[11] 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

[12] Kamlovskii O.V., “Chastotnye kharakteristiki lineinykh rekurrentnykh posledovatelnostei nad koltsami Galua”, Matem. sb., 200:4 (2009), 31–52 | DOI | MR | Zbl

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

[14] Lahtonen J., Ling S., Sole P., Zinoviev D., “$\mathbb{Z}_8$-Kerdock codes and pseudorandom binary sequences”, J. Complexity, 20:8 (2004), 318–330 | DOI | MR | Zbl

[15] 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 | 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] 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

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

[19] Lidl R., Niederreiter H., “Finite fields”, Encyclopedia of Mathematics and its Applications, 20, Addison-Wesley, 1987, 755 pp. ; Lidl R., Niderraiter G., Konechnye polya, Mir, M., 1988, 822 pp. | MR

[20] Solodovnikov V.I., “Bent-funktsii iz konechnoi abelevoi gruppy v konechnuyu abelevu gruppu”, Diskretnaya matematika, 14:1 (2002), 99–113 | DOI | MR | Zbl

[21] Glukhov M.M., Elizarov V.P., Nechaev A.A., Algebra: Uchebnik. t. 2, Gelios ARV, M., 2003, 416 pp.

[22] Logachev O.A., Salnikov A.A., Yaschenko V.V., Bulevy funktsii v teorii kodirovaniya i kriptologii, MTsNMO, M., 2004, 470 pp. | MR

[23] Golomb S.W., Gong G., “Signal design for good correlation”, New York, 2005, 438 pp. | MR

[24] Nechaev A.A., “Kod Kerdoka v tsiklicheskoi forme”, Diskretnaya matematika, 1:4 (1989), 123–139 ; Nechaev A. A., “Kerdock code in a cyclic form”, Discrete Math. Appl., 1:4 (1991), 365–384 | MR | Zbl | DOI | Zbl

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

[26] Nechaev A.A., “Tsiklovye tipy lineinykh podstanovok nad konechnymi kommutativnymi koltsami”, Matem. sb., 184:3 (1993), 21–56 ; Nechaev A. A., “Cycle types of linear substitutions over finite commutative rings”, Russian Acad. Sci. Sb. Math., 78:2 (1994), 283–311 | MR | Zbl | MR

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