Алгоритм Евклида для нахождения наибольшего общего делителя

Вычисление степени числа а по модулю n

Для того, чтобы найти а^х mod n можно выполнить как ряд умножений и делений.

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

Пример. Нужно вычислить а ⁸ mod n.

Не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

(а • а • а • а • а • а • а • а) mod n.

Вместо этого выполняют три малых умножения и три малых приведения по модулю:

((а ² mod n.)² mod n.)² mod n.

Тем же способом вычисляют

а ¹⁶ mod n. = (((а ² mod n.)² mod n.)² mod n.)² mod n.

Вычисление

а ^х mod n,

где х не является степенью 2, лишь немного сложнее. Двоичная запись числа х позволяет представить число х как сумму степеней 2:

х = 12 ₍₁₀₎ = 11001 ₍₂₎.

Поэтому 25 = 2 ⁴ + 2 ³ + 2 ⁰.

Тогда

а ²⁵ mod n. = (а • а ²⁴) mod n. = (а • а ⁸ • а ¹⁶) mod n =

= (а • ((а ²) ²) ² • (((а ²) ²) ² ) ²) mod n = ((((а ² • а) ²) ² ) ² • а) mod n.

При разумном накоплении промежуточных результатов потребуется только шесть умножений:

(((((((а ² mod n) • а) mod n)² mod n)² mod n)² mod n) • а) mod n.

Этот метод уменьшает трудоемкость вычислений до 1,5хk операций в среднем, где k – длина числа в битах.

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

Целое число а делит без остатка другое целое число b, если и только если

b = k • a

для некоторого целого числа k. В этом случае а называют делителем числа b или множителем в разложении числа b на множители.

Пусть а – целое число, причем а > 1. Тогда а является простым числом, если его единственным положительным делителем будут 1 и само а. В противном случае а называется составным.

Любое целое n > 1 может быть представлено единственным образом с точностью до порядка сомножителей как произведение простых.

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

n = p • q.

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

В эквивалентной форме (а, b) – это то единственное натуральное число, которое делит а и b и делится на любое целое, делящее и а и b.

Если НОД (а, b) = 1, то целые а и b – взаимно простые.

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

Опишем алгоритм Евклида для нахождения НОД (а, b).

Введем обозначения: q _i – частное, r _i – остаток.

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

а = b • q ₁ + r ₁, 0 < r ₁ < b,

b = r ₁ • q ₂ + r ₂, 0 < r ₂ < r ₁,

r₁ = r ₂ • q ₃ + r ₃, 0 < r ₃ < r ₂,

……...

r _{k - 2} = r _k - ₁ • q _k + r _k, 0 < r _k < r _{k - 1},

r _{k - 1} = r _k • q _{k + 1}.

Остановка гарантируется, поскольку остатки r _i от делений образуют строго убывающую последовательность натуральных чисел. Из этой цепочки немедленно получаем, что r _k есть общий делитель чисел а и b и, более того, что любой общий делитель чисел а и b делит и r _k. Таким образом, r _k = НОД (а, b) или r _k = (а, b).

Дата добавления: 2015-08-31