Загальне рішення лінійних діофантових рівнянь на основі модульних перетворень для оцінювання ризиків інформаційної безпеки

Степан Дмитрович Винничук, Володимир Володимирович Мохор, Віталій Михайлович Безштанько

Анотація


Запропоновано строго формалізовані алгоритми вирішення лінійних діофантових рівнянь (ЛДР) довільного порядку, засновані на використанні модульних перетворень для визначення кількісних значень ризиків інформаційної безпеки. На кожному кроці алгоритмів, що пропонуються, замість одного первинного ЛДР формується два, перше з яких використовується на зворотному ході алгоритму, а друге - для подальшого зменшення коефіцієнтів при змінних аж до отримання одного з коефіцієнтів, рівного одиниці. У другому рівнянні коефіцієнтами при невідомих є залишками від ділення всіх коефіцієнтів первинного рівняння на мінімальний коефіцієнт цього ЛДР. За рахунок цього, відбувається одночасне зменшення значень коефіцієнтів при всіх змінних, замість одного з них, як це здійснюється в методах заміни змінних. Це забезпечує зменшення обчислювальної складності алгоритмів та значень коефіцієнтів в загальному рішенні рівнянь. Визначена часова складність T(n), де n – число невідомих в рівнянні. Для алгоритму А1 показано, що T1(n)= O(n*m*log2M), де M – максимальне значення коефіцієнта в рівнянні, а m – середня трудомісткість однієї операції ділення із залишком. Для алгоритму А2 гранична асимптотична оцінка M є величиною порядку O(n*lognM*m).


Ключові слова


Лінійні діофантові рівняння з довільним числом невідомих; загальне рішення; формалізовані алгоритми; модульні перетворення

Посилання


Боревич З.И. Теория чисел. / З.И. Боревич. И.Р. Шафаревич // М.:Наука. Глав. Ред. физ.-мат. лит. — 1985. — 504 с.

Схрейвер А. Теория линейного целочисленного программирования. В двух томах. Т.1 / А. Схрейвер // Пер. с анг. – М.: Мир, 1991. — 360 с.

Eisenbeis C , Temam O., WijshofFH. On efficiently characterizing solutions of linear Diophantine equations and its application to data dependence analysis: Research Report / Utrecht University (Netherlands); — RUU-CS-92-01. — 1992. — 22p. [Електронный ресурс] – Режим доступа: https://hal.inria.fr/inria-00074944/PDF/RR-1616.pdf – Дата доступа: январь 2016. – Название с экрана.

Безштанько В. М. Диофантов метод определения частости нанесения ущерба вследствие реализации угроз информационной безопасности / В. М. Безштанько, В. В. Цуркан // Захист інформації. — 2013. — № 4 (15). — с. 278–283.

Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. —328 с.

Серпинский В. О решении уравнений в целых числах./Государственное издательство физико-математической литературы. / Пер. с польського И.Г. Мельникова. — М.: Физматгиз., 1961 — 88 с.

Саати Т.Л. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. — М.: Мир, 1973. — 181 с.


Повний текст: PDF

Посилання

  • Поки немає зовнішніх посилань.


ISSN  2411-071X (Online), ISSN 2225-5036 (Print)

Ліцензія Creative Commons
Цей твір ліцензовано за ліцензією Creative Commons Із зазначенням авторства - Некомерційна - Без похідних творів 3.0 Неадаптована

РИНЦ SSM WorldCat BASE Національна бібліотека ім. Вернадського Науково-технічна бібліотека НАУ Ulrich's Periodicals Directory


Fatal error: require_once(): Failed opening required '/var/www/clients/client1/web1/web/c55bf3fc219b9610c2b8abde2d8ed171/sape.php' (include_path='.:/var/www/clients/client1/web1/web/classes:/var/www/clients/client1/web1/web/pages:/var/www/clients/client1/web1/web/lib/pkp:/var/www/clients/client1/web1/web/lib/pkp/classes:/var/www/clients/client1/web1/web/lib/pkp/pages:/var/www/clients/client1/web1/web/lib/pkp/lib/adodb:/var/www/clients/client1/web1/web/lib/pkp/lib/phputf8:/var/www/clients/client1/web1/web/lib/pkp/lib/pqp/classes:/var/www/clients/client1/web1/web/lib/pkp/lib/smarty:.:/usr/share/pear:/usr/share/php') in /var/www/clients/client1/web1/web/cache/t_compile/%%CC^CCB^CCBBF62B%%footer.tpl.php on line 125