На самом деле сейчас сходу не очень понятно, зачем все это надо. Ну вот есть какие-то теоремы про числа, что с этого? Просто математика, пусть ей занимаются платоники и не лезут в нашу физико-информационную реальность. Такого же мнения придерживался и один из центральных математиков XX века Годфри Харди, который в своей книге "Апология математики" (1940) писал:
"Я никогда не делал чего-нибудь «полезного». Ни одно мое открытие не принесло и не могло бы принести, явно или неявно, к добру или ко злу, ни малейшего изменения в благоустройстве этого мира."
Как же он ошибался... Всего через четверть века теория чисел и непосредственно труды Харди начали активно использоваться в шифорвании. (нашу статью о шифровании с открытым ключом RSA читайте здесь: Взлом Гугла, Твиттера и многих банков.)
Многоликий алгоритм Евклида
Все мы знаем, что такое наибольший общий делитель двух целых чисел. Напомню, что если есть два натуральных числа a и b, то их НОД(a, b) – это наибольшее из чисел d, таких, что а делится на d и b делится на d. Например:НОД(26, 169) = 13, НОД(100, 14) = 2, НОД(16, 28) = 4.
Давайте вспомним, как мы искали НОД и НОК в пятом классе, когда нам только объясняли, что это такое. Мы раскладывали числа на простые и смотрели, с какими степенями входит каждое из простых чисел в соответствующие произведения, потом брали минимум по этим степеням, перемножали и получали НОД. НОК искали как-то похожим образом. Кто хоть что-то слышал о простых числах, понимает, что разложение числа на простые – очень затратный процесс. Скажем, если ввести трехсотзначное число в кампутер и заставить его разложить его на простые, у него уйдут не минуты, не часы, не дни и даже не годы. Современным компьютерам эта задача не по зубам. Однако почти любому компьютеру под силу достаточно быстро найти НОД двух трехсотзначных чисел. Для этого существует алгоритм Евклида.
Сам алгоритм заключается в следующем:
Пусть даны числа a и b, для которых нужно найти НОД (кстати, наши коллеги на западе называют его gcd – Greatest Common Divider). Разделим а с остатком на b, и представим в виде: a = q * b + r. Если d – общий делитель a и b, то, очевидно, r также делится на d, так как на d делятся обе части равенства. Значит, НОД (a, b) = НОД (b, r). Затем проделаем ту же самую процедуру, пока у нас наконец не станет остаток 0.
Алгоритм весьма примитивный, но играет наиважнейшую роль в теории чисел и не только, например, при помощи него доказывается практически весь тривиум теории чисел, он применяется в методе Штурма поиска корней многочлена, при помощи него строятся цепные дроби, решаются линейные диофантовы уравнения, в высшей алгебре он широко используется в теории колец (есть даже так называемые Евклидовы кольца, в которых существует аналог алгоритма Евклида), а также занимает центральную роль в шифровании с открытым ключом, которое имеет дикую популярность в современном мире. Его привлекательность в его простоте, как человеческой, так и алгоритмической (для тех, кто шарит: алгоритм Евклида дольше всего работает на числах Фибоначчи – за О(log n)).
Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite
