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

Анотація

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