Метод оптимизации алгоритмов решения систем Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ
Предложен метод построения новых алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ по произвольной конечной совокупности исходных таких алгоритмов. Показано, что в ряде случаев предложенный метод позволяет существенно повысить эффективность изве...
Збережено в:
| Дата: | 2005 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2005
|
| Назва видання: | Реєстрація, зберігання і обробка даних |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/50717 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2^N / А.Н. Алексейчук, С.М. Игнатенко // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 1. — С. 11-23. — Бібліогр.: 16 назв. — pос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-50717 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-507172013-10-30T03:05:53Z Метод оптимизации алгоритмов решения систем Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ Алексейчук, А.Н. Игнатенко, С.М. Математичні методи обробки даних Предложен метод построения новых алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ по произвольной конечной совокупности исходных таких алгоритмов. Показано, что в ряде случаев предложенный метод позволяет существенно повысить эффективность известных алгоритмов решения указанных систем уравнений. Запропонованo метод побудови нових алгоритмів розв’язання систем лінійних рівнянь зі спотвореною правою частиною над кільцем лишків за модулем 2ⁿ за довільною скінченою сукупністю вихідних таких алгоритмів. Показано, що в ряді випадків запропонований метод дозволяє суттєво підвищити ефективність відомих алгоритмів розв’язання зазначених систем рівнянь. A method of constructing new algorithms for solving systems of linear equations with a corrupted right part over the residue modulo 2ⁿ ring from arbitrary finite set of original such algorithms is proposed. It is shown that in certain cases the proposed method allows to increase essentially the efficiency of known algorithms for solving mentioned systems of linear equations. 2005 Article Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2^N / А.Н. Алексейчук, С.М. Игнатенко // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 1. — С. 11-23. — Бібліогр.: 16 назв. — pос. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/50717 621.391:519.2 ru Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математичні методи обробки даних Математичні методи обробки даних |
| spellingShingle |
Математичні методи обробки даних Математичні методи обробки даних Алексейчук, А.Н. Игнатенко, С.М. Метод оптимизации алгоритмов решения систем Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ Реєстрація, зберігання і обробка даних |
| description |
Предложен метод построения новых алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ по произвольной конечной совокупности исходных таких алгоритмов. Показано, что в ряде случаев предложенный метод позволяет существенно повысить эффективность известных алгоритмов решения указанных систем уравнений. |
| format |
Article |
| author |
Алексейчук, А.Н. Игнатенко, С.М. |
| author_facet |
Алексейчук, А.Н. Игнатенко, С.М. |
| author_sort |
Алексейчук, А.Н. |
| title |
Метод оптимизации алгоритмов решения систем Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ |
| title_short |
Метод оптимизации алгоритмов решения систем Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ |
| title_full |
Метод оптимизации алгоритмов решения систем Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ |
| title_fullStr |
Метод оптимизации алгоритмов решения систем Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ |
| title_full_unstemmed |
Метод оптимизации алгоритмов решения систем Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ |
| title_sort |
метод оптимизации алгоритмов решения систем метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2ⁿ |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2005 |
| topic_facet |
Математичні методи обробки даних |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/50717 |
| citation_txt |
Метод оптимизации алгоритмов решения систем линейных уравнений с искаженной правой частью над кольцом вычетов по модулю 2^N / А.Н. Алексейчук, С.М. Игнатенко // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 1. — С. 11-23. — Бібліогр.: 16 назв. — pос. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT aleksejčukan metodoptimizaciialgoritmovrešeniâsistemmetodoptimizaciialgoritmovrešeniâsistemlinejnyhuravnenijsiskažennojpravojčastʹûnadkolʹcomvyčetovpomodulû2n AT ignatenkosm metodoptimizaciialgoritmovrešeniâsistemmetodoptimizaciialgoritmovrešeniâsistemlinejnyhuravnenijsiskažennojpravojčastʹûnadkolʹcomvyčetovpomodulû2n |
| first_indexed |
2025-07-04T12:30:28Z |
| last_indexed |
2025-07-04T12:30:28Z |
| _version_ |
1836719515829796864 |
| fulltext |
Математичні методи обробки даних
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 11
УДК 621.391: 519.2
А. Н. Алексейчук1, С. М. Игнатенко2
1Специальный факультет СБ Украины в составе Военного института
телекоммуникаций и информатизации НТУУ «КПИ»
2В/ч А 1906
Метод оптимизации алгоритмов решения систем
линейных уравнений с искаженной правой частью
над кольцом вычетов по модулю 2N
Предложен метод построения новых алгоритмов решения систем ли-
нейных уравнений с искаженной правой частью над кольцом вычетов
по модулю 2N по произвольной конечной совокупности исходных таких
алгоритмов. Показано, что в ряде случаев предложенный метод по-
зволяет существенно повысить эффективность известных алгорит-
мов решения указанных систем уравнений.
Ключевые слова: корреляционный криптоанализ, система линейных
уравнений с искаженной правой частью, оптимизация вычислитель-
ных алгоритмов.
Введение
Одной из актуальных задач современного криптоанализа является разработка
эффективных, с точки зрения надежности и трудоемкости, методов решения сис-
тем линейных уравнений (СЛУ) с искаженной правой частью над конечными
коммутативными кольцами по аналогии с известными методами решения таких
СЛУ над полем из двух элементов [1–3]. К разработке и анализу алгоритмов ре-
шения систем линейных уравнений с искаженной правой частью приводят задачи
корреляционного криптоанализа поточных шифров, декодирования блоковых ко-
дов, восстановления искаженных линейных рекуррентных последовательностей и
ряд других [1, 4–8].
В настоящее время известны два универсальных метода решения СЛУ с ис-
каженной правой частью над кольцом RN = Z/(2N): метод максимума правдоподо-
бия (ММП) [1, 9] и метод последовательного решения N вспомогательных буле-
вых СЛУ с искаженными правыми частями и одинаковыми матрицами коэффици-
ентов [10]. В [11, 12] показано, что при выполнении определенных условий тру-
доемкость ММП можно уменьшить, заменяя процедуру вычисления, так называе-
мых векторов ошибок, вычислением (с использованием «быстрых» алгоритмов
[13]) комплексного преобразования Фурье или, соответственно, числового преоб-
© А. Н. Алексейчук, С. М. Игнатенко
А. Н. Алексейчук, С. М. Игнатенко
12
разования Ферма некоторых вспомогательных функций, заданных на множестве
RN
(n), где n — число неизвестных исходной СЛУ. На практике применение ММП
или указанных его модификаций становится невозможным уже при умеренных
значениях n или N в силу большой временной или емкостной сложности соответ-
ствующих алгоритмов решения СЛУ. С другой стороны, метод последовательно-
го решения булевых СЛУ с искаженными правыми частями [10] часто не позволя-
ет восстанавливать истинное решение системы уравнений с требуемой (высокой)
надежностью.
В настоящей статье предлагается метод построения новых алгоритмов реше-
ния СЛУ с искаженной правой частью над кольцом RN по произвольной конечной
совокупности исходных таких алгоритмов. Метод основывается на идее последо-
вательного решения статистических задач, примененной к решению булевых сис-
тем уравнений с мешающими параметрами Г.В. Балакиным и Ю.Б. Никольским
[2], а также формальном подходе к построению оптимальных по трудоемкости
вычислительных алгоритмов, предложенном М.В. Гаврилкевичем и В.И. Соло-
довниковым [14]. Установлены аналитические выражения оценок надежности и
временной сложности, получаемых по предложенному методу алгоритмов реше-
ния СЛУ с искаженной правой частью через соответствующие характеристики
исходных алгоритмов. Описана процедура построения оптимальных (в опреде-
ленном классе) алгоритмов решения СЛУ с искаженной правой частью над коль-
цом RN.
При N = 5 проведено экспериментальное исследование эффективности алго-
ритмов, получаемых из исходных алгоритмов решения СЛУ с искаженными пра-
выми частями (над различными кольцами вычетов) по методу максимума правдо-
подобия. Полученные результаты свидетельствуют о том, что в большинстве слу-
чаев новые алгоритмы являются более эффективными по сравнению с ранее из-
вестными алгоритмами решения СЛУ с искаженной правой частью над кольцом
RN [1, 9–12].
Определения основных понятий
Для заданных натуральных t и n обозначим ntNR ´)( кольцо матриц размера
t ´ n над кольцом .NR Символом NP обозначим совокупность всех распределений
вероятностей (РВ) на NR . Каждое РВ NN Pp Î представляет собой стохастический
вектор длины 2N с координатами )(apN , где NRaÎ .
Система линейных уравнений с искаженной правой частью над кольцом NR
определяется как упорядоченный набор (A, 0x , b, Np ), где ntNRA ´Î )( , )(
0
n
NRx Î
— неизвестный вектор длины n над кольцом NR , NN Pp Î , e 0 += Axb , e —
случайный вектор с независимыми в совокупности координатами, распределен-
ными на множестве NR по закону Np [1, 9].
Под алгоритмом решения СЛУ с искаженной правой частью над кольцом NR
будем понимать произвольную частичную вычислимую функцию Ã, заданную на
некотором подмножестве множества всех упорядоченных наборов (A, b, Np ), та-
Метод оптимизации алгоритмов решения систем линейных
уравнений с искаженной правой частью над кольцом вычетов по модулю 2N
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 13
ких, что ntNRA ´Î )( , NN Pp Î , e 0 += Axb , и ставящую в соответствие каждому
указанному набору некоторый вектор )(
0* n
NRx Î — оценку истинного решения
0x СЛУ:
e 0 +== AxbAx . (1)
Запись ),,(*0 NpbAx Ã= означает, что вектор *0x есть результат применения ал-
горитма Ã к входным данным ÃÎ DpbA N ),,( , где ÃD — область определения
функции Ã.
Обозначим LN класс всех алгоритмов решения систем линейных уравнений с
искаженной правой частью над кольцом NR . Символами
),,,( 0 NpxAÃÃ = pp ),,,( NptnNTT ÃÃ =
будем обозначать соответственно функции надежности и трудоемкости алгоритма
ÃÎLN.
Надежность алгоритма Ã определяется по формуле:
}), ,(Pr{ 0xpbA N =Ã=Ãp , (2)
где вероятность в правой части равенства (2) определяется относительно закона
распределения Np координат случайного вектора e . Отметим, что заданная та-
ким образом надежность зависит от матрицы ntNRA ´Î )( и вектора )(
0
n
NRx Î .
Можно определить среднюю надежность Ãp алгоритма Ã, положив
Ãp = }),,({Pr2 0
)(
xpbA N
RA
Ntn
ntN
=Ãå
´Î
- .
Наконец, можно усреднить значения (2) по всем ntNRA ´Î )( , )(
0
n
NRx Î и полу-
чить таким образом среднюю надежность алгоритма Ã решения СЛУ (1), которая
формируется путем случайного равновероятного, не зависящего от вектора e вы-
бора истинного решения и матрицы коэффициентов.
Трудоемкость ÃT алгоритма ÃÎLN определим как битовую временную слож-
ность (в худшем случае, при равномерном весовом критерии) этого алгоритма,
рассматривая в качестве модели вычислительного устройства, на котором реали-
зуются алгоритмы, равнодоступную адресную машину [15].
А. Н. Алексейчук, С. М. Игнатенко
14
Метод построения новых алгоритмов решения систем линейных
уравнений с искаженной правой частью над кольцом RN
Пусть заданы произвольные натуральные числа N1, N2. Положим N = N1 + N2
и определим отображение
,:
2121, NNNNN L®L´Lq (3)
ставящее в соответствие каждой упорядоченной паре ),( 21 ÃÃ алгоритмов реше-
ния систем линейных уравнений с искаженными правыми частями над кольцами
21
, NN RR соответственно новый алгоритм:
),,( 21, 21
ÃÃq=Ã NN ÃÎLN. (4)
Дадим точное определение алгоритма (4). Предварительно введем ряд обо-
значений.
Отождествим элементы кольца NR с N-мерными двоичными векторами, по-
лагая
),,,...,(2 011
1
0
rrrrr N
N
i
i
i
-
-
=
==å },1,0{ Îir 1,0 -Î Ni .
Для заданных N1, N2 определим отображения :, 10 dd NR ® NR по формулам:
),,...,,0,...,0()( 010 1
rrr N -=d ),,...,,0,...,0()(
111 NN rrr -=d
(5)
NN Rrrrr Î= - ),,...,( 011 .
На основании (5) имеем:
)(2)( 10
1 rrr N dd += , NRr Î . (6)
Считая, что множества
21
, NN RR канонически вложены во множество NR ,
можно записать:
,)(
10 NRr Îd .)(
21 NRr Îd (7)
Отметим, что соотношения (6), (7) однозначно определяют функции 10 , dd в
следующем смысле: для любых
21 10 , NN RaRa ÎÎ таких, что 10
12 aar N+= , име-
ют место равенства )(00 ra d= , )(11 ra d= . Это свойство функций 10 , dd будет ис-
пользовано ниже.
Метод оптимизации алгоритмов решения систем линейных
уравнений с искаженной правой частью над кольцом вычетов по модулю 2N
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 15
Для любой матрицы |||| mnuU = над кольцом NR положим по определению
||)(|| )( 00 mndd uU = , ||)(|| )( 11 mndd uU = . Очевидно равенство )(2)( 10
1 UUU N dd += .
Перейдем к определению алгоритма ),( 21, 21
ÃÃq=Ã NN . Рассмотрим СЛУ (1)
над кольцом NR . Для решения этой СЛУ с помощью определяемого алгоритма
Ã, прежде всего, построим систему линейных уравнений с искаженной правой
частью над кольцом
1NR следующего вида:
=d=d )()( 00 byA )()()( 0000 eddd +xA . (8)
Отметим, что закон распределения
1Np
def
= )(0 Npd координат случайного век-
тора )(0 ed определяется по формуле:
=- ),...,( 0111
aap NN å
Î
--
- 211
11
),...,(
011 ),...,,,...,(
NNN Ruu
NNNN aauup ,
11
),...,( 01 NN Raa Î- .
Если упорядоченный набор ) ),( ),((
100 NpbA dd принадлежит области опреде-
ления
1ÃD алгоритма 1Ã (то есть СЛУ (8) может быть решена с помощью этого
алгоритма), то, решая ее, получим оценку
)),(),((*
10011,0 NpbAx ddÃ= (9)
вектора )( 00
def
1,0 xx d= .
Итак, на первом шаге алгоритма Ã вида (4) осуществляется построение СЛУ
(8), проверка условия
11
)),(),(( 00 ÃÎDpbA Ndd (10)
и вычисление оценки истинного решения 1,0x СЛУ (8) по формуле (9).
На втором шаге алгоритма Ã по системе уравнений (1) и вектору (9) состав-
ляется СЛУ над кольцом
2NR следующего вида:
*) *()( 11,0112 edd +-= AxbzA , (11)
где )2mod( 2
2
NAA = ,
*)(* 1,001 Axb -= de . (12)
А. Н. Алексейчук, С. М. Игнатенко
16
Отметим, что в общем случае СЛУ (11) не является системой уравнений с ис-
каженной правой частью. Тем не менее, справедливо следующее утверждение.
Утверждение 1. При выполнении равенства
1,01,0 * xx = (13)
СЛУ (11) является системой линейных уравнений с искаженной правой частью
над кольцом
2NR , имеет истинное решение )( 01
def
2,0 xx d= и определяется упорядо-
ченным набором ),,,(
22,02 NpdxA , где вектор *) *()( 11,011
def
edd +-= Axbd удовле-
творяет равенству над кольцом
2NR
22,02 e+= xAd , (14)
а закон распределения случайного вектора )( 1
def
2 ede = определяется по формуле:
=- ),...,( 0122
aap NN å
Î
--
- 1011
12
),...,(
0101 ),...,,,...,(
NN Ruu
NNN uuaap ,
22
),...,( 01 NN Raa Î- .
Доказательство. Достаточно показать, что при выполнении соотношений
(1), (13) имеет место равенство (14).
Согласно определению вектора d и равенства (12), при выполнении (13) спра-
ведливо следующее равенство над кольцом
2NR :
))( *( )( 01,011 eddd +-= Axbd . (15)
С другой стороны, на основании (1)
=+++=+= )(2)()2( 102,01,00
11 edede NN xxAAxb
++=+++= ))(())((2)( 01,0012,001,0
1 eddeded AxAxAx N
+ )))(()((2 01,0112,0
1 edded +++ AxAxN ,
откуда согласно отмеченному выше свойству функций 10 ,dd , вытекает равенство:
)2(mod ))(()()( 2
01,0112,01
NAxAxb eddedd +++º . (16)
Из (15), (16) находим, что )2(mod )( 2
12,0
NAxd ed+º , то есть над кольцом
2NR выполняется равенство (14), что и требовалось доказать.
Метод оптимизации алгоритмов решения систем линейных
уравнений с искаженной правой частью над кольцом вычетов по модулю 2N
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 17
Полученное утверждение показывает, что в случае, когда оценка (9) истинно-
го решения 1,0x СЛУ (8) совпадает с этим решением, СЛУ (11) представляет со-
бой систему уравнений с искаженной правой частью над кольцом .
2NR Эта систе-
ма уравнений определяется набором ),,,(
21,02 NpdxA , заданным в формулировке
утверждения 1.
Итак, на основании вышеизложенного, второй шаг алгоритма Ã описывается
следующим образом. Вначале строится СЛУ (11), которая интерпретируется как
система уравнений с искаженной правой частью над кольцом .
2NR Затем прове-
ряется условие:
22
),,( 2 ÃÎ DpdA N . (17)
Если соотношение (17) выполняется, то СЛУ (11) решается с помощью алго-
ритма 2Ã , то есть вычисляется оценка
),,(*
2222,0 NpdAx Ã= (18)
истинного решения 2,0x СЛУ с искаженной правой частью
22,022 e+== xAdzA (19)
над кольцом
2NR .
Наконец, на третьем шаге алгоритма Ã вычисляется оценка ),,(*0 NpbAx Ã=
истинного решения СЛУ (1), которая находится по формуле:
*2** 2,01,00
1 xxx N += .
Отметим, что в соответствии с приведенным описанием алгоритма Ã его об-
ласть определения ÃD состоит из тех и только тех упорядоченных наборов
),,( NpbA , для которых выполняются условия (10) и (17). Таким образом, отобра-
жение
21, NNq вида (3) корректно определено.
Приведем аналитические выражения оценок надежности и трудоемкости ал-
горитма ),( 21, 21
ÃÃq=Ã NN через соответствующие характеристики алгоритмов
1Ã и 2Ã .
Утверждение 2. Пусть ),,,( 0 NpbxA — СЛУ вида (1) над кольцом NR , и
пусть ÃÎ DpbA N ),,( , где алгоритм Ã определяется равенством (4). Обозначим
),,),((
111 1,00 NpxAdpp ÃÃ = ),,(
222 2,02 NpxAÃÃ = pp
А. Н. Алексейчук, С. М. Игнатенко
18
значения функций надежности и трудоемкости алгоритмов 1Ã , 2Ã соответствен-
но (от аргументов ),),((
11,00 NpxAd и ),,(
22,02 NpxA , определяемых системами ли-
нейных уравнений с искаженными правыми частями (8) и (19) соответственно).
Положим ),,( 0 NpxAÃÃ = pp . Тогда справедливы неравенства:
},min{1
2121 ÃÃÃÃÃ ££-+ ppppp . (20)
Кроме того, если случайные векторы )(01 ede = и )(12 ede = независимы, то
21 ÃÃÃ = ppp . (21)
Доказательство. Рассмотрим события 1U и 2 ,U определяемые по формулам:
}) ),( ),((:{ 1,0001
)(
1 1
xpbARU N
t
N =ÃÎ= dde , }),,(:{ 2,022
)(
2 2
xpdARU N
t
N =ÃÎe= .
Обозначим символом )(Pr t РВ на множестве )(t
NR значений случайного век-
тора e . Из определения параметров
21
, ÃÃ pp следуют равенства:
}{Pr 1
)(
1
Ut=Ãp , }{Pr 2
)(
2
Ut=Ãp . (22)
С другой стороны, согласно определению алгоритма Ã, выполняется равенство:
}{Pr 21
)( UUt=Ãp . (23)
Непосредственно из формул (22), (23) следуют соотношения (20), (21). Ут-
верждение доказано.
Получим оценку трудоемкости ) , , ,( NptnNTT ÃÃ = алгоритма Ã. На первом
шаге этого алгоритма построение СЛУ (8) не требует вычислений (за исключени-
ем, быть может, нахождения распределения вероятностей
1Np по распределению
Np ). Следовательно, трудоемкость первого шага равна ),,,(
11 1 NptnNT Ã .
На втором шаге для вычисления вектора *1e по формуле (12) достаточно вы-
полнить nt умножений и (n – 1)t + t = nt сложений (вычитаний) в кольце .
1NR Да-
лее, вычисление вектора d в правой части СЛУ (11) потребует выполнения nt ум-
ножений и (n + 1)t сложений (вычитаний) в кольце NR .
Таким образом, суммарная сложность второго шага алгоритма Ã составит не
более
)()1(2)(2),,,(
22 22 NtTnNntTptnNTT N СЛУМ +++= Ã
Метод оптимизации алгоритмов решения систем линейных
уравнений с искаженной правой частью над кольцом вычетов по модулю 2N
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 19
двоичных операций (символы )(NTУМ и )(NTСЛ обозначают соответственно вре-
менные сложности алгоритмов умножения и сложения (вычитания) N-разрядных
двоичных целых чисел). Наконец, на третьем шаге алгоритма Ã вычислений фак-
тически не производится.
Итак, доказано следующее утверждение.
Утверждение 3. Трудоемкость алгоритма ),( 21, 21
ÃÃq=Ã NN , определяемого
по формуле (4), оценивается сверху величиной:
))()(()1(2),,,(),,,(
2211 21 NTNTtnptnNTptnNTT NN СЛУМ ++++= ÃÃÃ . (24)
Оптимизация алгоритмов решения систем линейных уравнений
с искаженной правой частью над кольцом RN
Следуя общей идее предложенного в [14] подхода к построению оптималь-
ных вычислительных алгоритмов, определим рекурсивно отображения
kNNN ,...,, 21
q : NNNN k
L®L´´L´L ...
21
,
где k ³ 3, N = N1 + N2 + … + Nk, Ni ³ 1, ki ,1Î , полагая для любых
Ãi Î iNL ( ki ,1Î ):
kNNN ,...,, 21
q (Ã1, Ã2, …, Ãk) =
121 ,...,,, (
-
qq - kkk NNNNNN (Ã1, Ã2, …, Ãk–1), Ãk).
Пусть теперь для каждого натурального Nj ,1Î задан некоторый алгоритм
Ã(j) решения систем линейных уравнений с искаженной правой частью над коль-
цом jR . Функции надежности jp и трудоемкости Tj алгоритма Ã(j) ( Nj ,1Î )
предполагаются известными. Обозначим через Q = Q(Ã(1), …, Ã(N)) класс всех
алгоритмов Ã Î NL вида Ã = qn
def
=
kNNN ,...,, 21
q (Ã(N1), Ã(N2), …, Ã(Nk)), где n =
= (N1, N2, …, Nk) пробегает всевозможные композиции (упорядоченные разбие-
ния) числа N.
Зафиксируем СЛУ вида (1) над кольцом RN и предположим, что двоичные
разряды координат случайного вектора e являются независимыми в совокупности
случайными величинами. Рассмотрим задачу построения алгоритма Ã* Î Q,
имеющего при заданной верхней границе трудоемкости наибольшую надежность
среди всех алгоритмов решения СЛУ (1), принадлежащих классу Q:
) , ,( 0 NpxAÃp ® max, ),,,( NptnNT Ã £ T0, Ã Î Q. (25)
Заметим, что, поскольку Q содержит ровно 2N–1 различных алгоритмов, то
тривиальная процедура решения задачи (25) сводится к перебору этих алгоритмов
А. Н. Алексейчук, С. М. Игнатенко
20
и вычислению их надежностей и трудоемкостей с использованием соотношений
(21), (24).
Отметим, что при определенных дополнительных ограничениях на РВ коор-
динат случайного вектора e задача (25) может быть решена более эффективно.
Рассмотрим, например, частный случай, в котором
aNa
N ppap --= )1()( , NN Raaa Î= - ),...,( 01 , (26)
где 10 ... -++= Naaa , 0 < p < 2
1 . Обозначим jj канонический гомоморфизм ко-
льца RN в кольцо jR , Nj ,1Î . Отображение jj стандартным образом продолжим
до отображений, заданных на множестве всех матриц над кольцом RN и распреде-
лений вероятностей на этом кольце соответственно.
Заметим, что на основании утверждений 2, 3 и равенства (26) для любой ком-
позиции n числа N надежность и трудоемкость алгоритма Ã = qn определяются
соответственно по формулам:
) , ,( 0 NpxAÃp = Õ
=
N
j
j
j
1
)( ap ,
),,,( NptnNT Ã = )1))(()(()1(2
1
СЛУМ
1
-+++ åå
==
N
j
j
N
j
jj NTNTtnT aa ,
где aj — число слагаемых, равных j, в композиции n, pj = pj(j j(A), j j(x0), j j(pN)),
Tj = Tj (N, n, t, jj (pN)), Nj ,1Î . Отсюда следует, что при выполнении условия (26)
задача (25) равносильна следующей задаче целочисленного линейного програм-
мирования:
å
=
N
j
jj
1
lnpa ® max, )))()(()1(2( СЛУМ
1
NTNTtnT
N
j
jj +++å
=
a £ T0 +
+ ))()(()1(2 NTNTtn СЛУМ ++ ,
ja Î Z, ja ³ 0, Nj ,1Î , 1a + 2 2a + … + N Na = N.
Для решения последней задачи можно применять известные алгоритмы [16].
Результаты экспериментального исследования
эффективности алгоритмов решения СЛУ с искаженной
правой частью над кольцом R5
Ниже в таблице представлены численные оценки средней надежности и тру-
доемкости семи программно реализованных алгоритмов решения СЛУ с иска-
женной правой частью над кольцом вычетов по модулю 32, соответствующих се-
ми композициям числа N = 5. Данные в таблице получены с использованием про-
Метод оптимизации алгоритмов решения систем линейных
уравнений с искаженной правой частью над кольцом вычетов по модулю 2N
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 21
граммы для ПЭВМ типа Celeron 1100 MHz, 256 Mb ОЗУ, которая для каждой па-
ры значений n, t (числа неизвестных и уравнений соответственно) решает 100 сис-
тем линейных уравнений с искаженной правой частью над кольцом R5.
Характеристики эффективности алгоритмов решения СЛУ
с искаженными правыми частями над кольцом вычетов по модулю 32
(1,1,1,1,1) (2, 2, 1) (2, 3) (3, 1, 1) (3, 2) (4, 1) (5)
n t P T P T P T P T P T P T P T
3 7 0,01 0 0,01 0 0,01 0 0,03 0 0,03 0 0,03 1 0,09 20
25 0,04 0 0,10 0 0,13 0 0,22 0 0,39 0 0,39 2 0,86 28
40 0,15 0 0,21 0 0,27 0 0,34 0 0,59 0 0,78 3 0,99 34
60 0,17 0 0,38 0 0,48 0 0,48 1 0,79 0 0,94 4 1 42
80 0,30 0 0,57 0 0,64 0 0,63 1 0,88 0 0,95 6 1 50
100 0,47 0 0,66 0 0,78 0 0,77 1 0,99 0 1 7 1 58
150 0,67 0 0,88 0 0,92 1 0,90 2 1 1 1 10 1 79
4 25 0 0 0,02 0 0,04 1 0,08 2 0,20 1 0,22 42 0,72 919
80 0,18 0 0,33 1 0,45 3 0,38 5 0,79 3 0,93 98 1 1717
150 0,49 0 0,81 1 0,88 4 0,81 10 1 5 1 168 1 2744
Истинное решение и элементы матрицы коэффициентов каждой системы ли-
нейных уравнений формируются с использованием линейного конгруэнтного ге-
нератора по модулю 32. Векторы искажений в правых частях СЛУ состоят из
символов, представленных в коде ASCII, которые выбираются последовательно, с
интервалом в 10 знаков, из осмысленного текста, составленного из русскоязыч-
ных и англоязычных фраз. В качестве исходного алгоритма Ã(j) решения СЛУ с
искаженной правой частью над кольцом Rj ( 5,1 Îj ) используется стандартный
алгоритм, основанный на методе максимума правдоподобия [11]. Параметры P и
T в таблице обозначают соответственно отношение числа правильно решенных
СЛУ к общему числу (100) систем уравнений и суммарное время (в секундах) ре-
шения всех систем уравнений без учета времени их формирования.
Как видно из таблицы, диапазон изменения значений характеристик эффек-
тивности рассматриваемых алгоритмов достаточно широк. Так, средняя надеж-
ность решения системы из 25 уравнений от трех неизвестных, с искаженными
правыми частями, изменяется от 0,04 до 0,86. При этом на решение 100 таких сис-
тем затрачивается от 1 до 28 секунд. Система от того же числа неизвестных, со-
стоящая из 60 уравнений с искаженными правыми частями, решается со средней
надежностью от 0,17 до 1. Время решения 100 указанных СЛУ составляет от 1 до
42 секунд. Очевидно, что с ростом отношения t/n надежность каждого из семи ал-
горитмов увеличивается.
Результаты экспериментальных исследований, приведенные в таблице, по-
зволяют упорядочить рассматриваемые алгоритмы по убыванию их средней на-
дежности. Так, при всех значениях параметров n и t, указанных в таблице, наи-
большую среднюю надежность имеет алгоритм q(5); далее следуют алгоритмы
q(4,1) и q(3,2). При умеренных (по сравнению с n) значениях t следующими в списке
А. Н. Алексейчук, С. М. Игнатенко
22
оказываются алгоритмы q(3,1,1) и q(2,3). С ростом t средние надежности этих алго-
ритмов выравниваются, и при t >> n порядок их расположения меняется на проти-
воположный: q(2,3), q(3,1,1). Наконец, замыкают список алгоритмы q(2,2,1) и q(1,1,1,1,1).
Отметим, что алгоритм q(1,1,1,1,1) совпадает с последовательным методом ре-
шения систем линейных уравнений с искаженной правой частью над кольцом R5
[10]. Как видно из таблицы, этот алгоритм имеет наименьшую среднюю надеж-
ность и наименьшую трудоемкость среди семи рассматриваемых алгоритмов. С
другой стороны, алгоритм q(5) по существу представляет собой метод максимума
правдоподобия решения СЛУ с искаженной правой частью над кольцом R5 и ха-
рактеризуется среди рассматриваемых алгоритмов наибольшими значениями
средней надежности и трудоемкости.
В целом, как видно из данных, представленных в таблице, предложенный ме-
тод оптимизации алгоритмов решения СЛУ с искаженной правой частью над
кольцом RN позволяет обеспечить хороший «баланс» между основными показате-
лями эффективности (надежностью и трудоемкостью) алгоритмов путем выбора
подходящей композиции числа N. Ясно также, что с расширением совокупности
исходных алгоритмов появляется дополнительная возможность целенаправленно
варьировать значения указанных показателей в зависимости от условия конкрет-
ной прикладной задачи, приводящей к решению систем линейных уравнений с
искаженной правой частью над кольцом вычетов по модулю 2N.
1. Балакин Г.В. Введение в теорию случайных систем уравнений // Труды по дискретной
математике. — М.: ТВП. — 1997. — Т. 1. — С. 1-18.
2. Балакин Г.В., Никольский Ю.Б. Последовательное применение метода максимума прав-
доподобия к решению систем уравнений с мешающими параметрами // Обозрение прикл. про-
мышл. матем. — 1995. — Т. 2. — Вып. 3. — С. 468-476.
3. Балакин Г.В. Эффективно решаемые классы систем булевых уравнений // Обозрение
прикл. промышл. матем. — 1995. — Т. 2. — Вып. 3. — С. 494-501.
4. Meier W., Staffelbach O. Fast Correlation Attacs on Stream Ciphers // J. Cryptology. — 1989.
— Vol. 1, N 3. — P. 159-176.
5. Kovalenko I.N., Savchuk M.N. Some Methods of Decoding Corrupted Linear Codes //
Реєстрація, зберігання і оброб. даних. — 1999. — Т. 1, № 2. — С. 62–68.
6. Johansson T., Jonsson F. Fast Correlation Attacks Through Reconstruction of Linear Polyno-
mials // Advances in Cryptology — Crypto’00, Proceedings. — Springer Verlag, 2000. — P. 300–315.
7. Chepyzhov V., Johansson T., Smeets B. A Simple Algorithm for Fast Correlation Attacks on
Stream Ciphers // FSE’2000. — Springer Verlag, 2001. — Vol. 547. — P. 181–195.
8. Смирнов В.Г. Системы булевых уравнений рекуррентного типа // Обозрение прикл. про-
мышл. матем. — 1995. — Т. 2. — Вып. 3. — С. 477-482.
9. Балакин Г.В. Оценка истинного решения системы уравнений над кольцом вычетов при
аддитивной помехе // Проблемы теоретической кибернетики: Тез. докл. XII Междунар. конф. —
Нижний Новгород, 1999. — С. 15.
10. Алексейчук А.Н. Системы линейных уравнений с искаженной правой частью над коль-
цом вычетов по модулю 2N // Захист інформації. — 2001. — № 4. — С. 12–19.
Метод оптимизации алгоритмов решения систем линейных
уравнений с искаженной правой частью над кольцом вычетов по модулю 2N
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 23
11. Алексейчук А.Н., Игнатенко С.М. Оценки эффективности универсальных методов вос-
становления искаженных линейных рекуррент над кольцом вычетов по модулю 2N // Зб. наук. пр.
ІПМЕ НАН України. — Вып. 20. — К., 2003. — С. 40–48.
12. Игнатенко С.М., Алексейчук А.Н. Алгоритм восстановления искаженной линейной ре-
курренты над кольцом вычетов по модулю 2N с использованием быстрого преобразования Ферма //
Тез. докл. VI Междунар. научно-практич. конф. «Безопасность информации в информационно-
телекоммуникационных системах». — К., 2003. — С. 53–54.
13. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. — М.: Мир,
1989. — 448 с.
14. Гаврилкевич М.В., Солодовников В.И. Эффективные алгоритмы решения задач линейной
алгебры над полем из двух элементов // Обозрение прикл. промышл. матем. — 1995. — Т. 2. —
Вып. 3. — С. 400-437.
15. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов:
Пер. с англ. — М.: Мир, 1979. — 535 с.
16. Мину М. Математическое программирование: Пер. с фр. — М.: Наука, 1990. — 488 с.
Поступила в редакцию 07.02.2005
УДК 621.391: 519.2
УДК 621.391: 519.2
УДК 621.391: 519.2
УДК 621.391: 519.2
УДК 621.391: 519.2
УДК 621.391: 519.2
УДК 621.391: 519.2
А. Н. Алексейчук1, С. М. Игнатенко2
Введение
Метод построения новых алгоритмов решения систем линейных
уравнений с искаженной правой частью над кольцом RN
Характеристики эффективности алгоритмов решения СЛУ
с искаженными правыми частями над кольцом вычетов по модулю 32
|