Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Следует однако заметить, что, упрощая описание алгоритма, мы пожертвовал* эффективностью!
При эффективной реализации на выполнение всех операций на шагах 3 и можно затратить OB((logn)2) единиц времени. Эта ситуация совершенно аналогична эффективному вычислению наибольшего общего делителя, основанному
Глава 6. Теория чисел
233
Алгоритм 6.2. Символ Якоби
ВВОД: нечетное целое число п > 2, целое число х € Ъ*п ВЫВОД:
Jacobi(a;,n)
1. if (х == 1) return (1);
2. if (2
а) if (2 I (n2 - l)/8) return (JacoU(x/2,n));
б) return (—Jacobi(a;/2,n));
(* Далее число x считается нечетным *)
3. if (2 I (x — l)(n— l)/4) return (Jacobi(nmoda;,a;));
4. return (— Jacobi(nmodx, x)).
на формуле (4.3.12). Следовательно, для х € Z* символ Якоби (^) можно вычислить за OB((logn)2) единиц времени. Эффективная модификация алгоритма 6.2 описана в части I книги [79].
В сравнении со сложностью критерия Эйлера (5.4.5), имеющего временную сложность OB((logp)3), сложность распознавания квадратичного вычета по простому модулю р в logp раз меньше.
Пример 6.5. Покажем, что 384 6 QNR443.
Отслеживая алгоритм 6.2 шаг за шагом, получаем следующее.
Jacobi(384,443) = - Jacobi(192,443) = = - ,Tacobi(96,443) = = - Jacobi(48,443) = = - Jacobi(24,443) = = - Jacobi(12,443) = = - Jacobi(6,443) = = - Jacobi(3,443) = = Jacobi(2,3) = = — Jacobi(l,3) = - -1.
Следовательно, 384 6 QNR443. ?
В заключение необходимо заметить, что для вычисления символа Якоби с помощью алгоритма 6.2 не обязательно знать разложение числа п. Это очень важ-
234
Часть II. Математические основы
ное свойство, которое широко применяется в криптографии с открытым ключом, например, в криптосистеме Голдвассера-Микали (14.3.3) и протоколе подбрасывания монеты Блюма (глава 19).
6.6 Квадратные корни по целочисленному модулю
В примере 6.2 мы вычислили квадратный корень по целочисленному модулю. Однако процедуру, которая там описана, нельзя считать алгоритмом, поскольку она использовала изоморфизм между группой и полем, позволивший свести сложную задачу к тривиальной: вычислению квадратных корней единицы и четырех, которые оказались квадратами в поле Z. Эта задача вполне по силам даже школьникам начальных классов. Как правило, такой изоморфизм неизвестен, и существует громадное количество случаев, когда образ числа при изоморфизме не является квадратом в поле Z.
Рассмотрим алгоритмы вычисления квадратных корней по целочисленному модулю. Начнем с простых модулей. По следствию 6.2 два корня квадратичных вычетов являются взаимно дополнительными по простому модулю. Значит, достаточно рассмотреть проблему вычисления одного из квадратных корней квадратичного вычета.
Для большинства нечетных чисел задача очень проста. В частности, к ним относятся простые числа р, такие как р = 3,5,7(mod8).
6.6.1 Вычисление квадратных корней по простому модулю
Вариант р = 3,7(mod8).
В данном случае число р + 1 делится на 4. Введем следующее обозначение для числа a G QRp.
def ?±i, , ч х = а * (modp).
Затем, поскольку а^р_1^2 = l(modp),
х2 = а^'2 = а("-1>/2а = a(mod р).
Итак, действительно, число х является квадратным корнем числа а по модулю р.
Вариант р = 5 (mod 8).
В данном случае число р + 3 делится на 8. Поскольку число (р — 1)/2 является четным, число —1 удовлетворяет критерию Эйлера и является квадратичным
Глава 6. Теория чисел
235
вычетом. Введем следующее обозначение для числа а € QRp-
х ^ а2^- (modp) (6.6.1)
Из условия а(р-1)/2 = l(modp) следует, что а^-1^/4 ее ±l(modp), поскольку в поле Z* число 1 имеет два квадратных корня: 1 и —1. Следовательно,
х2 = а(р+3)/4 ее аЬ-^а = ±a(modp).
Иначе говоря, мы доказали, что число х, определенное по формуле (6.6.1), является квадратным корнем либо числа а, либо числа —а. Если число положительное, алгоритм завершен. Если число отрицательное, то
—х2 = (л/—1х)2 ее a(modp).
Следовательно, число
х *f у/^Ла^ (modp) (6.6.2)
является искомым. Итак, задача сводится к вычислению у7- l(modp). Пусть число Ъ — произвольный квадратичный невычет по модулю р. Тогда по критерию Эйлера
(Ь(р-1)/4)2 = ь(р-1)/2 = _1(modp)j
следовательно, вместо числа можно применять число o(p-1)/4(modp). Кстати, поскольку
р2 - 1 = (р + 1 )(р - 1) = (8А; + 6)(8Jfc + 4) = 8(4Jt' + 3)(2к" + 1),
правая часть равенства является результатом умножения нечетного числа на 8. Следовательно, по теореме 6.16.6 выполняется условие 2 € QNRp. Иначе говоря, если р ее 5(mod8), вместо числа можно использовать число г^-1^4. Тогда формула (6.6.2) преобразуется в следующую.
2(p-D/4a(p+3)/8 _ (4a)(P+3)/8/2(modр) (6 6 3)
Используя правую часть формулы (6.6.3), мы можем сэкономить одну операцию возведения в степень по модулю.
Временная сложность алгоритма 6.3 имеет порядок C>B((logp)3).
236
Часть II. Математические основы
Алгоритм 6.3. Квадратный корень по модулю р ее 3,5,7(mod 8)
ВВОД: простое число р, удовлетворяющее условию р = 3,5,7(mod 8); целое число a G QRp.
ВЫВОД: квадратный корень числа а по модулю р.
1. if (р = 3,7(mod8)) return (a(P+1)/4(modp)); (* Далее считаем, что р ее 5(mod8). *)
