Алгоритм Евклида для нахождения НОД. Малая теорема Ферма. Функция Эйлера (Лекция 5)

до порядка сомножителей как произведение простых .

Существенный с точки зрения криптографии факт состоит в том, что не известно никакого эффективного алгоритма разложения чисел на множители;
не было получено и никакой нетривиальной нижней оценки временной сложности разложения.
Никаких эффективных методов не известно даже в таком простом случае, когда необходимо восстановить два простых числа p и q из их произведения:
n = p * q.

или просто (a,b), – это наибольшее целое, делящее одновременно числа a и b.
Если НОД (a,b)=1, то целые a и b – взаимно простые.

Наибольший общий делитель может быть вычислен с помощью алгоритма Евклида. Евклид описал этот алгоритм в своей книге "Начала", написанной около 300 лет до н.э. Он не изобрел его. Историки полагают, что этот алгоритм, возможно, старше еще на 200 лет. Это древнейший нетривиальный алгоритм, который просуществовал до настоящего времени и все еще хорош и сегодня.

частное; ri – остаток.
Тогда алгоритм можно представить в виде следующей цепочки равенств:

a = b * q1 + r1, 0 < r1< b,
b = r1 * q2 + r2, 0 < r2< r1,
r1 = r2 * q3 + r3, 0 < r3< r2,
…….
rn–2 = rn–1 * qn + rn, 0 < rn< rn–1,
rn–1 = rn * qn+1 rn+1=0

натуральных чисел.
Таким образом, rn = НОД (a, b) или rn = (a, b).

Как следствие из алгоритма Евклида, можно получить утверждение, что
наибольший делитель целых чисел a и b
может быть представлен в виде линейной комбинации этих чисел, т.е. существуют целые числа и и v такие, что справедливо равенство

(a,b)=(b,r)=(r,r1) = …=(rn-1,rn)=rn

i : =1;
while g[i] ! = 0 do
begin
g[i+1] : = g[i–1] mod(g[i]);
i : = i +1;
end
gcd : = g[i–1]; /*gcd – результат*/
end

взаимно просты, то существует число а', удовлетворяющее сравнению а • а' = 1(mod n).
Число a' называют обратным к а по модулю n и используют обозначение : a-1(mod n) .

Вычислить а' можно, например, воспользовавшись представлением наибольшего общего делителя чисел а и n в виде их линейной комбинации: а*и + n*v = 1.
Взяв наименьшие неотрицательные вычеты обеих частей этого равенства по модулю n, получим, что искомое значение а' удовлетворяет сравнению
а' = и (mod n)

алгоритм определяет вектор
(u1, u2, u3),
такой, что
a * u1 + b * u2 = u3 = НОД (a, b).

В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3). Действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения
a * t1 + b * t2 = t3, a * u1 + b * u2 = u3,
a * v1 + b * v2 = v3.

расширенного алгоритма Евклида, при котором b = n, НОД (a,n) = 1, и этот алгоритм определяет вектор
(u1, u2, u3),
такой, что
u3 =1, a * u1 + n * u2 = НОД (a,n) =1,
(a * u1 + n * u2) mod n ≡ a * u1 (mod n) ≡ 1,
a–1 (mod n) ≡ u1 (mod n).

n),
(v1, v2, v3) : = (1, 0, a).

2. u3 =1 ?. Если u3 =1, то алгоритм заканчивается.
3. Разделить, вычесть.
Установить q : = [u3/v3].
Затем установить
(t1, t2, t3) : = (u1, u2, u3) – (v1, v2, v3) * q,
(u1, u2, u3) : = (v1, v2, v3),
(v1, v2, v3) : = (t1, t2, t3).
Возвратиться к шагу 2.

Найти обратное число a–1 (mod 23), т.е. x = 5–1 (mod 23).
Используя расширенный алгоритм Евклида, выполним вычисления, записывая результаты отдельных шагов табл. П.3.

q : = [u3/v3].
(u1, u2, u3) : = (v1, v2, v3),
(t1, t2, t3) : = (u1, u2, u3) – (v1, v2, v3) * q,
(v1, v2, v3) : = (t1, t2, t3).

+ n * u2 ) mod n = (5 * (– 9) + 23 * 2) mod 23 =
= 5 * (– 9) mod 23 ≡ 1,
a–1 (mod n) = 5–1 (mod 23) = (– 9) mod 23 = (– 9 + 23) mod 23 = 14.
Итак, x = 5–1 (mod 23) ≡ 14 (mod 23) = 14.

кратно m ,то малая теорема Ферма утверждает:

вычетов, члены которого взаимно просты с п.
Например, приведенную систему вычетов по модулю 12 составляют числа {1, 5, 7, 11}.

Если п - простое число, в приведенную систему вычетов по модулю п входит всё множество чисел от 1 до п— 1.
Для любого n, не равного 1, число 0 никогда не входит в приведенную систему вычетов.

φ(п), указывает число элементов в приведенной системе вычетов по модулю п.

Иными словами, φ(п) - это количество положительных целых чисел, меньших п и взаимно простых с п (для любого n, большего 1).

Если п — простое число, то φ(п) = п-1.
Если n = pq, где р и q - простые числа, то φ(п) = (р-1)(q-1).

= 1,то:

Теперь нетрудно вычислить а-1 mod n:

..., n – 1, пока не будет найден a–1 (mod n), такой, что a*a–1 (mod n) ≡ 1.
n=Prime[number];
a= Mod[b, n]
Do[,]
While[,]
For[,]
If[,]
Break[]

≡ aϕ(n)–1 (mod n),
используя алгоритм быстрого возведения в степень.
EulerPhi[n];
PowerMod[a,b,n] = ab mod n.

a=5
ExtendedGCD[n,a]
{1,{2,-9}}
u3 =1, u2 = 2 ,u1 = –9
5–1 (mod 23) = (– 9) mod 23 = (– 9 + 23) mod 23 = 14.
Mod[-9,23]
14

т.е. b ≠1, x = ?
используется следующий прием. Сначала решают сравнение
a * y ≡1 (mod n),
т.е. определяют
y = a–1 (mod n),
а затем находят
x = a–1 b (mod n) = y * b (mod n).

методов и алгоритмов.
Она сравнивает криптографические методы и алгоритмы и определяет их безопасность.

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

теории к чёрной дыре состоит в том, что она постепенно испаряется благодаря излучению ХокингаПроблемы начнутся, когда мы учтём квантовые явления. Главный результат применения квантовой теории к чёрной дыре состоит в том, что она постепенно испаряется благодаря излучению Хокинга. Это значит, что можно дождаться такого момента, когда масса чёрной дыры снова уменьшится до первоначального значения (перед бросанием в неё тела). Таким образом, мы получаем в результате, что чёрная дыра превратила исходное тело в поток разнообразных излучений, но сама при этом не изменилась (поскольку она вернулась к исходной массе!). Испущенное излучение при этом совершенно не зависит от того, что за тело было брошено в чёрную дыру. То есть чёрная дыра уничтожила попавшую в неё информацию.

может только расти, но не может ни уменьшиться, ни исчезнуть совсем. Это значит, что в принципе возможна ситуация, что попавшая в чёрную дыру информация на самом деле не исчезла, она продолжает находиться внутри чёрной дыры, но просто не наблюдаема снаружи. Иная разновидность этой же мысли: если чёрная дыра служит мостом между нашей вселенной и какой-нибудь другой Вселенной, то информация, возможно, просто перебросилась в другую вселенную.

сложность алгоритма часто измеряется двумя параметрами:
Т - временная сложность ;
S - пространственная сложность, или требования к памяти.
Т и S представляются в виде функций от п, где п - это размер входных данных.
(Существуют и другие способы измерения сложности: количество случайных бит, ширина канала связи, объем данных и т.п.)

порядком величины вычислительной сложности.
Это просто член разложения функции сложности, быстрее всего растущий с ростом n, все члены низшего порядка игнорируются.
Например, если временная сложность данного алгоритма равна 4n2+7n+12, то вычислительная сложность порядка n2, записываемая как О(n2).

Временная сложность измеренная таким образом не зависит от реализации. Не нужно знать ни точное время выполнения различных инструкций, ни число битов, используемых для представления различных переменных, ни даже скорость процессора.

При работе с сложными алгоритмами , всем прочим можно пренебречь (с точностью до постоянного множителя) в сравнении со сложностью по порядку величины.

называют постоянным, если его сложность не зависит от п: О(1).
Алгоритм является линейным, если его временная сложность О(n).
Алгоритмы могут быть квадратичными, кубическими и т.д.
Все эти алгоритмы - полиномиальны, их сложность - О(nm),
где m - константа.
Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем.

чем 1,
a f(n) - некоторая полиномиальная функция от n,
называются экспоненциальными.

Подмножество экспоненциальных алгоритмов, сложность которых равна О(c f(n)),
где где с - константа,
a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция,
называется суперполиномиальным

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

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

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

С ростом п временная сложность алгоритмов может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма.

может выполнить постоянный алгоритм за микросекунду, линейный - за секунду, а квадратичный - за 11.6 дня.
Выполнение кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция которого позволила бы ему противостоять следующему ледниковому периоду, в конце концов получил бы решение.

пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа.
Если п - длина ключа, то сложность вскрытия грубой силой равна O(2n).
Сложность вскрытия грубой силой алгоритма DES при 56-битовом ключе составляет 256, а при 112-битовом ключе - 2112.
В первом случае вскрытие возможно, а во втором - нет.

только сложность конкретных алгоритмов решения проблемы.

Теория рассматривает минимальное время и объем памяти, необходимые для решения самого трудного варианта проблемы на теоретическом компьютере, известном как машина Тьюринга.
Машина Тьюринга представляет собой конечный автомат с бесконечной лентой памяти для чтения-записи и является реалистичной моделью вычислений.

числам состояний (finite-state control unit), k≥1 лент (tapes) и такого же количества головок (tapeheads).
Управляющее устройство контролирует операции, выполняемые головками, которые считывают информацию с лент или записывают ее на ленту.

нее влево и вправо.
Каждая лента разделена на бесконечное количество ячеек (cells).
Машина решает задачу, перемещая головку вдоль строки, состоящей из конечного количества символов, расположенных последовательно, начиная с крайней левой ячейки.

остаются пустыми (blank). Описанная выше строка называется исходными данными задачи (input).
Сканирование начинается с крайней слева ячейки ленты, содержащей исходные данные, когда машина находится в предписанном начальном состоянии (initial state).

своей ленте.
Операция доступа головки к своей ленте называется тактом (legal move).

исходную строку и завершает работу, достигая заключительного состояния (termination condition), говорят, что машина распознает (recognize) исходные данные.
В противном случае в некоторый момент машина не может выполнить очередной такт и останавливается, не распознав исходные данные.

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

исходной строки, называется продолжительностью работы или временной сложностью (time complexity) машины М.
Очевидно, что величину Тм можно представить в виде функции Тм(п) : N → N, где п — длина (length), или размер (size), исходного предложения, т.е. количество символов, из которых состоит исходная строка, когда машина М пребывает в начальном состоянии.

имеет ограничения памяти SM, представляющие собой количество ячеек, которые доступны для записи.
Величину SM также можно представить в виде функции
SM(n) : N → N, которая называется пространственной сложностью (space complexity) машины М.

исходную строку и завершает работу, достигая заключительного состояния (termination condition), говорят, что машина распознает (recognize) исходные данные.

она имеет вид:

где числа к и ci (i = 0,1,2,... ,к) — целые константы, причем сi ≠ 0.
Число к ≥ 0 называется степенью (degree) полинома и обозначается как deg(p(n)),
а числа ci называются коэффициентами (coefficients) полинома р(п).

характеристики.
Язык L принадлежит классу , если существует машина Тьюринга М и полином р(п), такие что машина М распознает любое предложение I ∈ L за время Тм(п),
где Тм(п) ≤ р(п) для всех неотрицательных целых чисел п,
а п — параметр, задающий длину предложения I.
В этом случае говорят, что язык L распознается за полиномиальное время.

Тьюринга — "всегда эффективными".
Рассмотрим смысл слова "всегда". Все машины Тьюринга, распознающие язык L из класса , называются детерминированными (deterministic).
Детерминированная машина Тьюринга порождает результат, который полностью предопределен исходными данными и начальным состоянием машины.
Иначе говоря, повторный запуск машины Тьюринга с теми же исходными данными и начальным состоянием приводит к идентичным результатам.

любой экземпляр данной задачи можно решить с помощью одной и той же машины Тьюринга (т.е. с помощью одного и того же метода).
Только в этом случае алгоритм считается достаточно общим и может называться методом.

трем.
Покажем, что DIV3 ∈ P.

BaseForm[3333,3]
111201103

Для того чтобы распознать язык DIV3 за полиномиальное время, построим машину Тьюринга с одной лентой.

системе счисления по основанию 3), т.е. в виде строки символов из множества {0,1,2}, то задача распознавания становится тривиальной:

когда последняя цифра в строке х равна нулю.

вправо, пока не обнаружит пустой символ.
Машина должна остановиться и выдать ответ "ДА", если и только если последний непустой символ был равен нулю.

предложение, состоящее из цифр, причем количество шагов алгоритма равно длине исходной строки.
Следовательно, DIV3 ∈ P.
Т DIV3(n) = n. Машина распознает язык DIV3 за полиномиальное время.

полиномиальное время.
Задача распознавания языка является задачей принятия решений (decisional problem).
При любых исходных данных результатом решения такой задачи является ответ "ДА" или "НЕТ".

Однако класс  является более широким и содержит полиномиальные вычислительные задачи (polynomial-time computational problems).
При любых исходных данных результатом решения таких задач является более общий ответ, чем "ДА" и "НЕТ". Поскольку машина Тьюринга может записывать символы на ленту, она позволяет решать такие задачи.

архитектуру),
состоит из счетчика, памяти и центрального процессора (central processor unit — CPU),
поочередно выполняющего элементарные команды, называемые микрокомандами.

Load (Загрузить)
Store (Сохранить)
Add (Сложить)
Соmр (Дополнение)
Jump (Перейти)
JumpZ (Условный переход)
Stop (Остановиться)

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

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

Это возможно благодаря тому, что для любых полиномов р(п) и q(n) произвольные арифметические комбинации р(п), q(n), p(q(n)) и q(p(n)) также являются полиномами, зависящими от аргумента п.

с > 0 и натуральное число N,
такие что |g(п)| ≤ с| f(n)| для всех n ≥ N.

Используя О – символику можно отобразить временную сложность алгоритмов, рассмотрим следующую теорему:

более чем 2mах(|а|, |b|) операций модулярной арифметики.

Эту теорему впервые доказал Ж. Ламе (1795-1870) (G. Lame).
Ее можно считать первой теоремой в теории вычислительной сложности.

⎡x⎤ - минимальное целое число, большее или равное числу x; функция Ceiling[x] в пакете Mathematica
⎣x⎦ - максимальное целое число, не превосходящее число x; функция Floor[x] в пакете Mathematica
Обозначение |x| - длина целого числа x, равная 1+ ⎣log2 x⎦ для x≥ 1, или модуль числа x.

условии a > b ) может быть определена как: (log a).
Не указывая явно основание логарифма.

-символика для поразрядных вычислений

Для оценки сложности поразрядных (bitwise) арифметических операций используется модифицированная -символика.
В поразрядных вычислениях все переменные принимают значения нуль или единица, а операции носят не арифметический, а логический характер:
∧ (для операции AND),
(для операции OR),
⊕ (для операции XOR, т.е. "исключающего или") и
¬ (для операции NOT).

чисел i и j затрачиваются max(|i|, |j|) побитовых операций, т.е. порядок временной сложности равен  (max( | i |, | j |)).
На умножение и деление двух целых чисел i и j затрачиваются |i|•|j| побитовых операций, т.е. порядок их временной сложности равен  ( log i × log j ).

каждом такте работы которого существует конечное количество вариантов следующего такта.
Входная строка считается распознанной, если существует хотя бы одна последовательность разрешенных тактов, начинающаяся считыванием первого символа строки и завершающаяся считыванием последнего символа.
Такая последовательность тактов называется последовательностью распознавания (recognition sequence).

этом случае последовательность распознавания представляет собой серию правильных догадок.
Таким образом, все возможные такты образуют дерево, называемое вычислительным деревом (computational tree) недетерминированной машины Тьюринга.

поскольку количество тактов в последовательности распознавания входной строки равно глубине дерева d, получаем, что d =  (log (количество узлов дерева)) и количество тактов в последовательности распознавания полиномиально зависит от размера входной строки.
Итак, временная сложность распознавания строки с помощью серии правильных догадок полиномиально зависит от размера исходных данных.
Язык принадлежит классу , если он распознается недетерминированной машиной Тьюринга за полиномиальное время.

зависит от размера исходных данных.

Определение : Язык принадлежит классу , если он распознается недетерминированной машиной Тьюринга за полиномиальное время.

они обычно могут быть решены для задач достаточно большой размерности n.

Класс Р или P - TIME состоит из всех задач, решаемых за полиномиальное время

за полиномиальное время на недетерминированной машине Тьюринга, способной параллельно выполнять
неограниченное количество независимых вычислений.

Класс NP Complete (NP - полных) задач включает все самые трудные NP задачи.

но не обязательно решаемых за полиномиальное время.