23. Задача дискретного логарифмирования

Задача дискретного логарифмирования заключается в том, чтобы по данным целым , , решить уравнение:

где и — взаимно просты (примечание: если они не взаимно просты, то описанный ниже алгоритм является некорректным; хотя, предположительно, его можно модифицировать, чтобы он по-прежнему работал).

Здесь описан алгоритм, известный как "baby-step-giant-step algorithm", предложенный Шэнксом (Shanks) в

1971 г., работающий за время за . Часто этот алгоритм просто называют алгоритмом "meet-in-the-middle" (потому что это одно из классических применений техники "meet-in-the-middle": "разделение задачи пополам").

Алгоритм

Итак, мы имеем уравнение:

где и взаимно просты. Преобразуем уравнение. Положим

где — это заранее выбранная константа (как её выбирать в зависимости от , мы поймём чуть позже). Иногда называют "giant step" (поскольку увеличение его на единицу увеличивает сразу на ), а в противоположность ему — "baby step".

Очевидно, что любое (из промежутка — понятно, что такого диапазона значений будет достаточно) можно представить в такой форме, причём для этого будет достаточно значений:

Тогда уравнение принимает вид:

откуда, пользуясь тем, что и взаимно просты, получаем:

Чтобы решить исходное уравнение, нужно найти соответствующие значения и , чтобы значения левой и правой частей совпали. Иначе говоря, надо решить уравнение:

Эта задача решается с помощью метода meet-in-the-middle следующим образом. Первая фаза алгоритма: посчитаем значения функции для всех значений аргумента , и отсортируем эти значения. Вторая фаза

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

24. Алгоритм Евклида

Алгоритм Евклида позволяет найти наибольший общий делитель двух многочленов, т.е. многочлен наибольшей степени, на который делятся без остатка оба данных многочлена. Алгоритм основан на том факте, что для любых двух многочленов от одного переменного, f(x) и g(x), существуют такие многочлены q(x) и r(x), называемые соответственно частное и остаток, что

f(x) = g(x)∙q(x) + r(x), (*)

при этом степень остатка меньше степени делителя, многочлена g(x), и, кроме того, по данным многочленам f(x) и g(x) частное и остаток находятся однозначно. Если в равенстве

(*) остаток r(x) равен нулевому многочлену (нулю), то говорят, что многочлен f(x) делится на g(x) без остатка.

Алгоритм состоит из последовательного деления с остатком сначала первого данного многочлена, f(x), на второй, g(x):

f(x) = g(x)∙q1(x) + r1(x), (1)

затем, если r1(x) ≠ 0, – второго данного многочлена, g(x), на первый остаток – на многочлен r1(x):

g(x) = r1(x)∙q2(x) + r2(x), (2)

далее, если r2(x) ≠ 0, – первого остатка, r1(x), на второй остаток, r2(x): r1(x) = r2(x)∙q3(x) + r3(x), (3)

затем, если r3(x) ≠ 0, – второго остатка на третий:

r2(x) = r3(x)∙q4(x) + r4(x), (4)

и т.д. Поскольку на каждом этапе степень очередного остатка уменьшается, процесс не может продолжаться бесконечно, так что на некотором этапе мы обязательно придем к ситуации, когда очередной, n + 1-й остаток rn + 1 равен нулю:

rn–2(x) = rn–1(x)∙ qn(x) + rn(x),	(n)
rn–1(x) = rn(x)∙ qn+1(x) + rn+1(x),	(n+1)
rn+1(x) = 0.	(n+2)

Тогда последний не равный нулю остаток rn и будет наибольшим общим делителем исходной пары многочленов f(x) и g(x).

Действительно, если в силу равенства (n + 2) подставить 0 вместо rn + 1(x) в равенство (n + 1), затем – полученное равенство rn – 1(x) = rn(x)∙qn + 1(x) вместо rn – 1(x) – в равенство

(n), получится, что rn – 2(x) = rn(x)∙qn + 1(x) qn(x) + rn(x), т.е. rn – 2(x) = rn(x)( qn + 1(x) qn(x) + 1),

и т.д. В равенстве (2) после подстановки получим, что g(x) = rn(x)∙Q(x), и, наконец, из равенства (1) – что f(x) = rn(x)∙S(x), где Q и S – некоторые многочлены. Таким образом, rn(x) – общий делитель двух исходных многочленов, а то, что он наибольший (т.е.

наибольшей возможной степени), следует из процедуры алгоритма.

Если наибольший общий делитель двух многочленов не содержит переменную (т.е. является числом), исходные многочлены f(x) и g(x) называются взаимно-простыми.

25. Теорема Эйлера

Если у нас есть два числа M и n, где M < n, а также что очень важное чтобы данные числа были взаимно простыми, то выполняется соотношение. M^(j(n)) = 1 (mod n). В данной формуле мы вычисляем значение степени для числа M равной функции Эйлера для n. В качесте числа M мы возьмем исходное сообщение которое мы хотим зашифровать. Для того чтобы обеспечить взаимную простоту чисел M и n, следует выбирать число n, равным произведенную двух больших простых множителей. Надеюсь, вы помните что число является простым если оно не имеет других делителей кроме себя и единицы. Предполагается, что если n = p*q, где p и q являются большими простыми числами, то вероятность того что случайное сообщение M будет делителем n, т.е. не будет взаимно простым с данным числом, будет достаточно мала и ей можно пренебречь. В алгоритме RSA в качестве односторонней функции с потайной лазейкой, про которую я упоминал ранее, будет взято возведение в степень по модулю простого числа. В общем случае SecretText = PlainText ^ (e) mod (n). Значение величины e мы будем считать общедоступным, это будет нашим открытым ключом. Значение данной величины будет известно всем, кто хочет посылать сообщения лицу владеющим другим значением d — и именно он будет использовано для того чтобы вычислить открытый текст на базе закрытого (зашифрованного). И данное значение будет известно только получателю сообщения.

Идея расшифровки информации основана на повторном возведении зашифрованного текста в в степень, но уже числа d, для того чтобы такая идея работала необходимо чтобы между e и d существовало особое соотношение. И действительно есть требования чтобы e*d = 1 (mod fi(n)). В данной формуле fi(n) — это значении функции Эйлера. Следовательно эти две операции возведения в степень будут взаимно обратными и мы получим (M^e)^d = M ^ (e*d) = M (mod n). Итак значение d — секретный ключ, а значеие e — открытый ключ. Наиболее сложный вопрос — как вычислить значение данных переменных. Очевидно, что первым шагом в поиске значение e и d будет определение значения правой части уравнения. Необходимо узнать значение функции Эйлера для переменной n. В общем случае значение функции Эйлера от некоторой величины x равно количеству чисел взаимно простых с x и меньших его. Для произвольного аргумента нам придется заняться перебором всех значений меньших x и проверять каждое из них на предмет того кратно он x или нет.

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

Пусть m - натуральное число, m1, m2, ..., mt - взаимно простые натуральные числа, произведение которых больше либо равно m.

Теорема

Любое число x: 0 <= x <= m может быть однозначно представлено в виде последовательности r(x) = (r1, r2, ..., rt), где ri = x(mod mi).

Для любых чисел r1 .. rt, таким образом, существует единственное число x(mod m), такое что x = ri(mod mi), 1 <= i <= t

Более того, любое решение x набора такого сравнений имеет вид

x = r1*e1 + ... + rt*et (mod m), где ei = m / mi * ( ( m/mi )-1 mod mi ), 1 <= i <= t.

Вышеприведенная формулировка - Китайская Теорема об Остатках в том виде, в котором ее сформулировал в 1247 году нашей эры китаец Jiushao Qin.

Заметим, что число m/mi = m1*...*mi-1*mi+1*...*mt взаимно просто с mi, а значит обратное число в формуле для ei всегда существует. Кроме того, имеют место равенства

ei*ei = ei (mod m)

ei * ej = 0 (mod m), i =/= j.

Знакомым с теорией колец: Zm = Zm1 + ... + Zmt, сумма прямая. ei, как следует из равенств выше - ортогональные идемпотенты в кольце Zm.

Иначе говоря, кольцо R = Zm разлагается в прямую сумму

R = R1 + R2 + ... + Rt ,

где Ri = Rei = {a*ei (mod m): a - целое} ~ Zmi , 1 <= i <= t.

Последовательность ( r1, ..., rt ) называется модульным представлением x. Набор модульных представлений для всех x: 0 <= x <= m называетсясистемой вычетов.

Операции

Сумма представлений - последовательность wi = ri + ui mod mi

Произведение - последовательность zi = ri * ui mod mi. Как восстановить число по системе вычетов?

Алгоритм Гаусса

Очевидный алгоритм получается, если вычислять x по формуле, данной в теореме: На входе:

положительные взаимно простые m1, ..,mt

целые r1, .., rt

На выходе: Целое число x:

x = ri (mod mi), 1 <= i<= t 0 <= x <= m, m = m1*..*mt

1.Вычислить m = m1*..*mt, положить x=0.

2.for i=1, 2, .., t do

вычислить yi = m/mi

вычислить расширенным алгоритмом Евклида si = yi-1 mod mi ci = ri*si mod mi

x= x + ci*yi (mod m)

3.Возвратить x

Алгоритм Гарнера

Пусть все mi > 1, m = m1*..*mt. Тогда любое число 0 <= x < m может быть однозначным образом представлено в виде

x = x0 + x1m1 + x2m1m2 + ... + xt-1m1m2*...*mt-1 ,

где 0 <= xi < mi+1, i = 0, 1, .., t-1.

Для xi верно соотношение

ri+1 - ( x0 + x1m1 + .. + xi-1m1mi-1)

xi =		(mod mi+1)

m1*..*mi

Таким образом, xi могут быть вычеслены один за другим. Получившийся алгоритм носит имя Гарнера(Garner). Он также пригоден для аналогичных операций с полиномами (в предыдущем алгоритме требуются некоторые изменения).

1.For i from 2 to t {

1.1Ci := 1;

1.2For j from 1 to (i-1) { u := mj-1 mod mi;

Ci := u*Ci mod mi;

}

}

2.u := r1; x := u;

3.For i from 2 to t {

u:= (ri-x)Ci mod mi;

x := x + u* [ Произведение mj от j=1 до i-1 ];

}

4. return (x);

Пример: пусть

m1=5, m2=7, m3=11, m4=13,

m = m1*m2*m3*m4 = 5*7*11*13 = 5005, r(x) = (2, 1, 3, 8).

Константы Ci: C2=3, C3=6, C4=5.

Значения (i, u, x), вычисленные на шаге 3: (1, 2, 2); (2, 4, 22); (3, 7, 267) и (4, 5, 2192).

Таким образом модульное представление r(x) отвечает x = 2192.

Примечание Нахождение m-1 - обратного элемента по модулю можно осуществить опять по алгоритму Евклида.