С.Н. Зайцев - Центр специальных разработок МО РФ (Москва) E-mail: MrNewman@ya.ru

Изучены псевдослучайные последовательности, полученные путем полиномиального усложнения разрядов скрученных рекуррент максимального периода над кольцами Галуа нечетной характеристики. Показано, что при некоторых ограничениях на разрядное множество и на функции усложнения удается доказать, что соответствующие генераторы не имеют эквивалентных состояний, т.е. начальное состояние однозначно восстанавливается по выходу генератора. Приведены соответствующие алгоритмы восстановления.

 

1. Гольтваница М.А., Зайцев С.Н., Нечаев А.А. Скрученные линейные рекурренты максимального периода над кольцами Галуа // Фундам. и прикл. мат. 2011/2012. № 17(3). С. 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). С. 59−72.
3. Zaitsev S.N. Description of Maximal Skew Linear Recurrences in Terms of Multipliers // Mat. Vopr. Kriptogr. 2014. № 5(2). С. 57−70.
4. Шеннон К. Работы по теории информации и кибернетике: Теория связи в секретных системах. ИЛ. М. 1963.
5. Кузьмин А.С., Нечаев А.А. Линейные рекуррентные последовательности над кольцами Галуа // Алгебра и логика. 1995. № 3(2). С. 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). С. 2793−2915.
7. Куракин В.Л. Функция переноса в первый разряд в кольце Галуа // Дискрет. матем. 2012. № 24(2). С. 21−36.
8. Goltvanitsa M.A. Digit sequences of skew linear recurrences of maximal period over Galois rings // Matem. vopr. kriptogr. 2015.№ 6(2). С. 19−27.
9. Nakayama T. On Frobeniuscan Algebras I // Ann. of Math. 1939. № 40. С. 611−633.
10. Кузьмин А.С., Нечаев А.А. Построение помехоустойчивых кодов с использованием линейных рекуррент над кольцами Галуа // Успехи математических наук. 1992. № 47(5). С. 183−184.
11. Preneel B. Introduction to the Proceedings of the Fast Software Encryption // 1994 Workshop (Ed. BartPreneel) LNCS1008. 1995. С. 1−5.
12. Кузьмин А.С., Нечаев А.А. Восстановление линейной рекурренты максимального периода над кольцом Галуа по ее старшей координатной последовательности // Дискретная математика. 2011. № 23. С. 3−31.
13. Кузьмин А.С., Маршалко Г.Б., Нечаев А.А. Восстановление линейной рекурренты над примарным кольцом вычетов по ее усложнению // Математические вопросы криптографии. 2010. № 1(2). С. 31−56.
14. Былков Д.Н., Нечаев А.А. Алгоритм восстановления ЛРП над кольцом R = Zpn по линейному усложнению ее старшей координатной последовательности // Дискретная математика. 2010. № 22(4). С. 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). С. 139−143.
16. Xuan-Yong Zhu, Wen-Feng Qi Compression mappings on primitive sequences over Zpn // IEEE Trans. Inform. Theory. 2004. № 50(10). С. 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). С. 2985−2990.
18. Tian Tian, Wen-Feng Qi Injectivity of compressing map on primitive sequences over Zpl // IEEE Trans. Inform. Theory. 2007. № 53(8). С. 2960−2966.
19. Zong-Duo Dai Binary sequences derived from ML-sequences over rings I: periods and minimal polynomials // J. Cryptology. 1992. № 5(4). С. 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). С. 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. С. 315−325.