Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Доказательство. Можем предполагать, что . Полагаем

Имеем

С другой стороны.

поэтому

или

Теорема 2. Пусть G = < G, , 1 > - конечная группа; а и b элементы группы G; t = ord b;

(1.2)

Тогда число l можно найти, выполнив не более чем операции умножения на элементы группы G.

Доказательство. Полагаем . Рассмотрим ряды

(1.3)

(1.4)

Если разрешимо относительно l, представим l в виде

Так как t = ord b, то b^' = b^xr+y = а в том и только в том случае, когда

, (1.5)

т.е. когда найдется элемент ряда (1.3), который совпадет с каким-нибудь членом ряда (1.4).

Нетрудно сосчитать число операций, позволяющих установить равенство (1.2). При вычислении элементов ряда (1.3) потребуется выполнить не более r-2 умножений. Для вычисления в силу следующей леммы

Лемма. Чтобы вычислить степень mⁿ , где m – элемент некоторого кольца, а n – натуральное число, достаточно выполнить не более умножений.

требуется выполнить не более чем умножений. И не более чем r - 1 умножений потребуется для вычисления всех членов ряда (1.4). Поэтому общее число операций для решения уравнения (1.2) не превосходит

Теорема 3. Пусть G = < G; •, 1 > - конечная группа; а и b -элементы группы G; t = ord b; b^'= a. И пусть, кроме того, число t составное:

Тогда дискретный логарифм элемента а по основанию b можно вычислить, выполнив не более чем за операций.

Доказательство. Нетрудно заметить, что любое целое число l с условием однозначно представимо в виде:

Равенство b^l = а можно записать в виде

(1.6)

Возводя обе части равенства (1.6) в степень r₁ и замечая, что t =r₁ r₂ , получим

А это удобно записать в виде

(1.7)

где .
Легко проверить, что ord b₁ = r₂. По теореме 2 дискретный логарифм a₁ по основанию b₁, т.е. m₁, можно вычислить при помощи не более чем операций. Из равенства (1.6) сразу получим

(1.8)

где

Аналогично, l₁ можно вычислить при помощи не более чем за операций. Далее, можно вычислить соответственно не более чем за

операций. Отсюда и следует наше утверждение.

Замечание. Здесь и дальше при подсчете числа операций, необходимых для вычисления индекса элемента конечного поля, учитываем только число умножений в конечном поле и не принимаем во внимание любые логические операции и операции в поле рациональных чисел, если такие потребуется выполнять.

Теорема 4. Пусть сохраняются условия теоремы 3. Если r₁ ,r_2, r₃ - натуральные (>1) числа, ord b = t и t = r₁ .r₂. r₃ , то для вычисления индекса элемента а при основании b достаточно выполнить не более

операций.

Доказательство. Пусть, как в теореме 3 b^l = а , и пусть l₁, m₁ - целые, тогда

Полагаем

Имеем

Обозначим

Получим

Оценим количество операций, достаточное для выполнения всех промежуточных шагов. При этом воспользуемся теоремами 2,3 и леммой:

Итак, общее число операций равно

Теорема 5. Если - есть произведение натуральных чисел, то решение уравнения (1. 1) можно найти, выполнив не более чем операций. При этом величины

определяются условиями:

Доказательство. Чтобы оценить верхнюю границу числа операций, достаточную для отыскания индекса а при основании b, как и ранее, представим число l в виде:

где m₁ и l₁ -целые с условиями

Тогда получим

Так как Введем обозначения:

Поэтому имеем

Далее находим

Полагаем теперь Тогда получим

Оценив количество операций, достаточное для выполнения всех промежуточных шагов, и применив индуктивное предположение, получим объявленный результат. [2]

Вопрос 9

Дискретный корень

Пусть G — некоторая конечная группа. Для а N, x  G положим f_a(x)=x^a. Рассмотрим обратную функцию f_a^-1(x)=x^1/a — дискретный корень.

Вычисление дискретных корней в Z_p*, где р — простое, не представляет трудностей. В самом деле, x^p-1=1 по Малой теореме Ферма, следовательно, x^1/a=x^c, где aс 1 (mod p-1). Таким образом, в качестве односторонней функции имеет смысл использовать возведение в степень только по составному модулю.[1]

Вопрос 10

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

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

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

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

Поскольку QR_p — группа, y^(p+1)/4QR_p. Заметим, что при p4k+3 квадратный корень можно найти, если известно какое-нибудь t Z_p\QR_p (квадратичный невычет по модулю р). Пусть n=p₁...p_l — составное, при этом простые делители p_i различны и разложение п известно. В этом случае у  QR_n тогда и только тогда, когда для любого i справедливо у_i=у mod p_i  QR_pi . При этом можно найти набор x_i  Z_pi* таких, что х_i² y_i (mod p_i), и скомбинировать из них с помощью теоремы 3.1 х  Z_n* — квадратный корень из у.

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

Если n=n₁n₂…n_k, n_i взаимно просты, то кольцо Z_n можно представить в виде прямой суммы колец Z_ni.

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

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

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

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

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

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

l-(log₂n)^-d

1. Выбрать случайно .

2. Найти х₁ —квадратный корень из х₀².

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

4. Положим a= x₀+x₁, b=x₀-x_{1 .}Отметим, что ab=x_Q²-x₁²0 (mod n), ab=kpq в Z, a0(mod n), b0 (mod n). Значит, a=k₀p, b=k_lq (либо наоборот).

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

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

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

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

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

Вопрос 11

Квадратичные вычеты

Определение. Если сравнение x ²  a (mod p ) имеет решения, то число а называется квадратичным вычетом по модулю р . В противном случае, число а называется квадратичным невычетом по модулю р .

Итак, если а – квадрат некоторого числа по модулю р , то а -“квадратичный вычет”, если же никакое число в квадрате не сравнимо с а по модулю р , то а - “квадратичный невычет”.

Пример. Число 2 является квадратом по модулю 7 , т.к. 4 ²  16 є 2(mod7). Значит, 2 - квадратичный вычет. (Сравнение x ²  2(mod7) имеет еще и другое решение: 3 ²  9  2(mod7).) Напротив, число 3 является квадратичным невычетом по модулю 7 , т.к. сравнение x ²  3(mod7) решений не имеет, в чем нетрудно убедиться последовательным перебором полной системы вычетов: x = 0,1,2,3,4,5,6.[4]

Характеристики

Список файлов ответов (шпаргалок)