S.N. Zaitsev - Researcher, Center of Special Development of Ministry of Defense of RF (Moscow). E-mail: MrNewman@ya.ru

This paper studies pseudorandom sequences determined as polynomial images of digits of maximal period skew recurrences over Galois ring of odd characteristic. The absence of equivalent states of corresponding pseudorandom generator with some contributions to the digital set and to the polynomial is proved, i.e. the initial state of the generator can be uniquely reconstructed from its output. The corresponding reconstruction algorithms with their complexity are provided.

 

1. Goltvanica M.A., Zajjcev S.N., Nechaev A.A. Skruchennye linejjnye rekurrenty maksimalnogo perioda nad kolcami Galua // Fundam. i prikl. mat. 2011/2012. № 17(3). S. 5−23.
2. Goltvanitsa M.A., Nechaev A.A., Zaitsev S.N. Skew LRS of Maximal Period over Galois Rings // Mat. Vopr. Kriptorg. 2013. № 4(2). S. 59−72.
3. Zaitsev S.N. Description of Maximal Skew Linear Recurrences in Terms of Multipliers // Mat. Vopr. Kriptogr. 2014. № 5(2). S. 57−70.
4. SHennon K. Raboty po teorii informacii i kibernetike: Teorija svjazi v sekretnykh sistemakh. IL. M. 1963.
5. Kuzmin A.S., Nechaev A.A. Linejjnye rekurrentnye posledovatelnosti nad kolcami Galua // Algebra i logika. 1995. № 3(2). S. 169−189.
6. Kurakin V.L., Kuzmin A.S., Mikhalev A.V., Nechaev A.A. Linear recurring sequences over rings and modules // J. Math. Sci. 1995. № 76(6). S. 2793−2915.
7. Kurakin V.L. Funkcija perenosa v pervyjj razrjad v kolce Galua // Diskret. matem. 2012. № 24(2). S. 21−36.
8. Goltvanitsa M.A. Digit sequences of skew linear recurrences of maximal period over Galois rings // Matem. vopr. kriptogr. 2015.№ 6(2). S. 19−27.
9. Nakayama T. On Frobeniuscan Algebras I // Ann. of Math. 1939. № 40. S. 611−633.
10. Kuzmin A.S., Nechaev A.A. Postroenie pomekhoustojjchivykh kodov s ispolzovaniem linejjnykh rekurrent nad kolcami Galua // Uspekhi matematicheskikh nauk. 1992. № 47(5). S. 183−184.
11. Preneel B. Introduction to the Proceedings of the Fast Software Encryption // 1994 Workshop (Ed. BartPreneel) LNCS1008. 1995. S. 1−5.
12. Kuzmin A.S., Nechaev A.A. Vosstanovlenie linejjnojj rekurrenty maksimalnogo perioda nad kolcom Galua po ee starshejj koordinatnojj posledovatelnosti // Diskretnaja matematika. 2011. № 23. S. 3−31.
13. Kuzmin A.S., Marshalko G.B., Nechaev A.A. Vosstanovlenie linejjnojj rekurrenty nad primarnym kolcom vychetov po ee uslozhneniju // Matematicheskie voprosy kriptografii. 2010. № 1(2). S. 31−56.
14. Bylkov D.N., Nechaev A.A. Algoritm vosstanovlenija LRP nad kolcom R = Zpn po linejjnomu uslozhneniju ee starshejj koordinatnojj posledovatelnosti // Diskretnaja matematika. 2010. № 22(4). S. 104−120.
15. Min-Qiang Huang, Zong-Duo Dai Projective maps of linear recurring sequences with maximal p-adic periods // Fibonacci Quart. 1992. № 30(2). S. 139−143.
16. Xuan-Yong Zhu, Wen-Feng Qi Compression mappings on primitive sequences over Zpn // IEEE Trans. Inform. Theory. 2004. № 50(10). S. 2442−2448.
17. Xuan-Yong Zhu, Wen-Feng Qi Further result of compressing maps on primitive sequences modulo odd prime powers // IEEE Trans. Inform. Theory. 2007. № 53(8). S. 2985−2990.
18. Tian Tian, Wen-Feng Qi Injectivity of compressing map on primitive sequences over Zpl // IEEE Trans. Inform. Theory. 2007. № 53(8). S. 2960−2966.
19. Zong-Duo Dai Binary sequences derived from ML-sequences over rings I: periods and minimal polynomials // J. Cryptology. 1992. № 5(4). S. 193−207.
20. Weng-Feng Qi, Xuan-Yong Zhu Compressing maps on primitive sequences over Z2n and its Galois extension // Finite Fields Appl. 2002. № 8(4). S. 570−588.
21. Weng-Feng Qi Compressing maps on primitive sequences over Z2n and analysis of their derivative sequences // PhD Thesis. ZhengzhouInform. Eng. Univ., Zhengzhou. China. 1997.
22. Weng-Feng Qi, Jun-Hui Yang, Jin-Jun Zhou ML-sequences over rings Z2n // Lecture Notes Computer Sci. 1998. № 1514. S. 315−325.