Кузюрин Н.Н. Фомин С.А. Сложность комбинаторных алгоритмов. Курс лекций
Подождите немного. Документ загружается.
Алгоритм 33 Протокол выработки общего секретного ключа
1. A и B независимо друг от друга выбирают по одному натуральному числу X
A
и X
B
. Эти элементы они держат в
секрете.
2. Каждый из них вычисляет новый элемент
Y
A
= a
X
A
mod p, Y
B
= a
X
B
mod p,
причем числа p и a считаются общедоступными. Потом они обмениваются этими элементами по каналу связи.
3. A получив Y
B
и зная свой секретный элемент X
A
вычисляет новый элемент
Y
X
A
B
= (a
X
B
)
X
A
mod p.
Аналогично поступает B:
Y
X
B
A
= (a
X
A
)
X
B
mod p.
После этого у A и B появился общий элемент a
X
A
X
B
mod p, который и объявляется общим ключом.
Теорема 32 Пусть существует полиномиальный алгоритм A, который при случайном и равномерном выборе
b ∈ Z
∗
p
правильно решает задачу дискретного логарифмирования на доле b не менее 1/n
O(1)
(здесь n обозна-
чает длину двоичной записи b).
Тогда существует полиномиальный по n вероятностный алгоритм, который находит дискретный лога-
рифм для всех b.
Доказательство Построим новый вероятностный алгоритм B:
1. выберем x
0
случайно и равномерно из Z
p−1
2. вычислим b
0
= bg
x
0
mod p.
Заметим, что величина g
x
0
mod p равномерно распределена в Z
∗
p
(упражнение 61).
Тогда b
0
— случайный элемент, равномерно распределенный в Z
∗
p
(упражнение 62).
А далее все просто. Применим алгоритм A к b
0
: при этом мы получим ответ с вероятностью не менее 1/n
O(1)
.
А по нему очень легко восстановить ответ для исходной задачи, т.е. найти дискретный логарифм b. Действительно,
дискретный логарифм от b
0
по определению равен x + x
0
, т.к. g
x
g
x
0
= g
x+x
0
. Но мы знаем x
0
, поэтому легко можем
найти x.
Далее используя стандартную технику амплификации (т.е. повторяя для данного b независимо эту процедуру поли-
номиальное число раз), можно сделать вероятность ошибки экспоненциально малой. 2
Упражнение 61 Выберем x случайно и равномерно из Z
p−1
. Докажите, что величина g
x
mod p равномерно
распределена в Z
∗
p
.
Упражнение 62 Выберем x случайно и равномерно из Z
p−1
. Докажите, что для любого фиксированного b 6= 0
величина b
0
= bg
x
mod p равномерно распределена в Z
∗
p
.
4.2.3 Система RSA и ее анализ
Еще одним новым понятием криптографии является понятие функции с секретом.
Определение 71 Функцией с секретом K называется функция F
K
: X → Y , зависящая от параметра K и
обладающая следующими свойствами:
1. при любом K существует полиномиальный алгоритм вычисления значений F
K
(x);
2. при неизвестном K не существует полиномиального алгоритма инвертирования F
K
;
3. при известном K существует полиномиальный алгоритм инвертирования F
K
.
121
Существование таких функций также не доказано, но для практических целей криптографии было построено несколь-
ко функций, которые могут оказаться функциями с секретом.
Для них свойство 2 пока строго не доказано, но считается, что задача инвертирования эквивалентна некоторой
давно изучаемой трудной (с алгоритмической точки зрения) математической задаче. Наиболее известной и популярной
из них является теоретико-числовая функция, на которой построен шифр RSA.
Сначала приведем общую схему криптосистемы с открытым ключом.
1. Пользователь A, который хочет получать шифрованные сообщения, должен выбрать какую-нибудь функцию F
K
с секретом K.
2. Он публикует описание функции F
K
в качестве своего алгоритма шифрования. При этом значение секрета K он
никому не сообщает и держит в секрете.
3. Пользователь B посылает пользователю A защищаемую информацию x ∈ X, вычисляя y = F
K
(x) и посылая y
по открытому каналу пользователю A.
4. Поскольку A знает секрет K, то он умеет эффективно инвертировать F
K
. Он вычисляет x по полученному y.
Никто другой не знает K и, поэтому, в силу свойства 2 функции с секретом, не сможет за полиномиальное время
по шифрованному сообщению F
K
(x) вычислить защищаемую информацию x.
Схема RSA устроена следующим образом (алгоритм 34).
Алгоритм 34 Схема RSA
1. Выбирают два достаточно больших простых числа p и q (обычно около 100 десятичных знаков).
2. Находят n = pq.
3. Выбирают число e, взаимно-простое с p − 1 и q −1:
нод(e, p − 1) = нод(e, q −1) = 1.
Здесь и далее нод(a, b) обозначает наибольший общий делитель чисел a и b.
4. Вычисляют функцию Эйлера φ(n), равную числу натуральных чисел не превосходящих n и взаимно-простых с
ним по формуле:
φ(n) = φ(p)φ(q) = (p − 1)(q −1).
5. Находят целое число d такое, что
de ≡ 1 mod φ(n), 1 ≤ d < φ(n).
Такое число существует и единственно, поскольку нод(e, φ(n)) = 1.
• Функция F
K
, реализующая шифрование в схеме RSA устроена следующим образом:
F
K
: x → x
e
mod n.
• Дешифрование осуществляется функцией
G(a) = a
d
mod n.
Секретом является число p (или q) в разложении n на простые множители (или d).
Докажем сейчас однозначность декодирования.
Теорема 33 Для всех x
x
ed
= x mo d n.
Доказательство Имеем:
ed = 1 mod φ(n),
откуда получаем, что для некоторого k
ed = 1 + k(p − 1)(q −1).
122
Пусть x 6= 0. Малая теорема Ферма гласит, что x
p−1
= 1 mod p, откуда мы получаем, что
x
ed
= x(x
p−1
)
k(q−1)
mod p
= x(1)
k(q−1)
mod p
= x mod p.
Если же x = 0, то тривиально имеем x
ed
= x mod p.
Аналогично рассматриваем соотношения по модулю q и получаем, что для всех x
x
ed
= x mo d q.
Теперь остается применить китайскую теорему об остатках, которая гласит:
для взаимно-простых чисел r
1
, . . . , r
k
любое число 0 ≤ n < r
1
· . . . · r
k
однозначно восстанавливается по остаткам
n = n
1
mod r
1
, n = n
2
mod r
2
, . .. , n = n
k
mod r
k
.
По китайской теореме об остатках имеет место соотношение:
x
ed
= x mo d pq.
2
Упражнение 63 Система RSA является мультипликативной в том смысле, что произведение кодов равно
коду произведения
x
e
y
e
mod n = (xy)
e
mod n.
Используя этот факт докажите, что если противник имеет алгоритм расшифровки 1 процента сооб-
щений случайно выбранных из Z
n
, то он может переработать его в вероятностный алгоритм расшифров-
ки произвольного сообщения, закодированного кодом RSA, с большой вероятностью (аналогично теореме
32).
123
Глава 5
Приложения
5.1 Глоссарий
По результатам чтения лекций, были выявлены основные матобозначения вызывающие у студентов затруднения. Они
приведены как справочный материал.
Итак,
Определение 72 Алфавит — конечный набор символов.
Определение 73 Слово — конечная последовательность символов из некоторого алфавита Σ.
Пустое слово обозначается ∅. Набор слов длины n над алфавитом Σ обозначается Σ
n
, набор всех слов (включая
пустое) — Σ
∗
.
Определение 74 Язык L — произвольное подмножество L ⊆ Σ
∗
, т.е. произвольное множество слов над ал-
фавитом Σ.
Надо различать пустой язык (язык не содержащий ни одного слова), который также обозначается ∅, от языка {∅},
содержащего единственное пустое слово.
Определение 75 Дополнение языка L — язык L, состоящий из всех возможных слов над алфавитом Σ, не
входящих в язык L — L ≡ Σ
∗
\ L.
Множество вещественных чисел обозначается R, целых — Z, рациональных — Q, натуральных — N. Неотрица-
тельные их подмножества обозначаются соответственно R
+
, Z
+
, Q
+
.
Пусть f : N → R, g : N → R.
Определение 76 f=O(g), если ∃c ∈ R, c > 0, и ∃n
0
∈ N, ∀n > n
0
: |f(n) ≤ c|g(n)||.
Определение 77 f=o(g), если f равно нулю лишь в конечном числе точек и lim
n→∞
f(n)
g (n)
= 0.
Определение 78 f = Ω(g), если g = O(f).
Определение 79 f = Θ(g), если f = O(g) и g = O(f).
Определение 80 Кортеж (к-кортеж) — упорядоченный набор из k элементов (множеств, подмножеств,
элементов множеств). Обозначается угловыми скобками, например кортеж из элементов a, b, и множества
C — ha, b, Ci.
5.2 Введение в Python
Здесь мы представим краткое введение в язык Python, в первую очередь для того, чтобы обеспечить однозначное по-
нимание представленных на языке Python алгоритмов.
Вообще, трудно найти другой язык, одновременно пригодный для обучения с одной стороны, и достаточно мощный,
для реализации реальных приложений (включая научные). Дело в том, что автор Питона (Guido van Rossum) долгое
время участвовал в проекте создания языка обучения программированию ABC, который должен был заменить BASIC,
124
и вынес из проекта несколько ценных идей, как минимизировать синтаксические накладные расходы, которые необ-
ходимы в реальном языке программирования (сложные декларации, открытия/закрытия блоков), избежав при этом
каббалистического минимализма (доступных только адептам пониманию взаимодействия спецсимволов типа «%$
ˆ
">)
в языках типа Perl.
В питоне была применена идея синтаксического выделения блоков с помощью отступов (в пределах блока отступ
должен быть одинаков), кроме того операторы, начинающие вложенный блок, должны, для повышения читаемости,
отделяться двоеточием:
Далее, все переменные в питоне являются однотипными ссылками на объекты. Таким образом, устраняется необ-
ходимость декларации переменных, переменная определяется в момент первого присваивания и тип хранимого в ней
объекта может быть переопределен последующими присваиваниями.
Кстати, можно можно присваивать одно и то же значение нескольким переменным одновременно:
Также, интерпретатор берет на себя все управление памятью (резервирование, сборка мусора и т.п.).
Непосредственно в язык встроенны не только примитивные типы данных, как числа и строки, но и более сложные
структуры: Кортежи (touples):
(к сожалению, индексы в Pythonе, также как и в C, 0-based — увы).
Эффективно реализованные словари или хэши (hash):
Списки или последовательности (list) (включая операции по slicinгу):
125
Вообще, Python современный, очень популярный, красивый, мощный и удобный интерпретируемый, расширяемый
и встраиваемый, объектно-ориентированный язык (со множественным наследованием), включающий даже элемен-
ты функционального программирования. Т.е. это живой язык, активно использующийся для программирования как
«обычных», пользовательских приложений, с переносимым оконным (см. например wxPython), или веб-приложений
(см. например Zope). Растет его сфера использования в научных целях, для прототипирования и разработки новых ал-
горитмов, для анализа или визуализации данных (см. например Scientific Python, ). Здесь, мы
рассмотрим только базовые свойства синтаксиса, чтобы можно было устранить непонимание текстов, отдельных, не
больше страничек, функций и процедур на Python, а за всем остальным, добро пожаловать на
.
Теперь перечислим основные операторы.
Оператор if:
Оператор for имеет вид
Блок кода после заголовка выполняется, пока некая_переменная принадлежит некому_диапазону (причем этот
диапазон может быть списком, числовой последовательностью, массивом каких-либо значений), а если нужно просто
организовать цикл «от a до b», то для этого можно воспользоваться функцией range(a,b+1), которая вернет соответ-
ствующий список:
Да, для выхода из цикла можно использовать оператор break.
Есть и цикл while, который выполняется пока истинно указанное выражение:
Понятна и проста декларация любой функции или процедуры (заметим, что декларации могут быть вложенными):
126
Для возврата значений (тип которых, кстати, может быть тоже любым), очевидно, используется return.
А оператор print печатает содержимое переданных ему аргументов, пытаясь придать печатный вид кортежам, спис-
кам и словарям.
127
Литература
[М. 82] Д. С. Джонсон М. Гэри. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 44, 46
[А. 99] М. Вялый А. Китаев, А. Шень. Классические и квантовые вычисления. издательство МЦНМО, 1999. 60
[Дж.67] Р. Стирнз Дж. Хартманис. О вычислительной сложности алгоритмов. In Киб. сборник, нов. сер., number 4,
pages 57–85. М., Мир, 1967. 40
[Ред71] Н. П. Редькин. О минимальной реализации линейной функции схемой из функциональных элементов. Ки-
бернетика, 6:31–38, 1971. 47
[Кар75a] Р. М. Карп. Сводимость комбинаторных задач. In ДАН СССР, editor, Киб. сборник, нов. сер., number 12,
pages 16–38, 1975. 44, 45
[Кук75b] C. А. Кук. Сложность процедур вывода теорем. In М. Мир, editor, Киб. сборник, нов. сер., number 12, pages
5–15, 1975. 41, 44, 45
[Раз85a] А. А. Разборов. Нижние оценки монотонной сложности логического перманента. Математические За-
метки, 37(4):887–900, 1985. 47
[Раз85b] А. А. Разборов. Нижние оценки монотонной сложности некоторых булевых функций. ДАН СССР,
281(4):798–801, 1985. 47
[Раз85c] А. А. Разборов. Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию
логического сложения. Математические Заметки, 37(6), 1985. 47
[А.91] Схрейвер А. Теория линейного и целочисленного программирования. М. Мир, 1991. 39
[Н.Н96] А.А. Разборов Н.Н. Кузюрин. Оценка состояния и прогнозные исследования эффективных алгоритмов для
точного и приближенного решения переборных задач дискретной оптимизации. Отчет по НИР., 1996. 4
[Том99] Рональд Ривест Томас Кормен, Чарльз Лейзерсон. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.
15
[AS92] N. Alon and J.H. Spencer. The Probabilistic Method. Wiley, 1992. 93
[Blu67] Manuel Blum. A machine-independent theory of the complexity of recursive functions. Journal of the ACM,
14(2):322–336, 1967. 39
[Joh90] David S. Johnson. A catalog of complexity classes. In Handbook of Theoretical Computer Science, Volume A:
Algorithms and Complexity (A), pages 67–161. 1990. 39, 89
[L.G79] L.G.Khachiyan. A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20:191–194,
1979. 39
[Lov] L
´
aszlo Lov
´
asz. Complexity of algorithms. 4
[MR95] R. Motwani and P. Raghavan. Randomized algorithms. Cambridge Univ. Press, 1995. 96, 97, 98, 110
[Rag88] Prabhakar Raghavan. Probabilistic constructions of deterministic algorithms: approximating packing integer
programs. Journal of Computer and System Scince, 37(4):130–143, 1988. 110
[RW90] Ran Raz and Avi Wigderson. Monotone circuits for matching require linear depth. In ACM Symposium on
Theory of Computing, pages 287–292, 1990. 47
128
[Sma00] Smale. Mathematical problems for the next century. In V. Arnold, M. Atiyah, P. Lax, and B. Mazur, editors,
Mathematics: Frontiers and Perspectives, IMU, AMS, 2000. 2000. 5, 44
[SS71] A. Schonhage and V. Strassen. Schnelle multiplikation grosser zahlen, 1971. 38
[SV77] R. Solovay and Strassen V. A fast Monte-Carlo test for primality. SIAM Journal on Computing, 6(1):84–85,
March 1977. 97
129
Index
2-Satisfiability
Задача, 46
2-Выполнимость
Задача, 46
2SAT, 46
Задача, 46
3-Satisfiability
Задача, 46, 57, 59
3-Выполнимость
Задача, 46, 57, 59
3SAT, 46, 57, 59
Задача, 46, 57, 59
3Выполнимость-Максимизация
Задача, 57–59
BPP
Класс, 39, 51–53
coNP
Класс, 42, 44, 47, 48, 50, 54
coNSPACE
Класс, 42
coNTIME
Класс, 42
coRP
Класс, 49, 50, 54, 56
DSPACE
Класс, 40, 42
DTIME
Класс, 39, 42
Euler cycle
Алгоритм, 73
EXPTIME
Класс, 39, 40
GCD
Алгоритм, 7
Greedy MSSC
Алгоритм, 70, 72
halting problem, 36, 40
Задача, 36, 40
K-covering, 69
Задача, 69
Knapsack, 79, 82
PTAS, 84, 87
Алгоритм, 79, 82, 84
PTAS, 84, 87
Жадный, 73, 84
Алгоритм Немхаузера-Ульмана, 82
Задача, 79, 82
Knapsack-SAT
Алгоритм, 79
MAX-3SAT, 57–59
Задача, 57–59
MAX-CUT, 108, 109
Алгоритм
Вероятностный, 109
Задача, 108, 109
MAX-CUT(VP), 109, 110
Задача, 109, 110
MAX-CUT(ЦЛП), 109
Задача, 109
MAX-SAT, 58, 105, 106, 110–112
Алгоритм
Вероятностный, 106, 107, 109, 112
Дерандомизация, 112
Задача, 58, 105, 106, 110–112
Mergesort
Алгоритм, 17
Min Sum Set Cover, 70, 71
Задача, 70, 71
Minimum Spanning Tree, 15, 40
Алгоритм
Прима, 15
Задача, 15, 40
NEXP
Класс, 56
NP
Класс, 8, 13, 15, 17, 39, 40, 42–47, 50, 54–59, 67,
76, 79, 88, 89, 94, 100, 105
NPC
Класс, 44, 46, 47, 57–59
NSPACE
Класс, 42
NTIME
Класс, 42, 56
P
Класс, 39–42, 44–47, 57
Packing, 89, 91
Алгоритм, 89, 91
Задача, 89, 91
PCP
Класс, 39, 55–59
130