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