Введение в современную криптографию


Алгоритм Эвклида и расширенный алгоритм Эвклида



Pdf көрінісі
бет237/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   233   234   235   236   237   238   239   240   ...   249
Криптография Катц

Алгоритм Эвклида и расширенный алгоритм Эвклида
Напомним из раздела 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», 
это означает что весь алгоритм действует в течение полиномиального времени.


Достарыңызбен бөлісу:
1   ...   233   234   235   236   237   238   239   240   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет