Reconstruction of linear recurrent sequence over prime residue ring from its image

A. S. Kuz'min ; G. B. Marshalko ; A. A. Nechaev

Matematičeskie voprosy kriptografii, Tome 1 (2010) no. 2, pp. 31-56

Résumé

We consider pseudorandom sequences $v$ over $\mathbb Z_p$, $p\ge3$, obtained from a primitive sequence $u$ over integer residue ring $\mathbb Z_{p^n}$ by means of some compressing map. We study sufficient conditions for the reconstruction of $u$ from known $v$ and suggest some methods of such reconstruction. The review of known results is presented also.

Bibliographie

[1] Van der Varden B. L., Algebra, Nauka, M., 1979 | MR | Zbl

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

[3] Kuzmin A. S., Nechaev A. A., “Linear recurrent sequences over Galois rings”, Proceedings 2-nd International Conference on Algebra (Barnaul, 1991), 174

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

[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, TVP, M., 1997, 139–202 | MR

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

[8] Kuzmin A. S., Kurakin V. L., Nechaev A. A., “Svoistva lineinykh i polilineinykh rekurrent nad koltsami Galua (II)”, Obozrenie prikl. i promyshl. matem. Ser. diskret. matem., 7:1 (2000), 5–59

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

[10] Kuzmin A. S., Kurakin V. L., Nechaev A. A., “Vpolne ravnomernye lineinye rekurrenty”, Trudy po diskretnoi matematike, 5, FIZMATLIT, M., 2002, 103–158

[11] Nechaev A. A., “Lineinye rekurrentnye posledovatelnosti nad kommutativnymi koltsami”, Diskret. matem., 3:4 (1991), 107–121 | 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”, UMN, 48:1 (1993), 167–168 | MR

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

[15] Kurakin V. L., “Pervaya koordinatnaya posledovatelnost lineinoi rekurrenty maksimalnogo perioda nad koltsom Galua”, Diskret. matem., 6:2 (1994), 88–100 | MR | Zbl

[16] Kurakin V. L., “Predstavleniya nad polem lineinykh rekurrent maksimalnogo perioda nad koltsom vychetov”, Uspekhi matem. nauk, 49:2 (1994), 157–158 | MR | Zbl

[17] Kurakin V. L., “Polinomialnye preobrazovaniya lineinykh rekurrentnykh posledovatelnostei nad koltsom $\mathbb Z_{p^2}$”, Diskret. matem., 11:2 (1999), 40–65 | MR | Zbl

[18] Kurakin V. L., “Polinomialnye preobrazovaniya lineinykh rekurrentnykh posledovatelnostei nad konechnymi kommutativnymi koltsami”, Diskret. matem., 12:3 (2000), 3–36 | MR | Zbl

[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, Ph.D. Thesis. — Graduate School of USTC, Academia Sinica, Beijing, China, 1988

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

[22] Xuan-Yong Zhu, Weng-Feng Qi, “Compression mappings on primitive sequences over $\mathrm 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. Inf. Theory, 53:8 (2007), 2985 | DOI | MR

[24] Tian Tian, Wen-Feng Qi, “Injectivity of compressing maps on primitive sequences over $\mathbb Z/(p^e)$”, IEEE Trans. Inf. Theory, 53:8 (2007), 2960 | DOI | MR

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

[26] Weng-Feng Qi, Xuan-Yong Zhu, “Compressing maps on primitive sequences over $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 $Z_{2^n}$ and analysis of their derivate sequences, Ph.D. Thesis, Zhengzhou Inform. Eng. Univ., Zhengzhou, China, 1997

[28] Weng-Feng Qi, Jun-Hui Yang, Jin-Jun Zhou, “ML-sequences over rings $Z_{2^n}$”, Lect. Notes Comput. Sci., 1514, 1998, 315–326 | MR