NAU Harvester System
General solving linear Diophantine equations based on a modular transformation for risk assessment in information security
Наукові журнали Національного Авіаційного Університету
View Archive Info| Field | Value | |
| Title |
General solving linear Diophantine equations based on a modular transformation for risk assessment in information security
Общее решение линейных диофантовых уравнений на основе модульных преобразований для оценивания рисков информационной безопасности Загальне рішення лінійних діофантових рівнянь на основі модульних перетворень для оцінювання ризиків інформаційної безпеки |
|
| Creator |
Винничук, Степан Дмитрович; Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины
Мохор, Володимир Володимирович; Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины, Институт специальной связи и защиты информации НТУ Украины «КПИ» Безштанько, Віталій Михайлович; Институт специальной связи и защиты информации НТУ Украины «КПИ» |
|
| Subject |
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) Информационная безопасность Линейные диофантовые уравнения с произвольным числом неизвестных; общее решение; формализованные алгоритмы; модульные преобразования УДК 004.056.53: 511.528.2(045) Інформаційна безпека Лінійні діофантові рівняння з довільним числом невідомих; загальне рішення; формалізовані алгоритми; модульні перетворення УДК 004.056.53: 511.528.2(045) |
|
| Description |
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).
Предложены строго формализованные алгоритмы решения линейных диофантовых уравнений (ЛДУ) произвольного порядка, основанные на использовании модульных преобразований для определения количественных значений рисков информационной безопасности. На каждом шаге предлагаемых алгоритмов вместо одного первичного ЛДУ формируется два, первое из которых используется на обратном ходе алгоритма, а второе – для дальнейшего уменьшения коэффициентов при переменных вплоть до получения одного из коэффициентов, равного единице. Во втором уравнении коэффициентами при неизвестных являются остатками от деления всех коэффициентов первичного уравнения на минимальный коэффициент этого ЛДУ. За счет этого, происходит одновременное уменьшение значений коэффициентов при всех переменных, вместо одного из них, как это реализуется в методах замены переменных. Это обеспечивает уменьшение вычислительной сложности алгоритмов и значений коэффициентов в общем решении уравнений. Определена временная сложность алгоритмов 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). |
|
| Publisher |
National Aviation University
|
|
| 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
|
|