Введение в современную криптографию
Алгоритм Эвклида и расширенный алгоритм Эвклида
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ПРЕДПОЛОЖЕНИЕ B.6
- АЛГОРИТМ B.7
| Алгоритм Эвклида и расширенный алгоритм Эвклида
Напомним из раздела 8.1, что gcd(a, b), наибольший общий делитель двух целых чисел a и b – это наибольшее целое число d, которое делит как a, так и b. Сформу- лируем простое предположение, относящееся к наибольшему общему делителю и затем покажем, как это приводит к эффективному алгоритму его вычисления. ПРЕДПОЛОЖЕНИЕ B.6 Пусть a, b > 1 при bƒ | a. Тогда gcd(a, b) = gcd(b, [a mod b]). ДОКАЗАТЕЛЬСТВО Если b > a, то актуально заявленное требование. Таким образом, допустим, что a > b. Запишем a = qb + r для q, r положительных целых чисел r < b (см. предположение 8.1); заметьте, что r > 0 поскольку bƒ | a. Так как r = [a mod b], докажем это предположение, показав, что gcd(a, b) = gcd(b, r). Пусть d = gcd(a, b). Тогда d делит как a, так и b, и, таким образом, d делит r = a − qb. По определению наибольшего общего делителя мы, таким образом, имеем gcd(b, r) ≥ d = gcd(a, b). Пусть dr = gcd(b, r). Тогда dr делит как b , так и r, и, таким образом, dr также делит a = qb + r. По определению наибольшего общего делителя мы, та- ким образом, имеем gcd(a, b) ≥ dr = gcd(b, r). Поскольку d ≥ dr и dr ≥ d, мы приходим к выводу, что d = dr. Указанное выше предполагает рекурсивный алгоритм Эвклида (алгоритм B.7) для вычисления наибольшего общего делителя gcd(a, b) двух целых чисел a и b. Коррект- 323 ность алгоритма полностью следует из предположения B.6. Что касается длительно- сти его работы, то далее мы покажем, что на входе (a, b) алгоритм делает менее 2 • «b» рекурсивных вызовов. Поскольку проверка, делит ли b a и вычисление АЛГОРИТМ B.7 Алгоритм Эвклида для наибольшего общего делителя Вход: Целые числа a, b при a ≥ b > 0 Выход: Наибольший общий делитель для a и b, если b делит a возвращает b в противном случае, возвращает GCD(b, [a mod b]) o[admb] могут быть сделаны в течение полиномиального времени в «a» и «b», это означает что весь алгоритм действует в течение полиномиального времени. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|