Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
2. if (а*?-1)/4 = l(modp)) return (a<P+3>/8(modp));
3. return ((4g)(p+3)/8/2).
Вычисление квадратных корней по простому модулю в общем случае
Описываемый ниже метод предложен Шенксом (Shanks) (см. раздел 1.5.1 в книге [179]).
Для произвольного простого числа р справедлива формула
Р-1-2е9,
где q — нечетное число, причем е > 1. По теореме 5.2 (раздел 5.2.3) циклическая группа Z* имеет единственную циклическую подгруппу G порядка 2е. Очевидно, порядки квадратичных вычетов в подгруппе G представляют собой степень числа 2, поскольку эти вычеты являются делителями числа 2е-1. Если а € QRp, то, поскольку
= (а9)2*"1 ее l(modp),
число a9(modp) принадлежит группе G и, разумеется, является квадратичным вычетом. Следовательно, существует четное число к, удовлетворяющее условию О ^ к < 2е, такое что
aqgk ее l(modp), (6.6.4)
где число д является порождающим элементом группы G. Допустим, что нам известны числа дик. Тогда, полагая
def Я±! Ь. х = а 2 52}
легко убедиться, что х2 ее a(modp).
Итак, задача сводится к двум подзадачам: 1) найти порождающий элемент д группы G и 2) найти наименьшее неотрицательное четное число к, удовлетворяющее условию (6.6.4).
Первая подзадача довольно проста. Для любого числа / G QNRp, поскольку число q — нечетное, /9 G QNRp и ordp(/9) = 2е, число fq является порождающим элементом группы G. Найти число / сравнительно легко. Для этого достаточно
Глава 6. Теория чисел
237
извлечь случайный элемент / е Z* и проверить условие (p-J = —1, используя алгоритм 6.2. Поскольку половина элементов поля Z* является квадратичными невычетами, вероятность найти искомое число равна 1/2.
Решение второй подзадачи также не вызывает особых затруднений. Число к, удовлетворяющее условию (6.6.4), можно быстро найти, используя тот факт, что порядки неединичных квадратичных вычетов в группе G являются степенями числа 2. Итак, положив
b = aq = сРд2* (mod р), (6.6.5)
приходим к выводу, что Ъ G G. Теперь можно найти наименьшее целое число тп, удовлетворяющее условию 0 ^ тп < е, такое что
о2™ = l(modp), (6.6.6)
и модифицировать число Ъ следующим образом:
Ь «- Ьд^~т = oV""™(modр). (6.6.7)
Заметим, что после модификации (6.6.7) порядок числа Ъ уменьшается по сравнению с определением (6.6.5). При этом число Ъ остается квадратичным вычетом в группе G, а уменьшенный порядок продолжает быть степенью числа 2. Следовательно, скорость убывания порядка является степенью числа 2, и после повторных вычислений по формулам (6.6.6) и (6.6.7) число т в выражении (6.6.6) значительно уменьшается. Если в выражении (6.6.6) т = 0, то Ъ = 1, и, следовательно, формула (6.6.7) сводится к формуле (6.6.4), а число к можно найти, накапливая степень 2т на каждом шаге итерации. Количество итераций не превышает числа е.
Итак, теперь можно сформулировать следующий алгоритм.
Поскольку е < log2p, временная сложность этого алгоритма имеет порядок OB((bgp)4).
Примечание 6.2. Для упрощения изложения мы следовали принципам, предложенным Шенксом, в частности, при поиске четной степени числа к (вторая подзадача). Это не самый эффективный способ решения задачи. Явного определения числа к можно избежать, вычислив число дк^2 в качестве побочного результата выполнения шага 3. Такой подход позволяет сэкономить одну операцию возведения в степень по модулю на шаге 4. Оптимизированный вариант алгоритма Шенкса приведен в книге [179] (алгоритм 1.5.1). ?
В заключение отметим, что все три варианта алгоритма 6.3 являются частными случаями алгоритма 6.4.
238
Часть II. Математические основы
Алгоритм 6.4. Квадратный корень по простому модулю ВВОД: простое число р; целое число а Е QRp. ВЫВОД: квадратный корень числа а по модулю р.
1. (* Инициализация *)
Положим р— 1 = 2eq, где число q — нечетное; Ъ <— aq(modр); г <— е; к <— 0.
2. (* Подзадача 1, применяется алгоритм 6.2. *) Находим / G QNRp;# <- /9(modp).
3. (* Подзадача 2, находим четную степень числа к. *) while (Ь ф 1) do
а) Найти наименьшее неотрицательное целое число т, удовлетворяющее условию b2™ = l(modp).
б) Ь «- by2r"m(modp); ч- + 2r-m; г «- m.
4. return (a^+1>/2pfc/2(modp)).
6.6.2 Вычисление квадратных корней по составному модулю
Благодаря теореме 6.8 мы знаем, что, если п = pq, где pnq — простые числа, группа Z* изоморфна пространству Z* х Z*. Поскольку изоморфизм сохраняет свойства арифметических операций, отношение
х2 ее y(mod п)
выполняется тогда и только тогда, когда оно справедливо как по модулю р, так и по модулю q. Следовательно, если известно разложение числа п на множители, квадратный корень по модулю п можно вычислить с помощью следующего алгоритма.
Алгоритм 6.5. Квадратный корень по составному модулю
ВВОД: простые числа р, q, удовлетворяющие условию п = pq; целое число у € QR„.
ВЫВОД: квадратный корень числа у по модулю п.
1. хр «- y/y(modp);
xq <— \Jy{modq); (* Применяем алгоритмы 6.3 или 6.4. *)
2. return (ipXp + lpa;p(modn)). (* Применяем алгоритм 6.1. *) Очевидно, что временная сложность алгоритма 6.5 имеет порядок C>B((log п)4).
Глава 6. Теория чисел
