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

Ukrainian Scientific Journal of Information Security

View Publication Info
 
 
Field Value
 
Title Загальне рішення лінійних діофантових рівнянь на основі модульних перетворень для оцінювання ризиків інформаційної безпеки
Общее решение линейных диофантовых уравнений на основе модульных преобразований для оценивания рисков информационной безопасности
General solving linear Diophantine equations based on a modular transformation for risk assessment in information security
 
Creator Винничук, Степан Дмитрович; Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины
Мохор, Володимир Володимирович; Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины, Институт специальной связи и защиты информации НТУ Украины «КПИ»
Безштанько, Віталій Михайлович; Институт специальной связи и защиты информации НТУ Украины «КПИ»
 
Subject Інформаційна безпека
Лінійні діофантові рівняння з довільним числом невідомих; загальне рішення; формалізовані алгоритми; модульні перетворення
УДК 004.056.53: 511.528.2(045)
Информационная безопасность
Линейные диофантовые уравнения с произвольным числом неизвестных; общее решение; формализованные алгоритмы; модульные преобразования
УДК 004.056.53: 511.528.2(045)
Information Security
Linear Diophantine equations with an arbitrary number of unknowns; the general solution; formalized algorithms; modular transformations
UDC 004.056.53: 511.528.2(045)
 
Description Запропоновано строго формалізовані алгоритми вирішення лінійних діофантових рівнянь (ЛДР) довільного порядку, засновані на використанні модульних перетворень для визначення кількісних значень ризиків інформаційної безпеки. На кожному кроці алгоритмів, що пропонуються, замість одного первинного ЛДР формується два, перше з яких використовується на зворотному ході алгоритму, а друге - для подальшого зменшення коефіцієнтів при змінних аж до отримання одного з коефіцієнтів, рівного одиниці. У другому рівнянні коефіцієнтами при невідомих є залишками від ділення всіх коефіцієнтів первинного рівняння на мінімальний коефіцієнт цього ЛДР. За рахунок цього, відбувається одночасне зменшення значень коефіцієнтів при всіх змінних, замість одного з них, як це здійснюється в методах заміни змінних. Це забезпечує зменшення обчислювальної складності алгоритмів та значень коефіцієнтів в загальному рішенні рівнянь. Визначена часова складність T(n), де n – число невідомих в рівнянні. Для алгоритму А1 показано, що T1(n)= O(n*m*log2M), де M – максимальне значення коефіцієнта в рівнянні, а m – середня трудомісткість однієї операції ділення із залишком. Для алгоритму А2 гранична асимптотична оцінка M є величиною порядку O(n*lognM*m).
Предложены строго формализованные алгоритмы решения линейных диофантовых уравнений (ЛДУ) произвольного порядка, основанные на использовании модульных преобразований для определения количественных значений рисков информационной безопасности. На каждом шаге предлагаемых алгоритмов вместо одного первичного ЛДУ формируется два, первое из которых используется на обратном ходе алгоритма, а второе – для дальнейшего уменьшения коэффициентов при переменных вплоть до получения одного из коэффициентов, равного единице. Во втором уравнении коэффициентами при неизвестных являются остатками от деления всех коэффициентов первичного уравнения на минимальный коэффициент этого ЛДУ. За счет этого, происходит одновременное уменьшение значений коэффициентов при всех переменных, вместо одного из них, как это реализуется в методах замены переменных. Это обеспечивает уменьшение вычислительной сложности алгоритмов и значений коэффициентов в общем решении уравнений. Определена временная сложность алгоритмов T(n) , где n – число неизвестных в уравнении. Для алгоритма А1 показано, что T1(n)= O(n*m*log2M), где M – максимальное значение коэффициента уравнения, а m – средняя трудоемкость одной операции деления с остатком. В случае алгоритма А2 предельная асимптотическая оценка при росте M является величиной порядка O(n*lognM*m).
Strictly formalized algorithms for solving linear Diophantine equations (LDE) of arbitrary order based on the use of modular transformations to determine quantitative values of information security risks. At every step of algorithms offered instead of one primary LDE formed two, the first of which is used on the reverse course of the algorithm, and the second - to further reduce the coefficients of the variables, to obtain one of the coefficients equal to unity. In the second equation, the coefficients of the unknowns are the remnants of the division of the primary coefficients of the equation for a minimum coefficient of this LDE. Due to this, there is a simultaneous decrease in the values of the coefficients of all the variables, instead of one of them, as it is implemented in the methods of change of variables. This provides a reduction the computational complexity of the algorithms and the values of the coefficients in the general solution of equations. Determine their time complexity T(n), where n - the number of unknowns in the equation. For algorithm A1 shown, that T1(n)= O(n*m*log2M) , where M – the maximum coefficient in equation, and m –the average labor input of a division operation with the remainder. For algorithm A2 asymptotic limit rating M it is of the order O(n*lognM*m).
 
Publisher Національний авіаційний університет
 
Contributor


 
Date 2016-06-22
 
Type


 
Format application/pdf
 
Identifier http://jrnl.nau.edu.ua/index.php/Infosecurity/article/view/10457
10.18372/2225-5036.22.10457
 
Source Безпека інформації; Том 22, № 1 (2016); 75-83
Безопасность информации; Том 22, № 1 (2016); 75-83
Ukrainian Scientific Journal of Information Security; Том 22, № 1 (2016); 75-83
 
Language uk
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2016 Simon Fraser University Library