Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
В главе 4 показана важная роль, которую малая теорема Ферма играет при вероятностной проверке простоты числа, часто применяемой при генерации ключей во многих криптографических системах и протоколах с открытым ключом. В свою очередь, теорема Эйлера нашла применение в криптосистеме RSA, описанной в разделе 8.5.
228
Часть II. Математические основы
6.5 Квадратичные вычеты
Квадратичные вычеты играют важную роль в теории чисел. Например, алгоритмы разложения целого числа на множители непременно используют квадратичные вычеты. Кроме того, квадратичные вычеты широко применяются при шифровании и в криптографических протоколах.
Определение 6.1 (Квадратичный вычет). Пусть л — целое число ип> 1. Число а из группы Z* называется квадратичным вычетом по модулю п (quadratic residue modulo п), если в группе "Ln существует число х, удовлетворяющее условию х2 = a(mod п); в противном случае число а называется квадратичным невычетом по модулю п (quadratic non-residue modulo п). Множество квадратичных вычетов по модулю п обозначается как QRn, а множество квадратичных невычетов по модулю п — как QNRn.
Пример 6.4. Вычислим QRn — множество всех квадратичных вычетов по модулю 11. QRn = {l2,22,32,42,52,б2,72,82,92,102} (mod 11) = {1,3,4,5,9}.
В нашем примере мы вычислили множество QRn путем полного перебора элементов группы Читатели могут самостоятельно убедиться в том, что
QRU = {12,22,32,42,52} (mod 11),
те. достаточно было возвести в квадрат по модулю 11 лишь половину элементов группы Щг. Этот факт обобщается в следующей теореме.
Теорема 6.12. Пусть р — простое число. Тогда справедливы следующие утверждения.
1. QRp = {a;2(modp) | 0 < х ^ (р - 1)/2}.
2. Существует ровно (р—1)/2 квадратичных вычетов и (р—1)/2 квадратичных невычетов по модулю р, т.е. группа Z* разбивается на два подмноже-{ ства, QRp и QNRp, состоящие из одинакового количества элементов.
Доказательство. Докажем первое утверждение. Очевидно, что S = {ж2(modp) | О < х ^ (р — 1)/2} С QRp. Для того чтобы показать, что QRp = S, достаточно доказать, что QRp С S.
Возьмем произвольное число а € QRp. Тогда существует число х < р, удовлетворяющее условию х2 = a(modp). Если х ^ (р — 1)/2, то a G S. Допустим, что х > (р— 1)/2. Тогда у = р — х ^ (р— 1)/2 и у2 = (р — х)2 =р2 - 2рх + х2 = х2 = = a(modp). Следовательно, QRp С S.
Докажем второе утверждение. Для того чтобы показать, что #QRp = (р—1 )/2,, достаточно доказать, что для всех чисел х, удовлетворяющих неравенству 0 < х < у ^ (р — 1)/2, выполняется условие ж2 ^у2 (modp). Предположим противное:
Глава 6. Теория чисел
229
х2 — у2 = (х + у){х — у) = O(modp). Следовательно, р \ х + у или р \ х — у. Поскольку х + у < р, возможен лишь последний вариант. Итак, х = у, что противоречит условиям теоремы.
Отсюда следует, что #QNRp = (р - 1)/2, поскольку #QNRp = Zp\QRp
H#z; = p-i. ?
Следствие 6.2. Пусть р — простое число. Тогда любое число а € QRp имеет ровно два квадратных корня по модулю р. Обозначим один из них буквой х, тогда второй корень равен —х{= р — х). ?
6.5.1 Задача о квадратичных вычетах
Часто возникает необходимость определить, является ли число п квадратичным вычетом по заданному модулю. Эта проблема называется задачей о квадратичных вычетах (quadratic residuosity problem).
Теорема 6.13 (Критерий Эйлера). Пусть р — простое число. Для любого числа х € Z* условие х € QRp выполняется тогда и только тогда, когда
х(р-т = Цто^р). (6.5.1)
Доказательство. (=>) Для числа х € QRp существует число у € Z*, такое что у2 ее x(modp). Тогда из теоремы Ферма (теорема 6.10) следует, что ж^р_1^2 = = yp_1 - l(modp).
(<=) Пусть a;(p-1)/2=l(modp). Тогда число х является корнем полинома у(р-1)/2— — 1 = 0(modp). Заметим, что группа Zp является полем. По теореме 5.9.3 (раздел 5.4.3) каждый элемент этого поля является корнем полинома ур—y=0(modp). Иначе говоря, каждый ненулевой элемент этого поля (т.е. каждый элемент группы Zp) является корнем полинома
yP-i _ 1 = (y(P-D/2 - l)^-1)/2 + 1) ее 0(modp).
Все эти корни отличаются друг от друга, поскольку полином, имеющий степень р — 1, может иметь не более р — 1 корней. Следовательно, все (р — 1)/2 корней полинома у(Р~1У2 — 1 ее 0(modp) должны быть разными. В ходе доказательства теоремы 6.12 было показано, что множество QRp содержит ровно (р — 1)/2 элементов, каждый из которых удовлетворяет условию у(р-1)/2—l=0(modp). Любой другой элемент группы Z* должен быть корнем уравнения y^p_1^2-l-l=0(modp). Следовательно, х € QRp. ?
Доказывая теорему 6.13, мы убедились, что если для х € Zp критерий не выполняется, то
ж(Р-1)/2 s _i(modp). (6.5.2)
230
Часть II. Математические основы
Критерий Эйлера позволяет проверить, является ли элемент группы Z* квадратичя ным вычетом: если условие (6.5.1) выполняется, то х € QRp, в противном случае^ выполняется условие (6.5.2) ихЕ QNRp.
Пусть тг — составное натуральное число, имеющее следующее разложение на простые множители:
n = tftf...p2. (6.5.3)
Тогда по теореме 6.8 группа 7Ln изоморфна пространству х Zp»2 х ... xJ х Zpefc. Поскольку изоморфизм сохраняет свойства арифметических операций,] справедлива следующая теорема.
