Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Наибольшим общим делителем двух данных целых чисел а и 6 (обозначаемым НОЯ (а,Ь) или просто (а,Ь)), не равных одновременно нулю, называется наибольшее целое число d, делящее и а, и Ь. Нетрудно доказать, что приведенное выше определение эквивалентно следующему: ИОД (а, Ь) — это единственное положительное число, которое делит а и b и делится на любой другой их общий делитель.
Если имеются разложения на простые множители двух чисел а и 6, — легко записать и НОД (а, Ь). Следует взять все простые числа, входящие в оба разложения, и каждое возвести в степень, равную минимуму из двух соответствующих показателей. Например, сравнивая разложение 10780 = 22 • 5 • 7 с приведенным выше разложением числа 4200, получаем, что НОД (4200,10780) = 22 • 5 • 7 = 140.
Наименьшее общее кратное чисел а и Ь обозначается HOK (а, 6) и по определению является наименьшим целым положительным числом, делящимся как на а, так и на Ь. Имея разложение на простые множители чисел а и 6, можно получить HOK (а,Ь), взяв все простые числа, входящие хотя бы в одно из разложений, и каждое возвести в степень, равную максимуму из двух показателей. Легко показать, что HOK (а, Ь) = |аЬ|/НОД (а,Ь).
Алгоритм Евклида. При работе с большими числами часто случается, что их разложение на простые множители неизвестно. В частности, важным направлением исследований в теории чисел явля-
ij 2. ДЕЛИМОСТЬ И АЛГОРИТМ ЕВКЛИДА
15
ется отыскание быстрых методов разложения больших чисел на простые множители. К счастью, существует сравнительно быстрый способ нахождения НОД (а,Ь) даже в том случае, когда неизвестны простые делители а или Ь. Он называется алгоритмом Евклида.
Алгоритм Евклида работает следующим образом. Чтобы найти НОД (а, 6), где а > Ь, сначала делят а на 6 и записывают частное и остаток T1: a = q^b + г\. Затем производят второе деление, в котором Ь играет роль а, а т\ — роль b: b = q2r\ + г2. Затем делят т\ на г2. Деление продолжают, каждый раз деля предпоследний остаток на последний, получая новые частное и остаток. Когда в конце концов получается остаток, который является делителем предыдущего остатка, то этот последний ненулевой остаток и есть наибольший общий делитель чисел а и Ь.
Пример 1. Найти НОД (1547,560).
Решение.
1547 =
2
560 + 427
560 =
1
427+ 133
427 =
3
133 + 28
133 =
4
28 + 21
28 =
1
21 + 7.
Так как 7|21, то НОД (1547,560) = 7.
Предложение 1.2.1. Алгоритм Евклида всегда дает наибольший общий делитель за конечное число шагов. Кроме того, для а > Ь
Time (нахождение НОД (а, Ь) по алгоритму Евклида) = O(\og\a)).
Доказательство. Доказательство первого утверждения детально изложено во многих учебниках по элементарной теории чисел, поэтому изложим его кратко. Во-первых, легко показать, что остатки строго уменьшаются с каждым шагом и, следовательно, в конце концов достигнут нуля. Чтобы убедиться, что последний остаток есть НОД, воспользуемся вторым определением НОД. Получаем, что если некоторое число делит и а, и Ь, то оно должно делить T1, a так как оно делит Ь и г\, то оно должно делить г2, и т.д. В конце концов, получаем, что оно должно делить последний ненулевой остаток. С другой стороны, переходя от последнего шага к предыдущему, легко видеть, что последний остаток должен делить все предыдущие остатки, а также а и Ь. Итак, это НОД, так как НОД — это единственное число, которое делит а и 6 и в то же время делится на любой их общий делитель.
16
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
Теперь докажем второе утверждение. Главный вопрос состоит в том, сколько раз производится деление. Покажем, что остатки не просто убывают, а убывают довольно быстро.
Лемма. Tj+2 < rj/2.
Доказательство леммы. Если Tj+1 ^ то сразу
получаем Tj+2 < ri+\ ^ rj/2- Пусть теперь г^+1 > rj/2. В этом случае
Следующее Деление Да.ЄТ Tj = I- Tj+I + Tj + 2 И Tj + 2 = Tj — Tj + I < Tj/2.
Лемма доказана.
Вернемся к доказательству теоремы. Так как за каждые два шага остаток уменьшается, по крайней мере, вдвое и так как остаток не может стать меньше 1, то производится самое большее 2 [log2 а] делений. Эта величина есть О (log а). Каждое деление производится над числа-ми, не превышающими а, и, следовательно, проводится за O(log а) двоичных операций. Таким образом, общее время работы составляет
2 3
О (log а) • О (log а) = О (log а), что и требовалось доказать.
Замечание. Если провести более тщательный подсчет числа двоичных операций, учитывая уменьшение чисел, участвующих в делении, можно улучшить оценку времени работы алгоритма Евклида до О (log а).
Предложение 1.2.2. Пусть d = НОД (а,Ь), где а > Ь. Тогда существуют такие целые числа и и v, что d = иа + bv. Другими словами, НОД двух чисел можно представить в виде линейной комбинации этих чисел с целыми коэффициентами. Кроме того, для нахождения чисел и и v достаточно O(log3 а) двоичных операций.
Схема доказательства. Проходя последовательность равенств в алгоритме Евклида снизу вверх и выражая каждый раз d через все более ранние остатки, в конце концов получаем выражение d через а и 6. Ha каждом шаге необходимо произвести одно умножение и одно сложение или вычитание. Таким образом, как легко убедиться, число двоичных операций снова есть О (log а).
