Вестник Бурятского государственного университета
Математика, информатика
АвторизацияРУСENG

Вестник БГУ. Математика, информатика

Библиографическое описание:
Меженная Н. М.
О КРИТЕРИИ ПРОВЕРКИ ВЛОЖЕНИЯ С ДОПУСКОМ ДЛЯ ДИСКРЕТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ // Вестник БГУ. Математика, информатика. - 2018. №4. . - С. 3-15.
Заглавие:
О КРИТЕРИИ ПРОВЕРКИ ВЛОЖЕНИЯ С ДОПУСКОМ ДЛЯ ДИСКРЕТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Финансирование:
Коды:
DOI: 10.18101/2304-5728-2018-4-3-15УДК: 519.244.2, 519.244.8
Аннотация:
Последовательность Х является подпоследовательностью с допуском d последовательности У, если Х получается из У удалением несмежных отрезков не более чем из d знаков. В этом случае говорят, что Х может быть вложена в У с допуском d. В работе предложен последовательный критерий проверки гипотезы о вложении с допуском d для дискретных случайных последовательностей над конечным алфавитом и изучены его свойства. Вероятность ошибки первого рода (вероятность отклонения верной гипотезы о вложении с допуском) построенного критерия равна нулю. Получено выражение для вероятности ошибки второго рода при альтернативной гипотезе о том, что рассматриваемые дискретные последовательности образованы независимыми в совокупности случайными величинами с равномерными распределениями на конечном алфавите. Найдено значение среднего числа знаков вкладываемой последовательности, используемых критерием до принятия решения при альтернативной гипотезе. Трудоемкость предложенной процедуры при верной гипотезе о плотном вложении пропорциональна длине вкладываемой последовательности или меньше при альтернативной гипотезе, что по порядку намного меньше трудоемкости тотального опробования. Приведены численные значения вероятности ошибки второго рода и среднего количества используемых знаков при различных значениях d и размерах алфавита.
Ключевые слова:
плотное вложение; вложение с допуском; последовательный критерий; гипотеза о независимости; вероятности ошибок первого и второго рода; дискретная случайная последовательность.
Список литературы:
Golic J. Dj. Constrained embedding probaЬility for two Ьinary strings // SIAМ

J. Discrete Math. 1996. V. 9, № 3. Р. 360-364. DOI: 10. l 137/S0895479894246917

Михайлов В. Г., Меженная Н. М. Оценки для вероятности плотного вложения одной дискретной последовательности в друrую // Дискретная математика. 2005. Т. 17, № 3. С. 19-27. DOI: 10.4213/dml 13

Меженная Н. М., Михайлов В. Г. Нижние оценки для вероятности вложения с произвольным допуском // Вестник Московского государственного технического университета им. Н. Э. Баумана. Сер. Естественные науки. 2012. № 2. С. 3-11.

Donovan D. М., Lefevre J., Simpson L. А Discussion of constrained Ьinary embeddings with applications to cryptanalysis of irregularly clocked stream ciphers // Balakrishnan R., Veni Madhavan С. (Eds.) Discrete mathematics. Proceedings of the intemational conference on discrete mathematics. Bangalore: Indian lnstitute of Sci­ ence, 2006. Р. 73-86.

Golic J. Dj. Embedding probaЬilities for the altemating step generator // IEEE Trans. Inform. Theory. 2005. V. 51(7). Р. 2543-2553. DOI: 10.1109/ТIТ.2005.850114

Annknecht F., Мikhalev V. On lightweight stream ciphers with shorter intemal states // Leander G. (Ed.) Fast Software Encryption. Proceedings of 22nd lntemational Workshop, FSE 2015. lstanbul: Springer-Verlag, 2015. Р. 451-470. DOI: 10.1007/978- 3-662-48116-5 22

Asimi У., Amghar А , Asimi А , Sadqi У. New random generator ofa safe cryp­ tographic salt per session // lnt. J. Netw. Secur. 2016. V. 18, № 3. Р. 445-453.

El-Razouk Н., Reyhani-Masoleh А , Gong G. New implementations of the WG stream cipher // IEEE Transactions on Very Large Scale lntegration (VLSI) Systems. 2014. V. 22, № 9. Р. 1865-1878. DOI: 10. l 109/ТVLSI.2013.2280092

Ма W., Feng D. Clock-controlled key-stream generator and its cryptographic properties // Front. Electr. Electron. Eng. China. 2008. Vol. 3, № 3. Р. 327-332. DOI: 10.1007/sl 1460-008-0014-6

Jiang S., Tang Z., Wang М. On the CLD attack to а statistical model of а key stream generator // lnt. J. Netw. Secur. 2016. Vol. 18, № 5. Р. 987-992.

Deepthi Р. Р., Deepa S. J., Sathidevi Р. S. Design and analysis ofa highly secure stream cipher based on linear feedback shift register // Computer & Electrical Engi­ neering. 2009. V. 35, № 2. Р. 235-243. DOI: 10.1016/j.compeleceng.2008.06.005

Шуваев Д. В. О подпоследовательностях марковских последователь­ ностей // Математические вопросы криптографии. 2016. Т. 7, № 4. С. 133-142. DOI: 10.4213/mvk208

Combinatorial Pattem Matching. Proceedings of СРМ 2013, LNCS 7922 /

J. Fischer, Р. Sanders (Eds.). Bad Herrenalb: Springer-Verlag, 2013. 259 р. DOI: 10.1007/978-3-642-38905-4



Reinert G., Waterman М. S. On the length ofthe longest exact position match in а random sequence // IEEE/ACM transactions on computational Ьiology and Ьioinfor­ matics. 2007. V. 4, № 1. Р. 153-156. DOI: 10.1109/ТСВВ.2007.1023

Сапаров А. Ю., Бельтюков А П. Применение регулярных выражений в распознавании математических текстов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2012. Вып. 2. С. 63-73. DOI: 10.20537/vml 20206

Ивченко Г. И., Медведев Ю. И. Введение в математическую статистику.

М.: Изд-во ЛКИ, 2010. 600 с.

Меженная Н. М. О проверке гипотезы о плотном вложении для дискретных случайных последовательностей // Вестник БГУ. Математика, информатика. 2017. № 4. С. 9-20. DOI: 10.18101/2304-5728-2017-4-9-20

Меженная Н. М. Проверка гипотезы о вложении с допуском для дискретных случайных последовательностей // Прикладная дискретная математика. Приложение. 2018. Т. 11. С. 12-14. DOI: 10.17223/2226308Х/11/3

Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. 2-е изд. М.: Либроком, 2010. Т. 1. 527 с.

Феллер В. Введение в теорию вероятностей и ее приложения: в 2 т. 2-е изд. М.: Либроком, 2010. Т. 2. 751 с.

Прохоров Ю. И., Пономаренко Л. С. Лекции по теории вероятностей и математической статистике. 2-е изд. М.: Изд-во Моск. ун-та, 2012. 256 с.

Рогозин Б. А. Замечание к одной теореме В. Феллера // Теория вероятностей и ее применения. 1969. Т. 14, № 3. С. 554-555. DOI: 10.1137/1114070

Могульский А. А., Рогозин Б. А. Локальная теорема для момента достижения фиксированного уровня случайным блужданием // Математические труды. 2005. Т. 8, № 1. С. 43-70.