Лабораторная работа №7
Тақырыбы: Некоторые алгоритмы расчета: Алгоритм Евклида. Обобщенный алгоритм Евклида. Алгоритм ранжирования.
Определение 1. Предположим, a и b — два положительных целых числа. Число c, которое является наибольшим из чисел, делящихся на a и b, называется их наибольшим общим делителем и обозначается как c=нод (a,b)=gcd(a,b) (обозначая наибольший общий делитель как gcd Аббревиатура английского слова «наибольший общий делитель» (заглавные буквы).
Например,
Чтобы найти наибольший общий делитель, вы можете использовать следующий алгоритм, известный как алгоритм Евклида.
Определение 1.
Вход: положительные целые числа
Выход: наибольший общий знаменатель.
1.WHILE b
2. .
3. RETURN
Пример 1. Покажем, как вычислить НОД(28,8) с помощью алгоритма Евклида:
Каждый столбец здесь представляет собой последовательную интерпретацию алгоритма. Процесс продолжается до тех пор, пока b не станет равным нулю. Тогда мы получим ответ (4) в значении переменной a.
Во многих криптографических системах подходит преобразование, определяемое следующей теоремой, известной как обобщенный алгоритм Евклида.
Обобщенный алгоритм Евклида используется для нахождения НОД(a,b) и чисел x,y. Введем три строки , , ), , , ), и T= , , ). Алгоритм записан в следующем виде.
Алгоритм 2. Обобщенный алгоритм Евклида.
Вход: - положительные целые числа
Выход: (1)-удовлетворяющий
(a,1,0), V
div ;
T ( mod
Результат находится в - строке. Операция в алгоритме делит это целое число:
.
Достарыңызбен бөлісу: |
