Вопрос 10 Квадратный корень по составному модулю (функция Рабина)

Специальный случай дискретного корня — квадратный корень в Zn*. Рассмотрим функцию f: Zn*Zn*, f(x)=х 2 ; f(Zn*)=QRn — группа квадратичных вычетов по модулю п. Каждый квадратичный вычет может иметь несколько квадратных корней в Zn . Если х — квадратный корень из у, то п-х — тоже квадратный корень из y.

Если р — простое число, то Zp * — циклическая группа. Элемент у  Zp * тогда и только тогда является квадратичным вычетом по модулю р, когда y = g t , где g — образующий элемент Zp * , a t — четное. Эквивалентное условие формулируется через символ Лежандра (Якоби) . Значит, квадратичных вычетов вZp * ровно половина и каждый из них имеет два квадратных корня:

Если к тому же p=4k+3, то — нечетно и ровно один из корней является квадратичным вычетом (какой именно — зависит от четности t /2). Он называется главным квадратным корнем и равен x=y ( p +1)/4 ,

Поскольку QRp — группа, y ( p +1)/4 QRp.Заметим, что при p4k+3 квадратный корень можно найти, если известно какое-нибудь tZp\QRp (квадратичный невычет по модулю р). Пусть n=p1. pl — составное, при этом простые делители pi различны и разложение п известно. В этом случае у  QRn тогда и только тогда, когда для любого i справедливо уi=у mod pi  QRpi . При этом можно найти набор xi Zpi* таких, что хi 2  yi (mod pi), и скомбинировать из них с помощью теоремы 3.1 х  Zn* — квадратный корень из у.

Теорема Китайская теорема об остатках.

Если n=n1n2…nk, niвзаимно просты, то кольцоZn можно представить в виде прямой суммы колецZni.

Группа QRn содержит (n) 2 - l элементов, где (n) — функция Эйлера, количество элементов в Zn*. Каждый элемент из QRn имеет 2 l квадратных корней.

Определение, n — число Блума (или Блама, В1ит), если п=р1 . рl, pi — различные простые числа, и для всех i выполнено pi mod 4=3.

Для любого у  QRn , где п — число Блума, ровно один из квадратных корней из у, а именно тот, для которого все xi  QRn, сам является квадратичным вычетом и называется главным квадратным корнем из у.

Теорема. Если n=pq, p и q — различные простые числа, то умение вычислять квадратный корень по модулю n позволяет разложить n на множители.

Доказательство. Пусть имеется полиномиальный алгоритм вычисления требуемого квадратного корня по модулю п. Построим вероятностный полиномиальный алгоритм разложения n на множители.

Имеется в виду, что наш алгоритм будет иметь доступ к некоторому источнику случайности и среднее время его работы будет ограничено (log2n) c для некоторой константы с. Дня любой константы d можно модифицироватьалгоритм так, чтобы он всегда завершался за время (log2n) c для некоторой константы с и выдавал правильный ответ с вероятностью не меньше

Найти х1 —квадратный корень из х0 2 .

Если x0+x10(modn) или x0-x10(modn), повторить попытку, начиная с шага 1. Поскольку х0 2 имеет четыре квадратных корня и два из них подходят, вероятность удачного выбора x0 ограничена снизу константой, не зависящей от п.

Положим a= x0+x1, b=x0-x1 .Отметим, что ab=xQ 2 -x1 2 0 (mod n), ab=kpq в Z, a0(mod n), b0 (mod n). Значит, a=k0p, b=klq (либо наоборот).

Найти р и q с помощью алгоритма Евклида как наибольшие общие делители а или b и n.

Теорема. Если n — число Блума и факторизация трудновычислима, то операция возведения в квадрат по модулю р является односторонней перестановкой QRn.

Доказательствопредставляет собой обобщение изложенного выше.

Более того, утверждается, что, не зная разложения п на множители, трудно вычислить даже младший бит квадратного корня. Имеется в виду, что если существует вероятностный полиномиальный алгоритм для угадывания этого бита с вероятностью, не меньшей ½+q(log2 n) -1 , где q — многочлен, то существует такой алгоритм и для разложения числа Блума на множители.

Функцией Рабина (Rabiri) называется функция возведения в квадрат по модулю n=pq, где р и q — простые числа. Чтобы затруднить факторизацию, накладывается дополнительное условие, что р и q состоят каждое из (log2 n)/2 битов.[1]