<< Предыдущая

стр. 47
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

3 15 1
4 20 6
5 25 4
6 30 2


2. Нахождение a–1 (mod n), если известна функция Эйлера ?(n).
Пусть n = 7, a = 5. Найти x = a–1 (mod n) = 5–1 (mod 7). Модуль n = 7 – простое число. Поэтому
функция Эйлера ?(n) = ?(7) = = n –1 = 6. Обратная величина от 5 по mod 7
a–1 (mod n) = a?(n)–1 (mod n) =
= 56–1 mod 7 = 55 mod 7 = (52 mod 7)(53 mod 7) mod 7 =
= (25 mod 7)(125 mod 7) mod 7 = (4 ? 6) mod 7 = 24 mod 7 = 3.
–1
Итак, x = 5 (mod 7) = 3.
3. Нахождение обратной величины a–1 (mod n) с помощью расширенного алгоритма Евклида.
Алгоритм Евклида можно обобщить способом, который имеет большое практическое значе-
ние. При этом способе во время вычисления НОД (a,b) можно попутно вычислить такие целые числа
u1 и u2, что
a ? u1 + b ? u2 = НОД (a,b).
Это обобщение (расширение) алгоритма Евклида удобно описать, используя векторные обо-
значения [45].


Расширенный алгоритм Евклида
При заданных неотрицательных целых числах a и b этот алгоритм определяет вектор
(u1, u2, u3),
такой, что
a ? u1 + b ? u2 = u3 = НОД (a, b).
В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3). Дейст-
вия с векторами производятся таким образом, что в течение всего процесса вычисления выполняют-
ся соотношения
a ? t1 + b ? t2 = t3, a ? u1 + b ? u2 = u3, a ? v1 + b ? v2 = v3.
Для вычисления обратной величины a–1 (mod n) используется частный режим работы расши-
ренного алгоритма Евклида, при котором b = n, НОД (a,n) = 1, и этот алгоритм определяет вектор
(u1, u2, u3),
такой, что
u3 =1, a ? u1 + n ? u2 = НОД (a,n) =1,
(a ? u1 + n ? u2) mod n ? a ? u1 (mod n) ? 1,
a–1 (mod n) ? u1 (mod n).
Шаги алгоритма:
1. Начальная установка.
Установить (u1, u2, u3) : = (0, 1, n),
(v1, v2, v3) : = (1, 0, a).
2. u3 =1 ?. Если u3 =1, то алгоритм заканчивается.
3. Разделить, вычесть.
Установить q : = [u3/v3].
Затем установить
(t1, t2, t3) : = (u1, u2, u3) – (v1, v2, v3) ? q,
(u1, u2, u3) : = (v1, v2, v3),
(v1, v2, v3) : = (t1, t2, t3).
Возвратиться к шагу 2.
–1 –1
Пример. Заданы модуль n = 23 и число a = 5. Найти обратное число a (mod 23), т.е. x = 5 (mod 23).
Используя расширенный алгоритм Евклида, выполним вычисления, записывая результаты отдельных шагов в табл.
П.3.
Таблица П.3
q u1 u2 u3 v1 v2 v3

– 0 1 n = 23 1 0 a=5
4 1 0 5 –4 1 3
1 –4 1 3 5 –1 2
1 5 –1 2 –9 2 1
– –9 2 1

При u3 =1, u1 = –9, u2 = 2
(a ? u1 + n ? u2 ) mod n = (5 ? (– 9) + 23 ? 2) mod 23 =
= 5 ? (– 9) mod 23 ? 1,
–1 –1
a (mod n) = 5 (mod 23) = (– 9) mod 23 = (– 9 + 23) mod 23 = 14.
–1
Итак, x = 5 (mod 23) ? 14 (mod 23) = 14.

Для решения более сложных сравнений
a ? x ? b (mod n), т.е. b ?1, x = ?
используется следующий прием. Сначала решают сравнение
a ? y ?1 (mod n),
т.е. определяют
y = a–1 (mod n),
а затем находят
x = a–1 b (mod n) = y ? b (mod n).
Пример. Найти x для сравнения
5 ? x ? 9 (mod 23).
Сначала решаем сравнение
5 ? y ? 1 (mod 23).
–1
Получаем y = 5 (mod 23) = 14. Затем находим
–1
x = 5 ? 9 (mod 23) = 14 ? 9 (mod 23) = 126 (mod 23) ? 11 (mod 23),
x = 11.


Китайская теорема об остатках
Любое неотрицательное целое число, не превосходящее произведения модулей, можно од-
нозначно восстановить, если известны его вычеты по этим модулям. Этот результат был известен
еще в древнем Китае и носит название китайской теоремы об остатках. Теорема была предложе-
на китайским математиком первого века Сун Це. Китайская теорема об остатках является мощным
криптографическим инструментом.
Китайская теорема об остатках формулируется следующим образом.
Пусть m1, m2, …, mt – модули (целые числа, большие 1), которые являются попарно взаимно
простыми, т.е. НОД (mi,mj) =1 при i ? j.
Пусть a1, a2, …, at – тоже целые числа, 0 ? ai ? mi.
Пусть M = m1? m2 ? …? mt – произведение всех mi. Обозначим Mi = M/mi.
И пусть Ni будет обратным к Mi (mod mi), i = 1, 2, …, t, т.е. Mi ? Ni ?1 (mod mi).
Так как НОД (Mi, mi) =1, то обратный элемент Ni существует и легко находится из алгоритма
Евклида из соотношения
Mi ? Ni + mi ? ni =1, i =1, 2, …, t.
Сравнения x ? ai (mod mi), i =1, 2, …, t, имеют в интервале [0, M –1] единственное общее ре-
шение
t

? ai ? Ni ? Mi (mod M).
x=
i=1

Рассмотрим частный случай. Пусть M=m1?m2, где m1, m2 – взаимно простые числа. Тогда для
произвольных целых a1< m1 и a2 < m2 существует единственное число x, x < M, такое, что
x ? a1 (mod m1) и x ? a2 (mod m2).
Чтобы найти значение решения x, сначала используют алгоритм Евклида для вычисления
значений N1 и N2, таких, что
N1 ? M1 ? 1 (mod m1) и N2 ? M2 ? 1 (mod m2).

m * m2
M M
=1
Здесь M1 = = m2; M2 = = m1.
m1 m1 m2
Затем вычисляют значение
x = (a1 ? N1 ? M1 + a2 ? N2 ? M2)(mod M).
Алгоритм нахождения решения системы сравнений,
использующий Китайскую теорему об остатках
{возврат x ? [0, M –1], такого что
x mod mi = ai (1 ? i ? t)}
begin
for i : =1 to t do
Ni : = inv (Mi mod mi, mi);
x : = 0;
for i : =1 to t do
x : = [x + Mi ? Ni ? ai] mod n;
crt : = x {crt – результат}
end
Пример. Решить систему из двух сравнений
x ?1 (mod 5),
x ?10 (mod 11)
и найти общее решение x по модулю 55. Здесь m1=5; m1=11; M = m1 ? m2 = 5 ?11 = 55; a1 = 1; a2 = 10; M1 = M/m1 = m2 = 11; M2 =
M/m2 = m1 = 5.
Найдем значения N1 и N2, обратные к M1 и M2 соответственно по mod m1
и mod m2:
M1 ? N1 ?1 (mod m1), 11 ? N1 ?1 (mod 5) ? N1 =1,
M2 ? N2 ?1 (mod m2), 5 ? N2 ?1 (mod 11) ? N2 = 9.
Вычисляем общее значение
x = (a1 M1 N1 + a2 M2 N2) (mod N) = (1 ?11 ?1 +10 ? 5 ? 9)(mod 55) =
= (11 + 450)(mod 55) = 461 (mod 55) = 21 (mod 55).
Итак, x = 21 (mod 55).



Квадратичные вычеты
Рассмотрим некоторое простое p > 2 и число a < p. Если число a сравнимо с квадратом
некоторого числа x по модулю p, т.е. выполняется сравнение x2 ? a (mod p), тогда a называют
квадратичным вычетом по модулю p. В противном случае a называют квадратичным невычетом по
модулю p.
Если a – квадратичный вычет, сравнение x2 ? a (mod p) имеет два решения: +x и –x, т.е. a
имеет два квадратных корня по модулю p.
Все квадратичные вычеты находят возведением в квадрат элементов 1, 2, 3, ..., (p –1)/2.
Не все значения a < p являются квадратичными вычетами. Например, при p = 7 квадратич-
ные вычеты это 1, 2, 4:
12 = 1 ? (mod 7),
22 = 4 ? 4 (mod 7),
32 = 9 ? 2 (mod 7),
42 =16 ? 2 (mod 7),
52 = 25 ? 4 (mod 7),
62 = 36 ?1 (mod 7).
Заметим, что каждый квадратичный вычет появляется в этом списке дважды. Не существует
никаких значений x, которые удовлетворяли бы любому из следующих уравнений:
x2 ? 3 (mod 7),
x2 ? 5 (mod 7),
x2 ? 6 (mod 7).
Числа 3, 5 и 6 – квадратичные невычеты по модулю 7. Можно доказать, что существует точно (p –
1)/2 квадратичных вычетов по модулю p и (p –1)/2 квадратичных невычетов по модулю p.
Если a – квадратичный вычет по модулю p, то a имеет точно два квадратных корня: один
корень между 0 и (p –1)/2, другой корень между (p –1)/2 и (p –1).
Один из этих квадратных корней также является квадратичным вычетом по модулю p; он на-
зывается главным квадратным корнем.
Вычиcление квадратных корней при p=7 представлено в табл. П.4.
Таблица П.4
Корни
x2 ? a (mod 7)
x1 x2

2
1 ? 1(mod 7) +1 –1 = –1 + 7 = 6
+2 –2 = –2 + 7 = 5
2
2 ? 4(mod 7)
+3 –3 = –3 + 7 = 4
2
3 ? 2(mod 7)


Если n – произведение двух простых p и q, т.е. n = p ? q, то существуют точно
(p –1)(q –1)/4
квадратичных вычетов по модулю n, взаимно простых с n. Например, по модулю 35 (p = 5, q = 7, n =
5 ? 7 = 35) существуют
(5 ? 7)(7 ? 1) 4 ? 6
= =6
4 4
квадратичных вычетов: 1, 4, 9, 11, 16, 29, взаимно простых с 35.


Вычисления в конечных полях
Поле F есть множество, на котором определены операции сложения и умножения, удовле-
творяющие требованиям: ассоциативности, коммутативности, дистрибутивности, существования ад-
дитивного 0 и мультипликативной 1, аддитивных обратных и мультипликативных обратных для всех
элементов за исключением 0.
Конечное поле F(p) с конечным числом p элементов играет важную роль в криптографии.
В общем случае число эле-ментов
p = qn,
где q – некоторое простое число и n ?1. Такие конечные поля называют полями Галуа и обозначают
GF(qn) или GF(q) при n =1. (Эварист Галуа – французский математик начала XIX века.) Многие крип-
тосистемы базируются на полях Галуа GF(q), где q – большое простое число.
Пример. Поле Галуа GF(5) имеет элементы 0, 1, 2, 3, 4 и описывается таблицами сложения и умножения (табл. П.
5):
Таблица П.5
+ 0 1 2 3 4 х 1 2 3 4
0 0 1 2 3 4 1 1 2 3 4
1 1 2 3 4 0 2 2 4 1 3
2 2 3 4 0 1 3 3 1 4 2
3 3 4 0 1 2 4 4 3 2 1
4 4 0 1 2 3


Если q – простое число, то число a ? [1, q –1] является взаимно простым с q, и поэтому об-
ратный элемент a–1 имеет единственное значение. Тем самым однозначно определяется операция
деления.
Обозначим через GF*(q) множество всех ненулевых элементов поля GF(q). Некоторый эле-
мент g из GF*(q) называют образующим или порождающим элементом GF*(q), если для всех a из
GF*(q) найдется такое целое x, что gx = a mod q. Всего имеется ?(q –1) образующих элементов g.
Число x называют дискретным логарифмом элемента a по основанию g и модулю q. Вычисление
дискретных логарифмов (когда заданы g, a и q) примерно такая же труднорешаемая задача, как и
разложение на множители.
Еще один тип поля Галуа, используемый в криптографии, основывается на арифметике по
модулю неприводимых многочленов степени n, чьи коэффициенты – целые числа по модулю q, где
q – простое. Эти поля Галуа обозначают как GF(qn). Они имеют элементы, которые описываются
многочленами степени не выше (n –1) в форме
a (x) = an–1 Xn–1 +…+ a1 X + a0.
Каждый элемент a(X) является вычетом по модулю p(X), где p(X) – неприводимый многочлен
степени n (т.е. p(X) нельзя разложить на сомножители – многочлены степени меньше n).
Арифметические действия над коэффициентами ai выполняются по модулю q, а наивысшая
степень X равна (n –1), так как выполняется приведение по модулю многочлена p(X), имеющего
старшую степень n.
Особый интерес представляют поля GF(2n). Здесь коэффициентами ai являются 0 и 1. По-
этому многочлен a(X) степени не выше (n –1) можно представить как вектор из n двоичных цифр:
an–1 an–2 ... a1 a0.
Каждый из n-битовых векторов соответствует конкретному элементу поля GF(2n).
Например, поле Галуа GF(23) имеет элементы:
Многочлены Двоичная форма
0 000
1 001
x 010
x +1 011
x2 100
x2 +1 101
x2 + x 110
x2 + x +1 111
Организация вычислений в полях Галуа предполагает знание некоторых свойств многочленов
и их корней в двоичном поле GF(2). Кратко приведем некоторые из них
Свойство 1. Ненулевые элементы поля GF(2n) являются корнями обобщенного многочлена
n
?1
X2 +1.

<< Предыдущая

стр. 47
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>