|
DOI: 10.14489/vkit.2018.08.pp.046-056
Лапиков И. И.
ПОЛИЭДРАЛЬНЫЙ МЕТОД ВОССТАНОВЛЕНИЯ ЛИНЕЙНОЙ РЕКУРРЕНТЫ ПО ЕЕ СТАРШЕЙ КООРДИНАТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ
(c. 46-56)
Аннотация. Рассмотрена задача восстановления линейной рекурренты, реализованной линейным регистром сдвига с трехчленным законом обратной связи, по старшей координатной последовательности. Для решения поставленной задачи построен полиэдральный метод, состоящий из двух этапов. На первом этапе на основе последовательности подряд идущих знаков старшего разряда формируется последовательность знаков переноса. На ее основе строится система линейных неравенств с k-значными неизвестными, решение которой осуществляется с помощью адаптивного алгоритма эллипсоидов на втором этапе. Приведены результаты масштабного экспериментального исследования полиэдрального метода, на основе которого получена эмпирическая оценка расстояния единственности, т.е. минимального числа знаков старшей координатной последовательности, необходимых для однозначного восстановления линейной рекурренты.
Ключевые слова: адаптивный алгоритм эллипсоидов; линейные рекуррентные последовательности; старшие разрядные последовательности; трехчленный закон обратной связи; полиэдральный метод; метод эллипсоидов.
Lapikov I. I.
THE POLYHEDRAL METHOD OF LINEAR RECURRENCE RECOVERING BY ITS SENIOR COORDINATE SEQUENCE
(pp. 46-56)
Abstract. The article discusses the recovery problem of linear recurrence implemented by a linear shift register with a trinomial law feedback by its senior coordinate. This type of pseudorandom sequences generators are widely used in the construction of information security systems. The analysis of their working logic is an important part ofensuring information security. In order to solve this problem it is worth applying the polyhedral method taking into consideration, which consist of two stages. At the first stage, on the base of senior coordinate sequence is built sequence of transfer characters, which are used in order to form a system of linear inequalities with the k-valued unknowns. At the second stage, this system of linear inequalities is carried out by ellipsoids adaptive algorithm. At the end of the article it is worth adding that the results of a large-scale experiment on which basis is built the singularity distance empirical estimate is provided.The results obtained in this article allow us to assert the possibility of using the ellipsoids adaptive algorithm in the polyhedral method framework for determining the parameters of the linear shift register as a discrete generator.
Keywords: Ellipsoids adaptive algorithm; Linear recurring sequences; Senior coordinate sequences; Trinomial feedback law; Polyhedral method; Ellipsoids method.
И. И. Лапиков (НКО «Фонд содействия развитию безопасных информационных технологий», Москва, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
I.I. Lapikov (NPO «The Promotion of Safe Information Technologies Development Foundation»,Moscow, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. СПб.: Лань, 2015. 608 c.
2. Linear Recurring Sequences over Rings and Modules / V. L. Kurakin et al. // J. Math. Sci. 1995. V. 76, Is. 6. P. 2793 – 2915.
3. Лапиков И. И., Никонов В. Г. Адаптивный алгоритм решения систем линейных неравенств с k-значными неизвестными // Труды Военнокосмической академии им. А. Ф. Можайского. 2016. № 650. С. 88 – 94.
4. Кузьмин А. С., Куракин В. Л., Нечаев А. А. Псевдослучайные и полилинейные последовательности // Труды по дискретной математике. 1997. Т. 1. С. 139 – 202.
5. Козлитин О. А. О периодических свойствах полилинейных регистров сдвига // Дискретная математика. 2017. Т. 29, № 1. С. 27 – 50.
6. Zheng Q.-X., Qi W.-F., Tian T. On the Distinctness of Modular Reductions of Primitive Sequences over Z/(232−1) // Designs, Codes and Cryptography. 2014. V. 70. P. 359 – 368.
7. Zheng Q.-X., Qi W.-F., Tian T. On the Distinctness of Binary Sequences Derived from Primitive Sequences Modulo Square-Free Odd Integers // IEEE Trans. Inf. Theory. 2013. V. 59, Is. 1. P. 680 – 690.
8. Kumar P. V., Helleseth T. An Expansion for the Coordinates of the Trace Function over Galois Rings // Applicate Algebra in Engineering, Communication and Computing. Springer-Verlag. 1997. P. 353 – 361.
9. Былков Д. Н., Камловский О. В. Параметры булевых функций, построенных с использованием старших координатных последовательностей линейных рекуррент // Математические вопросы криптографии. 2012. Т. 3, № 4. С. 25 – 53.
10. Кузьмин А. С., Нечаев А. А. Восстановление линейной рекурренты максимального периода над кольцом Галуа по ее старшей координатной последовательности // Дискретная математика. 2011. Т. 23, № 2. С. 3 – 31.
11. Былков Д. Н., Нечаев А. А. Алгоритм восстановления ЛРП над кольцом по линейному усложнению ее старшей координатной последовательности // Дискретная математика. 2010. Т. 22, № 4. С. 104 – 120.
12. Qi W.-F. Compressing Maps on Primitive Sequences over Z/2n and Analysis of Their Derivative Sequences. PhD Thesis. Zhengzhou Inform. Eng. Univ., Zhengzhou, China, 1997.
13. Лапиков И. И. О возможности построения пространственно-декомпозиционного алгоритма на базе геометрического распараллеливания адаптивного алгоритма эллипсоидов // Computational Nanotechnology. 2018. Вып. 1. С. 140 – 145.
14. Никонов Н. В., Рыбников К. К. Прикладные задачи, сводящиеся к анализу и решению систем линейных неравенств. Метод разделяющих плоскостей // Вестник МГУЛ «Лесной вестник». 2002. № 2(22). С. 191 – 195.
15. Хачиян Л. Г. Избранные труды. М.: МЦНМО, 2014. 519 с.
1. Gluhov M. M., Elizarov V. P., Nechaev A. A. (2015). Algebra. St. Petersburg: Lan'. [in Russian language]
2. Kurakin V. L. et al. (1995). Linear Recurring Sequences over Rings and Modules. J. Math. Sci, 76, (6), pp. 2793-2915.
3. Lapikov I. I., Nikonov V. G. (2016). Adaptive algorithm for solving systems of linear inequalities with kvalued unknowns. Trudy Voennokosmicheskoy akademii im. A. F. Mozhayskogo, 650, pp. 88-94. [in Russian language]
4. Kuz'min A. S., Kurakin V. L., Nechaev A. A. (1997). Pseudorandom and multilinear sequences. Trudy po diskretnoy matematike, 1, pp. 139-202. [in Russian language]
5. Kozlitin O. A. (2017). On the periodic properties of multilinear shift registers. Diskretnaya matematika, 29(1), pp. 27-50. [in Russian language]
6. Zheng Q.-X., Qi W.-F., Tian T. (2014). On the Distinctness of Modular Reductions of Primitive Sequences over Z/(232−1). Designs, Codes and Cryptography, 70, pp. 359-368.
7. Zheng Q.- X., Qi W.-F., Tian T. (2013). On the Distinctness of Binary Sequences Derived from Primitive Sequences Modulo Square-Free Odd Integers. IEEE Trans. Inf. Theory, 59, pp. 680-690.
8. Kumar P. V., Helleseth T. (1997). An Expansion for the Coordinates of the Trace Function over Galois Rings. Applicate Algebra in Engineering, Communication and Computing. Springer-Verlag, pp. 353-361.
9. Bylkov D. N., Kamlovskiy O. V. (2012). Options Boolean functions constructed using the highest coordinate sequences of linear recurrences. Matematicheskie voprosy kriptografii, 4(3), pp. 25-53. [in Russian language]
10. Kuz'min A. S., Nechaev A. A. (2011). Recovering the linear recurrence of the maximum period over the Galois ring from its highest coordinate sequence. Diskretnaya matematika, 23(2), pp. 3-31. [in Russian language]
11. Bylkov D. N., Nechaev A. A. (2010). The algorithm for reconstructing LRS over a ring by linear complication of its highest coordinate sequence. Diskretnaya matematika, 22(4), pp. 104-120. [in Russian language]
12. Qi W.-F. (1997). Compressing Maps on Primitive Sequences over Z/2n and Analysis of Their Derivative Sequences. PhD Thesis. ZhengzhouInform. Eng. Univ., Zhengzhou, China.
13. Lapikov I. I. (2018). On the possibility of constructing a space-decomposition algorithm based on the geometric parallelization of the adaptive algorithm of ellipsoids. Computational Nanotechnology, (1), pp. 140-145. [in Russian language]
14. Nikonov N. V., Rybnikov K. K. (2002). Applied Problems that reduce to the analysis and solution of systems of linear inequalities. Method of separation planes. Vestnik MGUL «Lesnoy vestnik», 22(2), pp. 191-195. [in Russian language]
15. Hachiyan L. G. (2014). Selected works. Moscow: MTsNMO. [in Russian language]
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2018.08.pp.046-056
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2018.08.pp.046-056
and fill out the form
.
|
Архив номеров
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»