Алгоритм Эвклида.
Криптографические методы защиты информации
Доказательство. Опишем в явном виде алгоритм поиска неизвестных значений х и у. Для этого определим начальные значения. Будем считать, что гп > а > 0. Определим r_i = гп, го = а и, используя деление с остатком, определим последовательность. Расширяя алгоритм Эвклида, можно получить явное выражение НОД (а, га) через числа, а и га. Верна следующая лемма. Определение 9.3. Будем называть натуральное… Читать ещё >
Алгоритм Эвклида. Криптографические методы защиты информации (реферат, курсовая, диплом, контрольная)
Определение 9.3. Будем называть натуральное число d наибольшим общим делителем двух целых чисел а, т, если:
- 1. d является общим делителем, то есть da, dm;
- 2. d является наибольшим, то есть для любого общего делителя с выполнено cd.
Мы будем обозначать наибольший общий делитель двух целых чисел а, т символом НОД (а, т).
Для вычисления наибольшего общего делителя двух чисел можно предложить алгоритм, который принято называть алгоритмом Эвклида — вычисления наибольшего общего делителя.
Будем считать, что гп > а > 0. Определим r_i = гп, го = а и, используя деление с остатком, определим последовательность.
где 0 < rfc+1 < rk для всех к = О, l,…, n+ 1. Верна следующая теорема.
Теорема 9.2 (см. [3, гл. 11). Пусть т > а > 0 — целые числа. Определим последовательность г _ i. г о, …, rn+i равенствами (9.2). Тогда найдется натуральное число п такое, что r"+i = О,.
и выполнено неравенство1.
Расширяя алгоритм Эвклида, можно получить явное выражение НОД (а, га) через числа а и га. Верна следующая лемма.
Лемма 9.2 (Лемма Везу). Пусть а. т — целые числа. Тогда найдутся такие целые х, у, что
Доказательство. Опишем в явном виде алгоритм поиска неизвестных значений х и у. Для этого определим начальные значения.
и последовательности чисел х, Х2,…, у, у2,…, гч, Г2,… равенствами.
для всех к = 0,1, —.
Тогда последовательность п, гг,… является последовательностью остатков, определенных в алгоритме Эвклида равенствами (9.2). Следовательно, для некоторого индекса п выполнено rn+i = О и гп — НОД (а, т).
Покажем, что для всех индексов к = —1,0,1,…, в выполнено равенство.
'Оценка сверху величины п была получена Габриэлем Ламе (Gabriel Lame), французским математиком, физиком и инженером, работавшим на протяжении 1820—1832 гг. в Институте корпуса инженеров путей сообщения в СанктПетербурге.
Действительно, в силу выбора начальных значений это равенство выполнено для к = —1,0. Предполагая, что оно выполнено для всех значений, меньших к + 1, получим.
Поскольку гп = НОД (а, Ь), то в качестве неизвестных значений х и у можно положить.
