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

Целое число а делит без остатка другое целое число 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).