В. Р. Гинзбург Перевод с английского

13.2. Китайская теорема об остатках
247
в диапазоне
−
n
+ 1
, . . . , n
−
1
. Единственным возможным значением такой
разности, кратным
n
, является
x
−
x
0
= 0
, или
x
=
x
0
. Это доказывает, что для
любой заданной пары
(
a, b
)
существует не более одного
x
, удовлетворяющего
условиям теоремы. Остается лишь найти значение
x
.
13.2.1
Формула Гарнера
Самым удобным способом вычисления
x
является так называемая
фор-
мула Гарнера (Garner’s formula)
:
x
= (((
a
−
b
)(
q
−
1
mod
p
)) mod
p
)
·
q
+
b.
Здесь множитель
(
q
−
1
mod
p
)
— это константа, которая зависит только
от
p
и
q
. Не забывайте, что мы можем выполнять деление по модулю
p
,
а значит, и вычислять
(1
/q
mod
p
)
, что является всего лишь другой формой
записи выражения
(
q
−
1
mod
p
)
.
Нам не нужно понимать, откуда взялась формула Гарнера; требуется
лишь доказать, что результат
x
правилен.
Вначале покажем, что
x
находится в диапазоне
0
, . . . , n
−
1
. Очевидно,
x
≥
0
. Значение
t
:= (((
a
−
b
)(
q
−
1
mod
p
)) mod
p
)
должно попадать в диапазон
0
, . . . , p
−
1
, так как является результатом вычисления по модулю
p
. Если
t
≤
p
−
1
, тогда
tq
≤
(
p
−
1)
q
и
x
=
tq
+
b
≤
(
p
−
1)
q
+ (
q
−
1) =
pq
−
1 =
n
−
1
.
Как видите, значение
x
действительно находится в диапазоне
0
, . . . , n
−
1
.
Теперь покажем, что найденное значение
x
дает правильный результат и
по модулю
p
, и по модулю
q
.
x
mod
q
= ((((
a
−
b
)(
q
−
1
mod
p
)) mod
p
)
·
q
+
b
) mod
q
= (
K
·
q
+
b
) mod
q
для некоторого
K
=
b
mod
q
=
b
Выражение
(((
a
−
b
)(
q
−
1
mod
p
)) mod
p
)
, которое умножается на
q
, — это
некоторое целое число
K
, но при выполнении операций по модулю
q
любое
кратное
q
можно отбросить. Вычислить
x
mod
p
немного сложнее.
x
mod
p
= ((((
a
−
b
)(
q
−
1
mod
p
)) mod
p
)
·
q
+
b
) mod
p
= (((
a
−
b
)
q
−
1
)
·
q
+
b
) mod
p
= ((
a
−
b
)(
q
−
1
q
) +
b
) mod
p
= (
a
−
b
) +
b
) mod
p
=
a
mod
p
=
a

248
Глава 13. Алгоритм RSA
В первой строке мы просто расписываем формулу
(
x
mod
p
)
. Во второй
избавляемся от нескольких лишних операторов mod
p
. Затем изменяем поря-
док умножения, что никак не сказывается на результате. (Возможно, вы еще
помните из школьного курса математики, что операция умножения облада-
ет ассоциативностью, т.е.
(
ab
)
c
=
a
(
bc
)
.) На следующем шаге мы замечаем,
что
(
q
−
1
q
) = 1(mod
p
)
, а потому можем избавиться и от этого множителя.
Оставшаяся часть преобразований тривиальна.
Это выведение намного сложнее, тех, которые встречались до сих пор,
особенно потому, что в нем используется больше алгебраических законов.
Если вы не совсем его поняли, не стоит беспокоиться.
Из всего сказанного выше следует, что формула Гарнера дает результат
x
, который лежит в нужном диапазоне и для которого
(
a, b
) = (
x
mod
p,
x
mod
q
)
. Поскольку мы уже знаем, что такое решение может быть только
одно, результат формулы Гарнера полностью решает китайскую теорему об
остатках.
В реальных системах значение
q
−
1
mod
p
обычно подсчитывают предва-
рительно, поэтому применение формулы Гарнера требует выполнения одного
вычитания по модулю
p
, одного умножения по модулю
p
, одного полного
умножения и одного сложения.
13.2.2
Обобщение
Китайская теорема об остатках справедлива и тогда, когда
n
является
произведением нескольких разных простых чисел
1
. Формулу Гарнера можно
обобщить, чтобы она распространялась и на подобные ситуации, но мы этого
делать не будем.
13.2.3
Использование
Так где же может пригодиться китайская теорема об остатках? Если вам
когда-нибудь понадобится выполнить множество вычислений по модулю
n
,
использование этой теоремы позволит сэкономить массу времени. Для числа
0
≤
x < n
назовем пару
(
x
mod
p, x
mod
q
)
представлением
x
по китайской
теореме об остатках или CRT-представлением
x
. Если мы представим
x
и
y
по
китайской теореме об остатках, тогда CRT-представление суммы
(
x
+
y
)
будет
иметь вид
((
x
+
y
) mod
p,
(
x
+
y
) mod
q
)
, что очень легко подсчитать, имея
CRT-представления
x
и
y
. Первый элемент этой пары
(
x
+
y
) mod
p
может
быть вычислен как
((
x
mod
p
)+(
y
mod
p
) mod
p
)
. Это просто сумма (по моду-
1
Существуют варианты китайской теоремы об остатках для
n
, которое делится на квад-
рат или более высокую степень некоторых простых чисел, но они еще более сложны.

13.2. Китайская теорема об остатках
249
лю
p
) первой половины каждого из CRT-представлений
x
и
y
. Аналогичным
образом вычисляется и второй элемент.
Точно так же можно выполнять и умножение. CRT-представлением чис-
ла
xy
будет пара
(
xy
mod
p, xy
mod
q
)
, элементы которой легко подсчитать,
зная CRT-представления
x
и
y
. Первый элемент
(
xy
mod
p
)
вычисляется пу-
тем перемножения значений
(
x
mod
p
)
и
(
y
mod
p
)
и последующего взятия
результата по модулю
p
. Аналогичным образом вычисляется и второй эле-
мент, только все операции выполняются по модулю
q
.
Пусть
k
— количество бит числа
n
. Каждое из простых чисел
p
и
q
имеет
длину примерно
k/
2
бит. Выполнение одной операции сложения по модулю
n
требует одного
k
-битового сложения, за которым может последовать одно
k
-битовое вычитание, если полученная сумма окажется больше
n
. При ис-
пользовании CRT-представления, в свою очередь, требуется проделать две
операции сложения по модулю над числами, длина которых примерно в два
раза меньше. Это практически тот же объем работы, что и в первом случае.
Значительный выигрыш от использования CRT-представлений можно по-
лучить при выполнении умножения. Умножение двух
k
-битовых чисел тре-
бует намного больше работы, чем два умножения двух
k/
2
-битовых чисел.
В большинстве реализаций умножение с применением CRT-представлений
будет выполняться в два раза быстрее, чем полное умножение. Это весьма
ощутимая экономия времени.
Еще более существенный результат может быть достигнут при возведении
в степень. Предположим, необходимо вычислить
x
s
mod
n
. Показатель сте-
пени
s
может быть до
k
бит длиной. Непосредственное возведение в степень
требует выполнения около
3
k/
2
умножений по модулю
n
. При использовании
CRT-представлений каждая операция умножения выполняется быстрее, но
это еще не все. Мы хотим вычислить
(
x
s
mod
p, x
s
mod
q
)
. Работая по модулю
p
, мы можем сократить показатель
s
по модулю
(
p
−
1)
. Аналогичная опера-
ция может быть выполнена и по модулю
(
q
−
1)
. Таким образом, останется
вычислить лишь
(
x
s
mod (
p
−
1)
mod
p, x
s
mod (
q
−
1)
mod
q
)
. Каждый из показате-
лей степени будет иметь длину лишь
k/
2
бит, а потому каждое возведение
в степень потребует только
3
k/
4
операции умножения. Вместо выполнения
3
k/
2
умножений по модулю
n
нам придется выполнить
2
·
3
k/
4 = 3
k/
2
умно-
жений по модулю одного из простых чисел
p
и
q
. В стандартной реализации
это позволит сократить объем работы в 3-4 раза.
Издержками использования CRT-представлений являются лишь дополни-
тельная сложность программного обеспечения и необходимость выполнения
преобразований. Если одно вычисление включает в себя более нескольких
операций умножения, тогда затраты на выполнение преобразований окупят-
ся сполна. В большинстве учебников по криптографии китайская теорема
об остатках упоминается лишь как один из приемов реализации алгоритма

250

жүктеу/скачать 2,74 Mb.

Достарыңызбен бөлісу: