Информационная безопасность



Проверка работоспособности методики - часть 2


В общем случае трансформирование системы линейных уравнений по модулю простого числа имеет в три раза более высокую скорость исполнения. Это обусловлено отсутствием операций умножения рациональных чисел, каждая из которых содержит три операции умножения натуральных чисел (полагаем, что операции переноса и сложения имеют на порядок меньшую вычислительную трудоемкость по сравнению с операцией умножения). Исключение составляют исчисление по модулю 2 и по модулю 3.

Преобразование системы линейных уравнений по модулю 3 на множестве (-1, 0, +1) позволяет исключить из набора выполняемых операций умножение натуральных чисел. Все преобразования будут реализуемы с помощью сложения и арифметического отрицания. Это сокращает вычислительную трудоемкость проверки условия в несколько раз (в зависимости от параметров архитектуры ВС). Преобразование системы линейных уравнений по модулю 2 позволяет достичь еще большего быстродействия. Это достигается за счет возможности обрабатывать строки матрицы R как битовые последовательности, тем самым расходуя на сложение и перестановку строк по одной-двум командам микропроцессора. Перестановка столбцов при этом производится циклическими сдвигами двоичных значений.

Недостатками применения малых значений q при проверке необходимого условия является рост вероятности невыполнения условия при истинности значения критерия. Двумя величинами, критически влияющими на вероятность PFN в подобной ситуации, являются величина q и разность между количеством переменных и количеством условий, их связывающими (n-k). В первом приближении (без учета корреляции между значениями элементов матрицы R) данная зависимость описывается следующим выражением:

22

Кроме того, специфика предметной области обуславливает наличие в начале преобразований в матрице S в подавляющем числе значений (0, -1, +1), так как высокостепенные зависимости между переменными здесь достаточно редки. Это приводит на практике к неприемлемо высокому уровню PFN при (q = 2) даже в случае достаточно больших значений параметра (n-k).


Содержание  Назад  Вперед