Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 213
Текст из файла (страница 213)
В разделе 31.6 рассматриваются степени заданного числа а по модулю п, а также представлен алгоритм повторного возведения в квадрат (гереагед-зг!папой а!8опгпгп) для эффективного вычисления величины а щоо и для заданных а, Ь и и. Эта операция является ключевой при эффективной проверке простоты чисел и для многих современных криптографических схем. В разделе 31.7 описывается криптографическая система с открытым ключом КБА. В разделе 31.8 исследуется рандомизированный тест простоты чисел, с помощью которого можно организовать эффективный поиск больших простых чисел, что является важной задачей при создании кяючей для криптографической системы КЯА. Наконец в разделе 31.9 представлен обзор простого, но эффективного эвристического подхода к задаче о разложении небольших целых чисел на множители.
Интересно, что задача факторизации — одна из тех, которой, возможно, лучше было бы оставаться трудноразрешимой, поскольку от того, до какой степени трудно раскладывать на множители большие целые числа, зависит надежность КВА-кодирования. !лала 3!.
Теоретико-числовые алгоритмы 969 Размер входных данных и стоимость арифметических вычислений Поскольку нам предстоит работать с большими целыми числами, следует уточнить, что будет подразумеваться под размером входных данных и под стоимостью элементарных арифметических операций. В этой главе "большйе входные данные" — это обычно входные данные, содержащие "большие целые числа", а не "большое количество целых чисел" (как зто было в задаче сортировки).
Таким образом, размер входных данных будет определяться количеством битов, необходимых для представления этих данных, а не просто количеством чисел в них. Время работы алгоритма, на вход которого подаются целые числа аы аз,..., аы является налнномннльным (ро!упоппа1), если он выполняется за время, которое выражается полиномиальной функцией от величин 1к ам 1яаз,..., 1я ахи т.е. если это время является полиномиальным от длины входных величин в бинарном представлении. В большей части настоящей книги было удобно считать элементарные арифметические операции (умножение, деление или вычисление остатка) примитивными, т.е.
такими, которые выполняются за единичный промежуток времени. При таком предположении в качестве основы для разумной оценки фактического времени работы алгоритма на компьютере может выступать количество перечисленных арифметических операций, выполняющихся в алгоритме. Однако если входные числа достаточно большие, то для выполнения элементарных операций может потребоваться значительное время, и удобнее измерять сложность теоретико-числового алгоритма количеством битовых операций (Ь11 орегаг(оп). В этой модели для перемножения двух 33-битовых целых чисел обычным методом необходимо 6(!3з) битовых операций.
Аналогично операцию деления !3-битового целого числа на более короткое целое число или операцию вычисления остатка от деления !3-битового целого числа на более короткое целое число с помощью простого алгоритма можно выполнить за время г3(!39) (см. упр. 31.1.12). Известны и более быстрые методы. Например, время перемножения двух !3-битовых целых чисел методом декомпозиции равно 0(!3!Яз), а время работы самого быстрого из известных на сегодняшний день методов равно 9(!31к!31к1й!3). Однако на практике зачастую наилучшим оказывается алгоритм со временем работы 9(,3з), и наш анализ будет основываться именно на этой оценке. В общем случае алгоритмы в этой главе анализируются как в терминах количества арифметических операций, так и в терминах количества битовых операций, требуемых для их выполнения.
Р10 Часть гп. Избранные темы 31.1. Элементарные понятия теории чисел В этом разделе приведен краткий обзор понятий, которые используются в элементарной теории чисел, изучающей свойства множества целых чисел Ж (..., — 2, — 1,0, 1,2,...) и множества натуральных' чисел !з( = (0,1,2,...). Делимость и делатели Основным в теории чисел является понятие делимости одного целого числа на другое. Обозначение г( ! а (читается как "г( делит а" или ма делится на г(") подразумевает, что для некоторого целого числа й выполняется равенство а = Ы. Число 0 делится на все целые числа.
Если а > 0 и г( ) а, то ф < !а~. Если г( ~ а, то говорят также, что о — кравзио (шц11!р!е) г(. Если о не делится на г(, то пишут гз' ! а. Если г( ( а и г1 > О, то говорят, что г( — дсаивксль (6!н!йог) числа а. Заметим, что 11 ~ а тогда и только тогда, когда — с( ~ о, поэтому без потери общности делители можно определить как неотрицательные числа, подразумевая, что число, противоположное по знаку любому делителю числа а, также является делителем числа а.
Делитель числа а, отличного от нуля, лежит в пределах от 1 до !а~. Например, делителями числа 24 являются числа 1, 2, 3, 4, 6, 8, 12 и 24. Каждое целое число а делится на тривиальные двштсли (1пгйа! 61н!йога) 1 и а. Нетривиальные делители числа а называются также миожнвзсаями (Гас1огй) а. Например, множители числа 20 — 2, 4, 5 и 10. Простые и составные числа Целое число а > 1, единственными делителями которого являются тривиальные делители 1 и а, называют лросвзым числом (рппзе пцшЬег) или просто простим. Простые числа обладают многими особыми свойствами и играют важную роль в теории чисел.
Ниже приведено 20 первых простых чисел в порядке возрастания: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 . В упр. 3!.1.2 предлагается доказать, что простых чисел бесконечно много. Целое число а > 1, которое не является простым, называется сосвуавнмм (сошроййе). Например, число 39 — составное, поскольку 3 ~ 39. Целое число 1 называют единицей (шп1), и оно не является ни простым, ни составным.
Аналогично целое число 0 и все отрицательные целые числа также не являются ни простыми, ни составными. Определение натуральных чисел в американской литературе отличаегсд от определенна натуральных чисел в отечественной математике, где и = (1,2,...). В лапкой главе мы будем использовать одределсние нтуральных чисел из оригинального издание книги — Прежнее. ред.
971 Глава 31. Геореелало-числовые алгоритыы Теорема о делении, остатки и равенство по модулю Относительно заданного числа и все целые числа можно разбить на те, которые являются кратными числу п, и те, которые не являются кратными числу и. Ббльшая часть теории чисел основана на уточнении этого деления, в котором последняя категория чисел классифицируется в соответствии с тем, чему равен остаток их деления на и. В основе этого уточнения лежит сформулированная ниже теорема (ее доказательство здесь не приводится, но его можно найти, например, в учебнике Найвена (!л!1теп) и Цукермана (Лис)сеппап) [2б3)). Теорема 31.1 (Теорема о делении) Для любого целого а и любого положительного целого п существует единственная пара целых чисел д и г, таких, что 0 < г < и и а = дп + г. Величина д = [а[п] называется частным (ццойеп!) деления.
Величина г = а шое! и называется остатком (геш!пбег или геаЫне) деления. Таким образом, и [ а тогда и только тогда, когда а шол) и = О. В соответствии с тем, чему равны остатки чисел по модулю и, их можно разбить на и классов эквивалентности. Класс эквивалентности но модулю и (е<рита!епсе с!ааз шодн!о п), в котором содержится целое число а, имеет вид [а]„= (а + )еп: 1е Е л') Например, [3]7 = (..., — 11, — 4,3, 10,17,...); другие обозначения этого множества — [ — 4]т и [10]т. Используя обозначения на с. 79, можно сказать, что запись а е [Ь]„— это то же самое, что и запись а = Ь (шее) и). Множество всех таких классов эквивалентности имеет вид л.„= ([а]„: О < а < п — 1) (31.!) Когда вы видите определение Ж„= (0,1,...,и — 1), (31.2) вы должны читать его как эквивалентное уравнению (31.1), понимая, что 0 представляет [0]„, 1 представляет [Ц„и т.дд каждый класс представлен своим наименьшим неотрицательным элементом.
Однако при этом следует иметь в виду именно соответствующие классы эквивалентности. Например, — 1 в качестве члена класса л.„обозначает [п — Ц„, поскольку — 1 = п — 1 (шоб и). Общие делители и наибольшие общие делители Если д является делителем числа а, а также делителем числа 6, то д представляет собой общий делитель чисел а и 6. Например, делителями числа 30 являются 1, 2, 3, 5, 6, 10, 15 и 30, так что общими делителями чисел 24 и 30 являются 1, 2, 3 и 6. Заметим, что 1 — общий делитель двух любых целых чисел. Часть Ргт Избранные тены 972 (31.3) (31.4) из а / Ь и Ь | а следует а = хЬ . (31.5) Наибольший обийий делитель (йгеаГезГ сопппоп «1191зог) двух целых чисел а и 6, не являющихся одновременно нулем, — это самый большой из общих делителей чисел а и Ь; он обозначается как йсг((а,6)~.
Например, 8сг((24,30) = 6, 8сч((5,7) = 1 и ясг((0,9) = 9. Если числа а и 6 отличны от нуля, то значение 8сг((а, Ь) находится в интервале от 1 до ппп()а~, )Ь)). Величину ксг((0, 0) считаем равной нулю; это необходимо для универсальной применимости стандартных свойств функции йсг( (как, например, в уравнении (31.9) ниже). Ниже перечислены элементарные свойства функции йсг(: Сформулированная ниже теорема дает полезную альтернативную характеристику функции 8со(а, Ь). Теорема 31.2 Если а и Ь вЂ” произвольные целые числа, не равные одновременно нулю, то величина 8сг((а,Ь) равна наименьшему положительному элементу множества (ах + (л): х, у я К) линейных комбинаций чисел а и Ь.
Доказательство. Обозначим через в наименьшую положительную из таких линейных комбинаций чисел а и Ь, и пусть в = ах + Ьу при некоторых х, у е Т.. Пусть также а = (а/в (. Тогда из уравнения (3.8) следует а пзог( в = а — ав = а — д(ах+ 6у) = а (1 — Чх) + Ь( — Чу) Важное свойство общих делителей заключается в том, что из а ( а н е( ) Ь следует а' ~ (а+ Ь) и а ~ (а — Ь) . В более общем виде можно записать, что для всех целых х и у из е((она'(6 следует е(~ (ах+Ьу) . Кроме того, если а ( Ь, то либо )а! ( )6|, либо Ь = О, откуда вытекает, что 8сг((а, 6) = 8сс((Ь, а), 8сг((а, Ь) = 8сс(( — а, Ь), 8сб(а, Ь) = 8сг1()а/,)6)), бег((а,О) = )а/, 8сс1(а, )са) = )а/ для любого )с Е Т . зв течестиеннай интеретуре применяется таске абазнечение НОД(а, Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
