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

Введение

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

В математике, алгоритм Евклида — это эффективный метод вычисления наибольшего общего делителя (НОД) двух целых чисел, наибольшего числа, которое делит их оба без остатка. Он назван в честь древнегреческого математика Евклида, который впервые описал его в своих «Началах» (около 300 г. до н.э.). Это пример алгоритма — пошаговой процедуры для выполнения вычислений в соответствии с чётко определёнными правилами, и один из старейших алгоритмов, находящихся в широком использовании. Его можно использовать для приведения дробей к их простейшей форме, и он является частью многих других теоретико-числовых и криптографических вычислений. Алгоритм Евклида основан на принципе, что наибольший общий делитель двух чисел не изменяется, если большее число заменяется его разностью с меньшим числом. Например, 21 является НОД чисел 252 и 105 (так как 252 = 21 * 12 и 105 = 21 * 5), и то же число 21 также является НОД чисел 105 и 147 (так как 147 = 105 + 42). Поскольку эта замена уменьшает большее из двух чисел, повторение этого процесса приводит к последовательно уменьшающимся парам чисел, пока два числа не станут равными. Когда это происходит, они и являются НОД исходных двух чисел. Обратив шаги алгоритма или используя расширенный алгоритм Евклида, НОД можно выразить как линейную комбинацию двух исходных чисел, то есть как сумму двух чисел, каждое из которых умножено на целое число (например, 21 = 252 * (-1) + 105 * 3). Тот факт, что НОД всегда можно выразить таким образом, известен как тождество Безу. Версия алгоритма Евклида, описанная выше, следующая оригинальному представлению Евклида, может потребовать много шагов вычитания для нахождения НОД, если одно из заданных чисел значительно больше другого. Более эффективная версия алгоритма сокращает эти шаги, заменяя большее из двух чисел его остатком от деления на меньшее из двух (в этой версии алгоритм останавливается при достижении нулевого остатка). Благодаря этому улучшению алгоритм никогда не требует больше шагов, чем в пять раз больше числа цифр (в десятичной системе счисления) меньшего целого числа. Это было доказано Габриэлем Ламе в 1844 году (теорема Ламе) и знаменует собой начало теории вычислительной сложности. В XX веке были разработаны дополнительные методы повышения эффективности алгоритма. Алгоритм Евклида имеет множество теоретических и практических применений. Он используется для приведения дробей к их простейшей форме и для выполнения деления в модульной арифметике. Вычисления с использованием этого алгоритма являются частью криптографических протоколов, используемых для защиты интернет-коммуникаций, и в методах взлома этих криптосистем путём разложения больших составных чисел на множители. Алгоритм Евклида может использоваться для решения диофантовых уравнений, таких как нахождение чисел, удовлетворяющих нескольким сравнениям согласно китайской теореме об остатках, для построения непрерывных дробей и для нахождения точных рациональных приближений к действительным числам. Наконец, он может быть использован в качестве основного инструмента для доказательства теорем в теории чисел, таких как теорема Лагранжа о четырёх квадратах и уникальность разложения на простые множители. Изначальный алгоритм был описан только для натуральных чисел и геометрических длин (действительных чисел), но в XIX веке алгоритм был обобщён для других типов чисел, таких как гауссовы целые числа и полиномы одной переменной. Это привело к современным абстрактным алгебраическим понятиям, таким как евклидовы области.

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC). It is an example of an algorithm, a step by step procedure for performing a calculation according to well defined rules,
and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number theoretic and cryptographic calculations. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as and , and the same number 21 is also the GCD of 105 and Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By reversing the steps or using the extended Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that is the sum of the two numbers, each multiplied by an integer (for example, ). The fact that the GCD can always be expressed in this way is known as Bézout's identity. The version of the Euclidean algorithm described above—which follows Euclid's original presentation—can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 (Lamé's Theorem), and marks the beginning of computational complexity theory. Additional methods for improving the algorithm's efficiency were developed in the 20th century. The Euclidean algorithm has many theoretical and practical applications. It is used for reducing fractions to their simplest form and for performing division in modular arithmetic. Computations using this algorithm form part of the cryptographic protocols that are used to secure internet communications, and in methods for breaking these cryptosystems by factoring large composite numbers. The Euclidean algorithm may be used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences according to the Chinese remainder theorem, to construct continued fractions, and to find accurate rational approximations to real numbers. Finally, it can be used as a basic tool for proving theorems in number theory such as Lagrange's four square theorem and the uniqueness of prime factorizations. The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as Gaussian integers and polynomials of one variable. This led to modern abstract algebraic notions such as Euclidean domains.

Основные сведения: величайший общий делитель

Евклидов алгоритм вычисляет наибольший общий делитель (НОД) двух натуральных чисел a и b. Наибольший общий делитель g — это наибольшее натуральное число, которое делит a и b без остатка. Синонимы НОД включают наибольший общий фактор (НОВ), наибольший общий делитель (НОД), наибольший общий множитель (НОМ) и наибольшую общую меру (НОМ). Наибольший общий делитель часто записывается как НОД(a, b) или, проще, как (a, b), хотя последнее обозначение неоднозначно, поскольку также используется для таких понятий, как идеал в кольце целых чисел, который тесно связан с НОД. Если НОД(a, b) = 1, то a и b называются взаимно простыми (или копримыми). Это свойство не означает, что a или b сами являются простыми числами. Например, 6 и 35 раскладываются на 6 = 2 × 3 и 35 = 5 × 7, поэтому они не являются простыми, но их простые делители различны, следовательно, 6 и 35 взаимно просты, не имея общих делителей, кроме 1. Пусть a = gm и b = gn. Поскольку a и b оба кратны g, их можно представить в виде gm и gn, и не существует большего числа G > g, для которого это верно. Натуральные числа m и n должны быть взаимно простыми, поскольку любой общий фактор можно было бы вынести за скобки из m и n, чтобы увеличить g. Таким образом, любое другое число c, которое делит и a, и b, также должно делить g. Наибольший общий делитель g чисел a и b — это единственный (положительный) общий делитель a и b, который делится на любой другой общий делитель c.

The Euclidean algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for GCD include greatest common factor (GCF), highest common factor (HCF), highest common divisor (HCD), and greatest common measure (GCM). The greatest common divisor is often written as gcd(a, b) or, more simply, as (a, b), although the latter notation is ambiguous, also used for concepts such as an ideal in the ring of integers, which is closely related to GCD. If , then a and b are said to be coprime (or relatively prime). This property does not imply that a or b are themselves prime numbers. For example, 6 and 35 factor as 6 = 2 × 3 and 35 = 5 × 7, so they are not prime, but their prime factors are different, so 6 and 35 are coprime, with no common factors other than 1. Let Since a and b are both multiples of g, they can be written and , and there is no larger number G > g for which this is true. The natural numbers m and n must be coprime, since any common factor could be factored out of m and n to make g greater. Thus, any other number c that divides both a and b must also divide g. The greatest common divisor g of a and b is the unique (positive) common divisor of a and b that is divisible by any other common divisor c.

The greatest common divisor can be visualized as follows. Consider a rectangular area a by b, and any common divisor c that divides both a and b exactly. The sides of the rectangle can be divided into segments of length c, which divides the rectangle into a grid of squares of side length c. The GCD g is the largest value of c for which this is possible. For illustration, a 24×60 rectangular area can be divided into a grid of: 1×1 squares, 2×2 squares, 3×3 squares, 4×4 squares, 6×6 squares or 12×12 squares. Therefore, 12 is the GCD of 24 and 60. A 24×60 rectangular area can be divided into a grid of 12×12 squares, with two squares along one edge and five squares along the other
The greatest common divisor of two numbers a and b is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as it divides both a and b. For example, since 1386 can be factored into 2 × 3 × 3 × 7 × 11, and 3213 can be factored into 3 × 3 × 3 × 7 × 17, the GCD of 1386 and 3213 equals , the product of their shared prime factors (with 3 repeated since 3 × 3 divides both). If two numbers have no common prime factors, their GCD is 1 (obtained here as an instance of the empty product); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors. Factorization of large integers is believed to be a computationally very difficult problem, and the security of many widely used cryptographic protocols is based upon its infeasibility. Another definition of the GCD is helpful in advanced mathematics, particularly ring theory. but it can also be calculated by repeatedly taking the GCDs of pairs of numbers. For example,

1=gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b). Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.

Наибольший общий делитель можно представить следующим образом. Рассмотрим прямоугольную область размером a × b и любой общий делитель c, который делит a и b нацело. Стороны прямоугольника можно разделить на сегменты длиной c, что разделит прямоугольник на сетку квадратов со стороной c. НОД g — это наибольшее значение c, для которого это возможно. Для иллюстрации, прямоугольную область 24 × 60 можно разделить на сетку: квадратов 1 × 1, квадратов 2 × 2, квадратов 3 × 3, квадратов 4 × 4, квадратов 6 × 6 или квадратов 12 × 12. Следовательно, 12 — это НОД 24 и 60. Прямоугольную область 24 × 60 можно разделить на сетку из квадратов 12 × 12, с двумя квадратами вдоль одного края и пятью квадратами вдоль другого. Наибольший общий делитель двух чисел a и b является произведением общих простых множителей этих чисел, где каждый простой множитель может повторяться столько раз, сколько он делит и a, и b. Например, поскольку 1386 можно разложить на 2 × 3 × 3 × 7 × 11, а 3213 можно разложить на 3 × 3 × 3 × 7 × 17, НОД 1386 и 3213 равен 3 × 3 × 7 = 63, произведению их общих простых множителей (с 3 повторяющимся, поскольку 3 × 3 делит оба числа). Если два числа не имеют общих простых множителей, их НОД равен 1 (полученный здесь как пример пустого произведения); другими словами, они взаимно просты. Ключевым преимуществом алгоритма Евклида является то, что он может эффективно находить НОД, не вычисляя простые множители. Факторизация больших целых чисел считается вычислительно сложной задачей, и безопасность многих широко используемых криптографических протоколов основана на ее неразрешимости. Другое определение НОД полезно в высшей математике, особенно в теории колец, но его также можно вычислить, многократно находя НОД пар чисел. Например, НОД(a, b, c) = НОД(a, НОД(b, c)) = НОД(НОД(a, b), c) = НОД(НОД(a, c), b). Таким образом, алгоритм Евклида, который вычисляет НОД двух целых чисел, достаточно для вычисления НОД произвольно большого количества целых чисел.

Процедура

Алгоритм Евклида можно рассматривать как построение последовательности неотрицательных целых чисел, начинающейся с двух заданных целых чисел и и в конечном итоге завершающейся целым числом ноль: с Целое число тогда будет НОД, и мы можем утверждать, что алгоритм указывает, как построить промежуточные остатки посредством деления с остатком предыдущей пары путем нахождения целого частного такого, чтобы:

Поскольку последовательность неотрицательных целых чисел строго убывает, она в конечном итоге должна завершиться. Другими словами, поскольку для каждого , и каждое является целым числом, строго меньшим предыдущего , в конечном итоге не может быть неотрицательного целого числа, меньшего нуля, и, следовательно, алгоритм должен завершиться. Фактически, алгоритм всегда завершится на n-м шаге, когда равно нулю. Для иллюстрации предположим, что требуется найти НОД чисел 1071 и 462. Последовательность начинается с и для нахождения необходимо найти целые числа и такие, чтобы:

Это частное , поскольку Это определяет и, следовательно, последовательность теперь Следующий шаг – продолжить последовательность для нахождения путем нахождения целых чисел и таких, чтобы:

Это частное , поскольку Это определяет и, следовательно, последовательность завершена как , поскольку больше неотрицательного целого числа, меньшего , найти нельзя. Предпоследний остаток является, следовательно, искомым НОД:

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

Визуализация

Алгоритм Евклида можно визуализировать с точки зрения аналогии с мощением, описанной выше для наибольшего общего делителя. Предположим, что мы хотим полностью покрыть прямоугольник размером a × b квадратными плитками, где a – большее из двух чисел. Сначала мы пытаемся покрыть прямоугольник квадратными плитками размером b × b; однако это оставляет незаполненным остаточный прямоугольник размером r0 × b, где r0 < b. Затем мы пытаемся покрыть остаточный прямоугольник квадратными плитками размером r0 × r0. Это оставляет второй остаточный прямоугольник размером r1 × r0, который мы пытаемся покрыть квадратными плитками размером r1 × r1, и так далее. Последовательность завершается, когда не остается остаточного прямоугольника, то есть когда квадратные плитки точно покрывают предыдущий остаточный прямоугольник. Длина стороны самой маленькой квадратной плитки равна НОД размеров исходного прямоугольника. Например, самая маленькая квадратная плитка на соседнем рисунке имеет размер 21 × 21 (показана красным), а 21 является НОД чисел 1071 и 462, которые являются размерами исходного прямоугольника (показан зеленым).

Историческое развитие

Евклидов алгоритм — один из древнейших алгоритмов, находящихся в широком применении. Он встречается в «Началах» Евклида (ок. 300 г. до н. э.), в частности, в книге VII (предложения 1–2) и книге X (предложения 2–3). В книге VII алгоритм сформулирован для целых чисел, а в книге X — для длин отрезков. (В современной терминологии можно сказать, что он был сформулирован там для действительных чисел. Однако длины, площади и объемы, представленные в современной практике как действительные числа, не измеряются в одних и тех же единицах, и не существует естественной единицы длины, площади или объема; понятие действительных чисел в то время было неизвестно.) Последний алгоритм носит геометрический характер. НОД двух длин *a* и *b* соответствует наибольшей длине *g*, которая равномерно измеряет *a* и *b*; иными словами, длины *a* и *b* являются целыми кратными длины *g*.

Вероятно, алгоритм не был открыт Евклидом, который собрал результаты более ранних математиков в своих «Началах». Математик и историк Б. Л. ван дер Варден предполагает, что книга VII происходит из учебника по теории чисел, написанного математиками пифагорейской школы. Алгоритм, вероятно, был известен Евдоксу Книдскому (ок. 375 г. до н. э.). Судя по использованию технического термина ἀνθυφαίρεσις (антифирезис, взаимное вычитание) в трудах Евклида и Аристотеля, алгоритм мог существовать еще до Евдокса. Спустя столетия алгоритм Евклида был независимо открыт как в Индии, так и в Китае, главным образом для решения диофантовых уравнений, возникавших в астрономии и при создании точных календарей. В конце V века индийский математик и астроном Арьябхата назвал алгоритм «пульверизатором», возможно, из-за его эффективности в решении диофантовых уравнений. Хотя частный случай китайской теоремы об остатках уже был описан в китайской книге «Суньцзы Суаньцзин», общее решение было опубликовано Цинь Цзюшао в его книге 1247 года «Шушу Цзючжан» (數書九章 — Математический трактат в девяти разделах). Впервые в Европе алгоритм Евклида был описан численно и популяризирован во втором издании «Приятных и занимательных задач» Баше (1624 г.), который приписал его Роджеру Коутсу как метод эффективного вычисления непрерывных дробей. В XIX веке евклидов алгоритм привел к развитию новых систем чисел, таких как гауссовы целые числа и айзенштейновские целые числа. В 1815 году Карл Гаусс использовал евклидов алгоритм для доказательства единственности разложения гауссовых целых чисел на множители, хотя его работа была впервые опубликована в 1832 году. Лежен Дирихле отметил, что многие результаты теории чисел, такие как единственность разложения на множители, будут справедливы для любой другой системы чисел, к которой можно применить евклидов алгоритм. Лекции Лежена Дирихле по теории чисел были отредактированы и дополнены Рихардом Дедекиндом, который использовал евклидов алгоритм для изучения алгебраических целых чисел — нового общего типа чисел. Например, Дедекинд первым доказал теорему Ферма о сумме двух квадратов, используя единственность разложения гауссовых целых чисел на множители. Дедекинд также определил понятие евклидова домена — системы чисел, в которой можно определить обобщенную версию евклидова алгоритма (как описано ниже). В последние десятилетия XIX века евклидов алгоритм постепенно уступил место более общей теории идеалов Дедекинда. «[Евклидов алгоритм] — прародитель всех алгоритмов, поскольку это самый старый нетривиальный алгоритм, дошедший до наших дней». Дональд Кнут, «Искусство программирования», том 2: Получисловые алгоритмы, 2-е издание (1981), с. 318. В XIX веке были разработаны и другие применения евклидова алгоритма. В 1829 году Шарль Штурм показал, что алгоритм полезен в цепном методе Штурма для подсчета вещественных корней многочленов на заданном интервале. Евклидов алгоритм стал первым алгоритмом поиска целочисленных соотношений, то есть методом нахождения целочисленных соотношений между соизмеримыми действительными числами. Было разработано несколько новых алгоритмов поиска целочисленных соотношений, таких как алгоритм Хеламана Фергюсона и Р. В. Форкада (1979) и алгоритм LLL. В 1969 году Коул и Дэви разработали двухместную игру, основанную на евклидовом алгоритме, под названием «Игра Евклида», для которой существует оптимальная стратегия. Игроки начинают с двух куч камней, содержащих *a* и *b* камней соответственно. Игроки по очереди удаляют из большей кучи *m* кратных меньшей кучи. Таким образом, если две кучи содержат *x* и *y* камней, где *x* больше *y*, следующий игрок может уменьшить большую кучу с *x* камней до *x* − *my* камней, при условии, что последнее число является неотрицательным целым числом. Победителем становится игрок, первым уменьшивший одну из куч до нуля камней.

The algorithm was probably not discovered by Euclid, who compiled results from earlier mathematicians in his Elements. The mathematician and historian B. L. van der Waerden suggests that Book VII derives from a textbook on number theory written by mathematicians in the school of Pythagoras. The algorithm was probably known by Eudoxus of Cnidus (about 375 BC). The algorithm may even pre date Eudoxus, judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and Aristotle. Centuries later, Euclid's algorithm was discovered independently both in India and in China, primarily to solve Diophantine equations that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer Aryabhata described the algorithm as the "pulverizer", perhaps because of its effectiveness in solving Diophantine equations. Although a special case of the Chinese remainder theorem had already been described in the Chinese book Sunzi Suanjing, the general solution was published by Qin Jiushao in his 1247 book Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections). The Euclidean algorithm was first described numerically and popularized in Europe in the second edition of Bachet's Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624). who attributed it to Roger Cotes as a method for computing continued fractions efficiently. In the 19th century, the Euclidean algorithm led to the development of new number systems, such as Gaussian integers and Eisenstein integers. In 1815, Carl Gauss used the Euclidean algorithm to demonstrate unique factorization of Gaussian integers, although his work was first published in 1832. Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied. Lejeune Dirichlet's lectures on number theory were edited and extended by Richard Dedekind, who used Euclid's algorithm to study algebraic integers, a new general type of number. For example, Dedekind was the first to prove Fermat's two square theorem using the unique factorization of Gaussian integers. Dedekind also defined the concept of a Euclidean domain, a number system in which a generalized version of the Euclidean algorithm can be defined (as described below). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of ideals. "[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day." Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318. Other applications of Euclid's algorithm were developed in the 19th century. In 1829, Charles Sturm showed that the algorithm was useful in the Sturm chain method for counting the real roots of polynomials in any given interval. The Euclidean algorithm was the first integer relation algorithm, which is a method for finding integer relations between commensurate real numbers. Several novel integer relation algorithms have been developed, such as the algorithm of Helaman Ferguson and R. W. Forcade (1979) and the LLL algorithm. In 1969, Cole and Davie developed a two player game based on the Euclidean algorithm, called The Game of Euclid, which has an optimal strategy. The players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from the larger. Thus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to x − my stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.

Основные идеалы и связанные с ними проблемы

Тождество Безу дает еще одно определение наибольшего общего делителя g двух чисел a и b. Рассмотрим множество всех чисел ua + vb, где u и v – любые два целых числа. Поскольку a и b делятся на g, каждое число в этом множестве делится на g. Другими словами, каждое число множества является целым кратным g. Это верно для любого общего делителя a и b. Однако, в отличие от других общих делителей, наибольший общий делитель является элементом множества; по тождеству Безу, выбор u = s и v = t дает g. Меньший общий делитель не может быть элементом множества, так как каждый элемент множества должен делиться на g. И наоборот, любое кратное m числа g можно получить, выбрав u = ms и v = mt, где s и t – целые числа из тождества Безу. Это можно увидеть, умножив тождество Безу на m: 1 = mg = msa + mtb. Таким образом, множество всех чисел ua + vb эквивалентно множеству кратных m числа g. Другими словами, множество всех возможных сумм целых кратных двух чисел (a и b) эквивалентно множеству кратных НОД(a, b). Наибольший общий делитель называют генератором идеала, порожденного a и b. Это определение НОД привело к современным абстрактным алгебраическим понятиям главного идеала (идеала, порожденного одним элементом) и главного идеального домена (домена, в котором каждый идеал является главным идеалом). Некоторые задачи можно решить, используя этот результат. Например, рассмотрим две мерные чашки объемом a и b. Добавляя/отнимая u кратных первой чашки и v кратных второй чашки, можно отмерить любой объем ua + vb. Все эти объемы являются кратными g = НОД(a, b).

Умножающие инверсы и алгоритм RSA

Конечное поле — это множество чисел с четырьмя обобщенными операциями. Эти операции называются сложением, вычитанием, умножением и делением и обладают обычными свойствами, такими как коммутативность, ассоциативность и дистрибутивность. Примером конечного поля является множество из 13 чисел {0, 1, 2, ..., 12} с использованием модульной арифметики. В этом поле результаты любой математической операции (сложения, вычитания, умножения или деления) приводятся по модулю 13; то есть, к результату добавляются или вычитаются кратные 13, пока он не окажется в диапазоне от 0 до 12. Например, результат 5 × 7 = 35 mod 13 = 9. Такие конечные поля могут быть определены для любого простого числа p; используя более сложные определения, они также могут быть определены для любой степени m простого числа p, то есть pm. Конечные поля часто называются полями Галуа и обозначаются GF(p) или GF(pm). В таком поле, содержащем m чисел, каждый ненулевой элемент a имеет уникальный модульный мультипликативный обратный элемент a-1, такой что 1 = aa-1 = a-1a ≡ 1 mod m. Этот обратный элемент можно найти, решив сравнение ax ≡ 1 mod m, или эквивалентное линейное диофантово уравнение 1 = ax + my. Это уравнение можно решить с помощью алгоритма Евклида, как описано выше. Нахождение мультипликативных обратных является важным шагом в алгоритме RSA, который широко используется в электронной коммерции; в частности, это уравнение определяет целое число, используемое для расшифровки сообщения. Хотя алгоритм RSA использует кольца, а не поля, алгоритм Евклида все равно можно использовать для нахождения мультипликативного обратного, если оно существует. Алгоритм Евклида также имеет другие применения в кодах, исправляющих ошибки; например, его можно использовать как альтернативу алгоритму Берлекэмпа — Мэсси для декодирования кодов BCH и Рида — Соломона, которые основаны на полях Галуа.

Алгоритмы факторизации

Вычисление наибольшего общего делителя является важным шагом в нескольких алгоритмах факторизации целых чисел, таких как алгоритм ро Поларда, алгоритм Шора, метод факторизации Диксона и факторизация эллиптической кривой Ленстры. Алгоритм Евклида может быть использован для эффективного нахождения этого НОД. Факторизация с помощью цепных дробей использует цепные дроби, которые определяются с помощью алгоритма Евклида.

Альтернативные методы

Алгоритм Евклида широко используется на практике, особенно для небольших чисел, благодаря своей простоте. Для сравнения можно определить эффективность альтернативных алгоритмов для нахождения НОД. Один из неэффективных подходов к нахождению НОД двух натуральных чисел a и b заключается в вычислении всех их общих делителей; НОД, таким образом, является наибольшим общим делителем. Общие делители можно найти, последовательно деля оба числа на целые числа, начиная с 2 и до меньшего из чисел b. Количество шагов этого подхода растет линейно с b или экспоненциально с количеством цифр. Другой неэффективный подход — найти простые множители одного или обоих чисел. Как отмечалось выше, НОД равен произведению общих простых множителей чисел a и b. Однако эта альтернатива также имеет сложность O(h²). Как правило, на реальных компьютерах она быстрее алгоритма Евклида, хотя масштабируется аналогичным образом. Дополнительную эффективность можно получить, рассматривая только старшие разряды чисел a и b. Бинарный алгоритм можно обобщить на другие системы счисления (k-ичные алгоритмы), что позволяет увеличить скорость до пяти раз. Алгоритм GCD Лемера использует тот же общий принцип, что и бинарный алгоритм, для ускорения вычислений НОД в произвольных системах счисления. Рекурсивный подход для очень больших целых чисел (с более чем 25 000 цифр) приводит к квазилинейным алгоритмам НОД, таким как алгоритмы Шёнхаге, Штеле и Циммермана. Эти алгоритмы используют матричную форму 2×2 алгоритма Евклида, представленную выше. Обычно эти квазилинейные методы имеют сложность: