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

A. S. Kuzmin ; G. B. Marshalko

Matematičeskie voprosy kriptografii, Tome 2 (2011) no. 2, pp. 81-93

Résumé

Let $v$ be a pseudorandom sequence over $\mathbb Z_p$, $p\ge3$, obtained from primitive sequence $u$ over the ring $\mathbb Z_{p^n}$ by means of some compressing map. We study conditions on the compressing map under which the period of $v$ is less than the period of the initial sequence $u$.

Bibliographie

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

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

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

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

[5] Kuzmin A. S., Nechaev A. A., “Linear recurrent sequences over Galois rings”, Proc. 2nd Int. Conf. Algebra, Barnaul, 1991

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

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

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

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

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

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

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

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

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

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

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

[17] Kuzmin A. S., “Raspredelenie elementov na tsiklakh lineinykh rekurrent nad koltsami vychetov”, Uspekhi matem. nauk, 47:6 (1992), 213–214 | MR | Zbl

[18] Lidl R., Niderraiter G., Konechnye polya, v. 1, 2, Mir., M., 1988, 824 pp. | Zbl

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

[20] “Min-Qiang Huang, Zong-Duo Dai”, Fibonacchi Quart., 30:2 (1992), 139–143 | MR | Zbl

[21] Min-Qiang Huang, Analysis and cryptologic evaluation for primitive sequences over an integer residue ring, Ph. D. diss., Graduate School of USTC, Acad. Sinica, Beijing, China, 1988

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

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

[24] 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–2990 | DOI | MR

[25] 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–2966 | DOI | MR

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

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

[28] Weng-Feng Qi, Compressing maps on primitive sequences over $Z_{2^n}$ and analysis of their derivate sequences, Ph. D. diss., Zhengzhou Inform. Eng. Univ., Zhengzhou, China, 1997

[29] Weng-Feng Qi, Jun-Hui Yang, Jin-Jun Zhou, “ML-sequences over rings $Z_{2^n}$”, ASIACRYPT' 98, Lect. Notes Comput. Sci., 1514, 1998, 315–325