Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Теорема 6.14. Пусть п — составное целое число с полным разложением (6.5.3/.* Следовательно, a;GQRn тогда и только тогда, когда ^(modp^) eQRp«4 т.е. то-{ гда и только тогда, когда x(modpi) € QRpi, где pi,i = 1,2,...,k — простые числа. ?
Следовательно, при известном разложении числа тг число х G Z* представляет собой квадратичный вычет по модулю п, если число a;(modp) является квадра-у тичным вычетом для каждого простого числа р, удовлетворяющего условию р | nJ
Однако если разложение числа тг неизвестно, определить, является ли число квадратичным вычетом по модулю тг, довольно трудно.
Определение 6.2 (Задача о квадратичном вычете (задача QRP)).
ВВОД: тг: составное число;
хеК-
ВЫВОД: ДА, если х G QR„.
Задача QRP представляет собой хорошо известную трудноразрешимую задач теории чисел и принадлежит к числу четырех алгоритмических задач, рассмотренных Гауссом в его работе "Disquisitiones Arithmeticae" [119]. Эффективное решение этой задачи зависит от решения других открытых проблем теории чи-f сел. В главе 14 будет описана популярная криптосистема Голдвассера-Микал'* (Goldwasser-Micali). Безопасность этой криптосистемы гарантируется сложно^ стью решения задачи QRP.
Теорема 6.15. Пусть п — составное число, имеющее k > 1 простых множи{ телей. Тогда ровно ^-я часть элементов группы Z* является квадратичны* вычетом по модулю п.
Итак, для составного числа п эффективный алгоритм для распознавания квад ратичного вычета по модулю тг образует основу эффективной статистическое проверки доли квадратичных вычетов в группе Z*, и, следовательно, теорема 6.15
Глава 6. Теория чисел
231
позволяет создать эффективный алгоритм для ответа на вопрос, имеет ли число п два или три разных простых множителя. Если число п имеет два разных простых множителя, то квадратичными вычетами являются ровно четверть элементов группы Z*, а если три — одна восьмая их количества. Следовательно, существует возможность распознать ансамбли E^-Prime и Es-Prime (см. раздел 4.7).
В настоящее время не известно ни одного алгоритма, позволяющего распознать квадратичные вычеты по модулю п при неизвестном разложении числа п за время, полиномиально зависящее от размера числа п.
6.5.2 Символы Лежандра-Якоби
Для распознавания квадратичного вычета с помощью критерия Эйлера (6.5.1) приходится интенсивно выполнять операцию возведения в степень по модулю. Однако эту задачу можно решить намного быстрее. Этот алгоритм использует символы Лежандра и Якоби (Legendre-Jacobi).
Определение 6.3 (Символы Лежандра и Якоби). Для каждого простого числа р и числа х € Z* символом Лежандра числа х по модулю р называется значение, вычисляемое по следующему правилу.
(х\ def J 1, если х € QRp, р) если х € QNRp.
Пусть п - р\Р2 ¦ --Pk —разложение числа п на простые множители (некоторые из этих множителей могут повторяться). Число
(х\ def / х \ ( х\ ( х\ \п) \pi) \p2j"\PkJ
называется символом Якоби числа х по модулю п.
В оставшейся части книги обозначение (|) всегда будет относиться к символу Якоби, независимо от того, является ли число Ь простым.
Если число р — простое, сравнивая формулы (6.5.1) и (6.5.2) с определением 6.3, получаем
= rcfr-W^modp). (6.5.4)
Теорема 6.16. Символ Якоби имеет следующие свойства
232
Часть II. Математические основы
3. (JL) = (?) (?).
\тпу \mJ \nJ
4. Если х = 2/(modп), то (—^ = (—
Далее числа тип считаются нечетными числами.
-1)—.
7. Если gcd(m, n) = 1 и числа т, п > 2, /по (—^ (—^ = (— 1)
(,п-1)(п-1) 4
Утверждения 6.16.1-6.16.4 непосредственно следуют из определения символа Якоби. Доказательство утверждений 6.16.5-6.16.7 не требует применения особых методов. Однако эти доказательства довольно громоздки и выходят за рамки книги. Любознательные читатели могут найти их в любом учебнике по теории чисел (например, [170, 176]).
Утверждение 6.16.7 известно под названием закона квадратичной взаимнс ста Гаусса (Gauss' Law of Quadratic Reciprocity). Благодаря этому закону совсем нетрудно доказать, что вычисление символа Якоби (^), где gcd(x,n) = 1, рав! носильно вычислению наибольшего общего делителя, и, следовательно, имеет ту же временную сложность.
Примечание 6.1. При вычислении символа Якоби по теореме 6.16 вычислений правых частей в утверждениях 6.16.1-6.16.7 должно выполняться без возведеХ ния в степень. Поскольку ord(—1) = 2 (при умножении), требуется лишь провеА рить равенство степеней. В алгоритме 6.2 эти вычисления сводятся к проверке факта, что эти степени делятся на число 2.
Алгоритм 6.2 позволяет вычислить символ Якоби, используя его свойства, перечисленные в теореме 6.16.
В алгоритме 6.2 каждый рекурсивный вызов функции Jacobi, зависящей от двух аргументов, либо делит первый аргумент на два, либо делит второй аргумег на первый по модулю х. Следовательно, алгоритм выполняет не более log2 п вызс вов, пока первый аргумент не уменьшится до единицы. Строго говоря, поскольк каждая арифметическая операция по модулю имеет сложность Ов((1о§и)2), н| выполнение алгоритма 6.2 затрачивается Og((logn)3) единиц времени.
