Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 9

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 3 4 5 6 7 8 < 9 > 10 11 12 13 14 15 .. 125 >> Следующая


б) Объяснить, как переводятся числа из двоичной системы в шестнадцатиричную и обратно и почему эти операции требуют много меньше времени, чем в полученной в примере 11 общей оценке для перевода из двоичной системы в 6-ичную.

8. Описать двоичные операции при вычитании битов аналогично тому, как это было сделано в тексте для сложения (список из 5 возможностей).

9. а) Используя обозначение О-большое, оценить в терминах простой функции от п число двоичных операций при вычислении 3" в двоичной системе.

б) То же самое для пп.

10. Оценить в терминах простой функции от п и N число двоичных операций при вычислении Nn.

11. Для суммы квадратов первых п натуральных чисел справедлива формула

а) Используя обозначение О-большое, оценить в терминах п число двоичных операций, требующихся для вычисления левой части этого равенства.

б) Оценить число двоичных операций, требующихся для вычисления правой части этого равенства.

12. Используя обозначение О-большое, оценить число двоичных операций, требующихся для умножения т x n-матрицы на п x s-матрицу, если все элементы матриц не превосходят т.

13. Цель этого упражнения — оценить в терминах п число двоичных операций, требующихся для вычисления произведения всех простых чисел, меньших п. При этом предполагается, что список всех простых чисел, не превосходящих п, уже составлен.

а) Обозначим 7г(п) число простых чисел, не превосходящих п. Согласно теореме о распределении простых чисел 7г(п) имеет асимптотику re/logra. Это означает, что nJі "g „ стремится к 1 при п —> оо. Используя этот факт, оценить число двоичных разрядов в произведении всех простых чисел, меньших п.

п

п(п + l)(2n + 1)

§ 2. ДЕЛИМОСТЬ И АЛГОРИТМ ЕВКЛИДА

13

б) Найтн границу для числа двоичных операций при любом из умножений, которые производятся при вычислении этого произведения.

в) Оценить число двоичных операций, требующихся для вычисления произведения всех простых чисел, меньших п.

14. а) Пусть надо проверить простоту числа п при помощи последовательного деления на все нечетные числа, не превосходящие у/п. Оценить число двоичных операций.

б) В постановке п. а) дополнительно предположим, что имеется список простых чисел, не превосходящих у/п. Тогда можно ограничиться делением на числа из этого списка (а не делить на все нечетные). Дать оценку числа двоичных операций в этом случае. Использовать теорему о распределении числа простых чисел.

15. Оценить время, необходимое для проверки того, имеет ли число п простой делитель, не превосходящий т. Предположим, что имеется список всех простых чисел, не превосходящих т. Опять воспользоваться теоремой о распределении числа простых чисел.

16. Пусть п — очень большое целое число, записанное в двоичной системе счисления. Найти простой алгоритм вычисления [у/п~\ за 0(log3 п) двоичных операций. Здесь [ ] — целая часть числа.

§ 2. Делимость и алгоритм Евклида

Делители и делимость. Для данных целых чисел а и Ь говорят, что а делит Ь (или Ь делится на а), и используют обозначение а\Ь, если существует такое целое число d, что b — ad. В этом случае а называют делителем Ь. Любое целое число b > 1 имеет, по крайней мере, два положительных делителя: 1 и 6. Под собственным делителем b подразумевают любой положительный делитель, не равный Ь, а под нетривиальным делителем b — любой положительный делитель, не равный 1 или Ь. Простым числом, по определению, является целое число, большее 1, которое не имеет положительных делителей,'отличных от 1 и самого себя; число называется составным, если оно имеет, по крайней мере, один нетривиальный делитель. Следующие свойства делимости легко выводятся непосредственно из определений:

1. Если а\Ь и с — любое целое число, то а\Ьс.

2. Если а\Ь и Ь\с, то а\с.

3. Если а\Ь и а\с, то a\b ± с.

Для простого р и целого неотрицательного числа а мы используем запись ра\\Ь, подразумевая, что ра — наивысшая степень р, делящая 6, т.е. ра\Ь, а ра+1 /Ь. В этом случае говорят, что р° точно делит Ь.

Основная теорема арифметики утверждает, что любое натуральное число п может быть записано в виде произведения простых чисел единственным образом (с точностью до перестановки сомножителей). Принято записывать это разложение в виде произведения различных простых сомножителей в соответствующих степенях, располагая простые числа в порядке возрастания. Например,

14

ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ

4200 = 23 • 3 • 52 • 7.

Следующие два свойства делимости вытекают из основной теоремы.

4. Если простое число р делит ab, то р\а или р\Ь.

5. Если т\а и п\а и если m и га не имеют общих делителей, больших 1, то тп\а.

Из единственности разложения целых чисел на простые множители следует также простой способ отыскания всех делителей п по его разложению. А именно, любой делитель d числа п должен быть произведением тех же простых сомножителей в степенях, не превышающих степени, точно делящие п. Таким образом, если р^Цп, то p®\\d для некоторого /3, удовлетворяющего условию 0 ^ ? ^ а. Например, для нахождения делителей числа 4200 нужно взять 2 в степени 0, 1, 2 или 3, умножить на 3 в степени 0 или 1, на 5 в степени 0, 1 или 2 и на 7 в степени 0 или 1. Число всех сомножителей, таким образом, есть произведение числа способов выбора степени для каждого простого сомножителя, которое, в свою очередь, равно а + 1. Иначе говоря, число п — Pi1P22 ¦ ¦ -р"г имеет (q1 + 1)(«2 + 1) • • ¦ (аг + 1) различных делителей. В частности, у числа 4200 их 48.
Предыдущая << 1 .. 3 4 5 6 7 8 < 9 > 10 11 12 13 14 15 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed