Reconstruction of a~linear recurrence of maximal period over a~Galois ring from its highest coordinate sequence

A. S. Kuzmin ; A. A. Nechaev

Diskretnaya Matematika, Tome 23 (2011) no. 2, pp. 3-31.

Résumé

Let $R=GR(q^n,q^n)$ be a Galois ring of cardinality $q^n$ and characteristic $p^n$, $q=p^r$, $p$ be a prime. We call a subset $K\subset R$ a coordinate set if $0\in K$ and for any $a\in R$ there exists a unique $\varkappa(a)\in K$ such that $a\equiv\varkappa(a)\pmod{pR}$. Let $u$ be a linear recurring sequence of maximal period (MP LRS) over a ring $R$. Then any its term $u(i)$ admits a unique representation in the form $$ u(i)=w_0(i)+pw_1(i)+\dots+p^{n-1}w_{n-1}(i),\qquad w_t(i)\in K,\quad t\in\{0,\dots,n-1\}. $$ We pose the following conjecture: the sequence $u$ can be uniquely reconstructed from the sequence $w_{n-1}$ for any choice of the coordinate set $K$. It is proved that such a reconstruction is possible under some conditions on $K$. In particular, it is possible for any $K$ if $R=\mathbf Z_{p^n}$ and for any Galois ring $R$ if $K$ is a $p$-adic (Teichmüller) coordinate set.

Bibliographie

[1] Berlekemp E., Algebraicheskaya teoriya kodirovaniya, Mir, Moskva, 1971 | MR

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

[3] Kuzmin A. S., Nechaev A. A., “Postroenie pomekhoustoichivykh kodov s ispolzovaniem lineinykh rekurrent nad koltsami Galua”, Uspekhi matematicheskikh nauk, 47:5 (1992), 183–184 | MR | Zbl

[4] Kuzmin A. S., Nechaev A. A., “Linear recurrences over Galois rings”, Trudy 2-i Mezhd. konf. po algebre, Barnaul, 1991

[5] Kuzmin A. S., Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad koltsami Galua”, Algebra i logika, 3:2 (1995), 169–189 | MR

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

[7] Kuzmin A. S., Kurakin V. L., Nechaev A. A., “Svoistva lineinykh i polilineinykh rekurrent nad koltsami Galua”, Trudy po diskretnoi matematike, 2, 1998, 191–222 | MR | Zbl

[8] Kuzmin A. S., Kurakin V. L., Nechaev A. A., “Strukturnye analiticheskie i statisticheskie svoistva lineinykh i polilineinykh rekurrent”, Trudy po diskretnoi matematike, 3, 2000, 155–194

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

[10] Nechaev A. A., “Konechnye koltsa glavnykh idealov”, Matematicheskii sb., 91(133):3 (1973), 350–366 | MR | Zbl

[11] Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad kommutativnymi koltsami”, Diskretnaya matematika, 3:4 (1991), 107–127 | MR | Zbl

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

[13] Kuzmin A. S., Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad koltsami Galua”, Uspekhi matematicheskikh nauk, 48:1 (1993), 167–168 | MR | Zbl

[14] Kuzmin A. S., “Nizhnie otsenki rangov koordinatnykh posledovatelnostei lineinykh rekurrentnykh posledovatelnostei nad primarnymi koltsami vychetov”, Uspekhi matematicheskikh nauk, 48:3 (1993), 193–194 | MR | Zbl

[15] Lidl R., Niderraiter G., Konechnye polya, v. 2, Mir, Moskva, 1988 | Zbl

[16] Nechaev A. A., “Kod Kerdoka v tsiklicheskoi forme”, Diskretnaya matematika, 1:4 (1989), 123–139 | MR | Zbl

[17] Nechaev A. A., “Tsiklovye tipy lineinykh podstanovok nad konechnymi kommutativnymi lokalnymi koltsami”, Matematicheskii sb., 184:3 (1993), 21–56 | MR | Zbl

[18] Laxton R. R., Anderson J. A., “Linear recurrences and maximal length sequences”, Math. Gazette, 56 (1972), 299–309 | DOI | MR

[19] Min-Qiang Huang, Zong-Duo Dai, “Projective maps of linear recurring sequences with maximal $p$-adic periods”, Fibonacci Quart., 30:2 (1992), 139–143 | MR

[20] Min-Qiang Huang, Analysis and cryptologic evaluation for primitive sequences over an integer residue ring, PhD Thesis, Graduate School of USTC, Academia Sinica, Beijing, China, 1988

[21] Xuan-Yong Zhu, Wen-Feng Qi, “Uniqueness of the distribution of zeros of primitive level sequences over $\mathbf Z_{p^n}$”, Finite Fields Appl., 11:1 (2005), 30–44 | DOI | MR | Zbl

[22] Xuan-Yong Zhu, Wen-Feng Qi, “Compression mappings on primitive sequences over $\mathbf Z_{p^n}$”, IEEE Trans. Inform. Theory, 50:10 (2004), 2442–2448 | DOI | MR

[23] Xuan-Yong Zhu, Wen-Feng Qi, “Further result of compressing maps on primitive sequences modulo odd prime powers”, IEEE Trans. Inform. Theory, 53:8 (2007), 2985–2990 | DOI | MR

[24] Tian Tian, Wen-Feng Qi, “Injectivity of compressing map on primitive sequences over $\mathbf Z_{p^l}$”, IEEE Trans. Inform. Theory, 53:8 (2007), 2960–2966 | DOI | MR

[25] Zong-Duo Dai, “Binary sequences derived from ML-sequences over rings I: periods and minimal polynomials”, J. Cryptology, 5:4 (1992), 193–207 | MR | Zbl

[26] Weng-Feng Qi, Xuan-Yong Zhu, “Compressing maps on primitive sequences over $\mathbf Z_{2^n}$ and its Galois extension”, Finite Fields Appl., 8:4 (2002), 570–588 | MR

[27] Weng-Feng Qi, Compressing maps on primitive sequences over $\mathbf Z_{2n}$ and analysis of their derivative sequences, PhD Thesis, Zhengzhou Inform. Eng. Univ., Zhengzhou, China, 1997

[28] Weng-Feng Qi, Jun-Hui Yang, Jin-Jun Zhou, “ML-sequences over rings $\mathbf Z_{2^n}$”, Lecture Notes Computer Sci., 1514, 1998, 315–325