Положим 8 к = 8(х),х е Х к . Набор чисел (|Х0|,...,|Х,|) естественно
назвать спектром расстояний системы (11) относительно решения х0 (по аналогии со спектром расстояний кода, задаваемого соответствующим преобразованием / ) .
Теорема 5.1А
Пусть левая
часть
системы (11)
фиксированное
Р1 = р < 1 / 2 , 1 =
—
спектр
расстояний
системы (11)
относительно истинного решения х0; тогда вероятность того, что метод
максимума правдоподобия дает правильное решение системы (11), удовлетворяет неравенству
р {х*=х°}> 1-=|Х *|р(Л ;),
где
* > 1
р(к) = = С[р‘(1 - р)к < ак, а = т]Ар{\-р)
1>к/2
ДОКАЗАТЕЛЬСТВО. Нетрудно проверить, что
р ^ = х° } > 1 - р й и ^ (х )< $ (х ° )}
к=1хеХ к
> 1 - = |Х к|Р{Зк 5 8 0}.
к=1
Разность 8 к - 50 имеет такое же распределение, как и случайная величина ^ = к - 2( е \+ ^ + е к), поэтому при 0 < р < 1/2
294
Р{5, <5,} =?{*, +л +*, >М = 2 с; р ' (1 ■- р Г =
1>к/2
\1-к/2
С ледствие 5.2.
Если
= ° ( 0 при п , ( —>оо
вероятность правильного решения системы (11) методом максимума правдоподобия стремится к 1:
Дополнительные сведения о тематике случайных систем уравнений читатель может найти в работах:
Балакин Г. В. О распределении числа решений систем случайных булевых уравнений. - Теория вероятн. и ее примен., 1973, т XVIII, в. 3, с. 627632.
Коваленко И. Н., Левитская А. А., Савчук М. Н. Избранные задачи вероятностной комбинаторики. Киев: Наукова думка, 1986, 224 с.
Ва1акш О. V. Оп 1Ье питЬег оГзо1иПопз оГзуз^етз о?рзеи(1о-Ьоо1еап гапбош е^иа^^оп8. - В сб.: Вероятностные методы дискретной математики. Труды третьей Петроза-водской конференции / Под ред. В. Ф. Колчина и др. Москва/Утрехт: ТВП/У8Р, 1993, с. 71-98.
Параграф 5.6 Аналитические методы криптоанализа
Имеется достаточно обширная литература по алгоритмам решения сис тем уравнений в разнообразных алгебраических структурах. В учебных целях мы сосредоточимся на алгоритмах решения систем линейных и нелинейных уравнений над полем Р2, состоящим из двух элементов.
Линейные системы.
Пусть система линейных уравнений над полем Р2 имеет вид ацХ1+а12Х2+....+а1Пхп=Ь1 а21Х,+а22Х2+ ....+а2пхп=Ь2
ат 1Х1+ат2х2+ ... .+атпх„ Ът
295
а^бР2,Ь]€ Рг,Ле 1,ш, 1е 1,п.
Положим,
а и ...............
1
X
II
/'и Л
Ъ 1
, ь=
а т\
• • •
а ,пп
КХ п )
Тогда рассматриваемая система принимает вид А х = Ь .
Метод Гаусса, Как известно из курса линейной алгебры, данный метод основан на по
следовательном исключении неизвестных в уравнениях системы. В терминах матриц исключение неизвестных равносильно выполнению операций сложения в поле Р2 строк матрицы А. Например, пусть первые два уравнения системы имеют вид
Х1+а12х2+....+а1Пх„=Ь1 х,+а22х2+ ... .+а2пх„=Ь2
Выражая XI из первого уравнения (операция + в поле Р2) и, подставляя его во второе уравнение, получаем уравнение
(аи +а22)х2+ • • ■-+(а1„+а2п)хп=Ъ,+Ь2,
исключив таким образом неизвестное X]. Такое преобразование соответствует . замене в матрице
а п ..... ....... а 1п Ь1
а т1
второй строки на сумму первой и второй строк.
Определим следующие элементарные преобразования над матрицами:
1)прибавление одной строки матрицы к другой строке;
2)перестановка строк матрицы;
3)перестановка столбцов.
Отметим, что при перестановке строк матрицы (А, Ь ) система уравне ний не изменится, а при перестановке столбцов матрицы А произойдет перену мерация неизвестных.
Как известно, метод Гаусса заключается в следующем. На первом шаге
матрица (А, Ь) преобразуется в матрицу (А1, Ь ’), у которой первый столбец совпадает с первым столбцом единичной матрицы. Для этого необходимо най-
296
ти строку, в которой первый элемент равен единице (если такой нет, то надо переставить столбцы) и прибавить ее к другим строкам, содержащим единицу в первом столбце. На втором шаге выполняется это же преобразование над под
матрицей матрицы (А',Ь ‘), полученной удалением первой строки и первого столбца. Продолжая этот процесс, матрицу приводят к виду
/ 1 2 . . .
к к+1 . . .п п+1 \
1
*
*
1
О
Теперь система уравнений А' х = Ь ' (имеет то же множество решений, что и исходная, возможно с измененным порядком нумерации переменных). Если некоторые из элементов Ь'к+ь...,Ь'т отличны от нуля, то система линей ных уравнений не имеет решений. Если ••=Ь'т=0, то система имеет 2ПК решений. Для их нахождения фиксируют произвольным образом переменные Хк+ь ...,х„ (2П"Кспособов), а затем находят значение переменной хк из к-го урав нения, значение хк.1 из (к-1)-го, и т. д. Так находят все решения исходной сис
темы уравнений.
Подсчитаем трудоемкость этого метода. На первом шаге выполняется не более (п+1)(т-1) операций сложения, на втором - не более п(т-1) и т. д. Сле
довательно, трудоемкость преобразования матрицы (А,Ь) к виду (А', Ь ') оце нивается величиной
0 (п 2т), .п < т,
(п + 2 - у)(/и - у) = > 0 (л 3),. т = п,
0(п т 2),. гп<п,
или иначе
Т1<0((ш1п(т,п))2тах(т,п).
\
При т=п данная оценка принимает вид
297
Т,*2(п+2Ч)(п- й = Ц х;+2 ) - & 2+ 2 |>
3=1
3=о
з=о
з=о
(п - 1)п(2п -1 )
= п(п - 1)(2п + 5) _
п3
6
6
~
3 ‘
Несложно показывается, что для нахождения каждого из решений тре буется не более
операций сложения. Таким образом, поскольку Т2< Т1, общая трудоемкость ме
тода Гаусса оценивается величиной Т|.
ЫЖ-разложение матриц.
Если приходится решать не одну систему линейных уравнений, а много таких систем с одинаковой левой частью и разных правых частях, то исполь зуют зачастую следующую модификацию метода Гаусса.
Сначала заметим, что метод Гаусса фактически заключается в приведе
нии матрицы (А,Ь ) с помощью элементарных операций к верхнетреугольному виду. Каждая из элементарных операций эквивалентна умножению матрицы
(А, Ь) на некоторую матрицу:
1) при 1<3 прибавление 1-й строки к3-й осуществляется умножением слева на
матрицу
1
1
0
.
0
=Ьн
0
1
1
размера тхщ; 2) перестановка 1-й и3-й строк (1<3) эквивалентно умножению слева на матри
цу
1
1
0
1
1
1
1
1...........0
3
размера тхщ.
298
3)перестановка 1-го и )-го столбцов эквивалентна умножению справа на мат
рицу Ку размера (п+1)(п+1).
Выделим особо случай, когда можно ограничиться выполнением только элементарных операций первого типа.
Обозначим через
3 ц
.
• а 1к
а к1
• а кк
главные миноры матрицы А. Справедливы следующие теоремы.
Теорема. Если все главные миноры матрицы А отличны от нуля, то до статочно использовать только операции первого типа.
Доказательство теоремы проводится индукцией по к.
Теорема. Для любой матрицы А размера пхщ с ненулевыми главными ми
норами найдутся невырожденные нижнетреугольная матрица Ь размера пхп и верхнетреугольная матрица И размера пхщ такие, что А=Ы1
Теорема. Невырожденную матрицу А размера пхп можно перестановкой только строк (или только столбцов) перевести в матрицу, у которой все глав ные миноры отличны от нуля.
В качестве следствия из этих теорем можно получить утверждение: всякую
невырожденную матрицу А можно привести к виду А=ШК=КХ'ЕГ, где К.,К.' - подстановочные матрицы, а Ь,Ь' и 1ДГ, соответственно, нижние и верхние треугольные матрицы. На основании этого утверждения доказывается, что раз ложение матрицы А, указанное выше, находится за 0(п3) операций, а после то го как оно найдено, решение каждой системы (со своей правой частью) нахо дится за 0(п2) операций.
Метод И.В. Коновальцева.
Изложение данного метода мы проведем на основе работы И.В. Коно вальцева «Об одном алгоритме решения систем линейных уравнений в конеч ных полях», Проблемы кибернетики, вып. 19, 1967 г.
Итак, задача состоит в нахождении решений системы линейных урав
нений
1^1X.. .а]пхп а1>п+1
..аппхп ап>п+1
299
в случае, когда элементы матрицы А данной системы принадлежат конечному полю из я элементов. Алгоритм И.В. Коновальцева состоит в следующем.
Первые г элементов 1-той строки матрицы А назовем кортежем С].
Перебирая последовательно строки матрицы А, находят первый кортеж С,отличный от (0,0,.. .,0), и ставят его на первое место. В полученной матрице сравнивают кортеж С]^(0,0,...,0) с кортежем С2. Если С1=С2, то вычитают из
второй строки первую, после чего кортеж второй строки станет нулевым. Если С,*С2, то сравнивают С, с Сз и поступают аналогично предыдущему. На по следнем этапе сравнивают кортежи С1 и С„ и выполняют соответствующие
операции. Отметим, что в полученной матрице кортеж С]^(0,0,...,0) и среди кортежей С2,...,С„ нет равных С1. Рассматривают строки 2,.. .,п полученной
матрицы, находят первый ненулевой кортеж, меняют его местами с кортежем С2 (переставляя соответствующие строки) и повторяют процедуру, описанную выше. Если число различных ненулевых кортежей равно V, то после V шагов матрица А системы линейных уравнений принимает вид
* Л
А=
0 А'
гдематрица А' имеет V строк и г столбцов. Алгоритмом Гаусса приводят мат рицу А' к верхнетреугольному виду. В случае, когда определитель матрицы А отличен от нуля полученная матрица принимает вид
0
1
0
А П - Г /
Если же на этом этапе выяснится, что с1е1А=0, то процесс заканчивается. Этот этап применяется 1 раз, где 1 выбирается исходя из условий
Яг<п-(1-1)г,
но
Яг> п -й \
В результате матрица А принимает вид
300
Ап-1г /
Преобразование подматрицы Ап.№к треугольному виду осуществляется ме тодом Гаусса. В результате матрица А преобразуется в матрицу треугольного вида с единичными элементами на главной диагонали (если <1е1А*0). Затем ре шается система линейных уравнений с треугольной матрицей коэффициентов. В цитированной выше работе И.В. Коновальцева доказывается, что число всех операций (арифметических и вспомогательных) данного алгоритма не превос ходит величины
.3
о( п' )•
1 ° § а
1 1
В заключение отметим, что для уравнений с невырожденной матрицей
Штрассеном был предложен алгоритм со сложностью 0 ( п1о§27 ) операций. По нижение оценки сложности в нем достигнуто благодаря использованию памяти ЭВМ.
Методы решения систем нелинейных уравнений
Метод решения системы нелинейных уравнений над полем Р2, ос нованный на приведении ее к трапецеидальному виду.
Приведем сначала метод решения системы нелинейных уравнений, уже имеющий трапецеидальный вид:
Г,(х(1),... ,х0 0)=у 1
Г2(х ( 1) , . . . , х 0 г ))= У 2
!т.1(х(1),...,хОт.1))=ут.1
Гт(х(1),...,х(п))=ут, где 1<)1<)2<...^]’т-1<п. Такую систему уравнений называют системой трапе
цеидального вида. Решают эту систему уравнений следующим образом.
Опробованием 2 ^ векторов (х( 1),... ,х(] 1)) е Р % находят все решения
первого уравнения. Затем во второе уравнение подставляют (опробуют) все
