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

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

 

Модулярная арифметика

 

Модулярная арифметика часто называется “арифметикой часов”. Если прибавить 14 часов к 3 часам после полудня, то получится 5 часов утра следующего дня:

 

3 + 14 º 5 (mod 12)

или

(3 + 14) mod 12 = 5.

 

Это арифметика по модулю 12.

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

 

a º b (mod n)

 

читается так: “ a сравнимо с b по модулю n ”.

Это соотношение справедливо для целых значений a, b и n ¹ 0, если и только если

а = b + k • n

для некоторого целого k.

Отсюда, в частности, следует

 

n | (a ─ b).

 

Это читается как “ n делит (a ─ b)”.

Если a º b (mod n), то b называют вычетом числа a по модулю n.

Операцию нахождения вычета числа а по модулю n

 

a (mod n)

 

называют приведением числа а по модулю n или приведением по модулю.

В нашем примере

 

(3 + 14) mod 12 = 17 mod 12 = 5

или

17 º 5 (mod 12),

 

число 5 является вычетом числа 17 по модулю 12.

Набор целых чисел от 0 до (n – 1) называют полным набором вычетов по модулю n.

Это означает, что для любого целого а (а > 0) его вычет r по модулю n есть некоторое целое число в интервале от 0 до (n – 1), определяемое из соотношения

r = a – k • n,

где k – целое число.

Например, для n = 12 полный набор вычетов:

{0, 1, 2, …, 11}.

Обычно используют вычеты

r Î {0, 1, 2, …, n – 1},

но иногда полезны вычеты в диапазоне целых:

r Î {– ½ (n – 1), …, ½ (n – 1)}.

Важно, что

 

– 12 (mod 7) º – 5 (mod 7) º 2 (mod 7) º 9 (mod 7) и т.д.

 

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

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

 

(a + b) mod n = [ a (mod n) + b (mod n) ] mod n,

(a - b) mod n = [ a (mod n) - b (mod n) ] mod n,

(a • b) mod n = [ a (mod n) • b (mod n) ] mod n,

[a • (b + c) ] mod n = {[a • b (mod n) ] + [a • c (mod n) ]} mod n.

 

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

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

 

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

Вычисление степени числа а по модулю 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).

 

Алгоритм 1.2.1 – Алгоритм Евклида для вычисления наибольшего общего делителя

 

Begin

g ₀ : = b;

g ₁ : = a;

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