Основы программирования



              

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


Q(a,b): b = 0

Теперь можно выписать алгоритм нахождения наибольшего общего делителя:

цел алгоритм НОД(вх: цел m, цел n) | дано: целые числа m, n, хотя бы одно отлично от нуля | надо: вычислить наибольший общий делитель пары (m, n) начало алгоритма | цел a, b, r; | // инициализация | a := m; b := n; | утверждение: НОД(a, b) == НОД(m, n); | | цикл пока b != 0 | | инвариант: НОД(a, b) == НОД(m, n) | | r := a % b; // находим остаток от деления a на b | | a := b; b := r; // заменяем пару (a, b) на (b, r) | конец цикла | | утверждение: b == 0 и НОД(a, b) == НОД(m, n); | ответ := a; конец алгоритма

Алгоритм Евклида - один из самых замечательных алгоритмов теории чисел и программирования. Работает он исключительно быстро, за время, линейно зависящее от длины записи входных чисел. (Действительно, легко показать, что за два выполнения тела цикла число b уменьшается не менее, чем в четыре раза. Следовательно, число выполнений тела цикла в худшем случае равно длине двоичной записи максимального из чисел a, b.) Это позволяет применять алгоритм Евклида к очень большим целым числам - например, к двухсотзначным десятичным. Алгоритм Евклида (более точно, расширенный алгоритм Евклида, который будет рассмотрен ниже) применяется для таких больших чисел в схеме кодирования с открытым ключом RSA, которая в настоящее время широко используется на практике для защиты информации.




Содержание  Назад  Вперед