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

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

Алгоритм Евклида позволяет найти наибольший общий делитель двух многочленов, т.е. многочлен наибольшей степени, на который делятся без остатка оба данных многочлена.
Алгоритм основан на том факте, что для любых двух многочленов от одного переменного, 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)∙ q ₁(x) + r ₁(x), (1)

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

g (x) = r ₁(x)∙ q ₂(x) + r ₂(x), (2)

далее, если r ₂(x) ≠ 0, – первого остатка, r ₁(x), на второй остаток, r ₂(x):

r ₁(x) = r ₂(x)∙ q ₃(x) + r ₃(x), (3)

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

r ₂(x) = r ₃(x)∙ q ₄(x) + r ₄(x), (4)

и т.д. Поскольку на каждом этапе степень очередного остатка уменьшается, процесс не может продолжаться бесконечно, так что на некотором этапе мы обязательно придем к ситуации, когда очередной, n + 1-й остаток r_{n + 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)

Тогда последний не равный нулю остаток r_n и будет наибольшим общим делителем исходной пары многочленов f (x) и g (x).
Действительно, если в силу равенства (n + 2) подставить 0 вместо r_{n + 1}(x) в равенство (n + 1), затем – полученное равенство r_{n – 1}(x) = r_n (x)∙ q_{n + 1}(x) вместо r_{n – 1} (x) – в равенство (n), получится, что r_{n – 2}(x) = r_n (x)∙ q_{n + 1}(x) q_n (x) + r_n (x), т.е. r_{n – 2}(x) = r_n (x)(q_{n + 1}(x) q_n (x) + 1), и т.д. В равенстве (2) после подстановки получим, что g (x) = r_n (x)∙ Q (x), и, наконец, из равенства (1) – что f (x) = r_n (x)∙ S (x), где Q и S – некоторые многочлены. Таким образом, r_n (x) – общий делитель двух исходных многочленов, а то, что он наибольший (т.е. наибольшей возможной степени), следует из процедуры алгоритма.
Если наибольший общий делитель двух многочленов не содержит переменную (т.е. является числом), исходные многочлены f (x) и g (x) называются взаимно-простыми.

Если у нас есть два числа 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 или нет.

Дата добавления: 2015-04-23