Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
3. Предположим, что 6 взаимно просто с т, где т > 2, и что о и с — положительные целые числа. Доказать, что если 6" = —1 (mod т), bc = ±1 (mod m) и d = НОД (а, с), то bd = —1 (mod m) и a/d нечетно.
4. Доказать, что если р\Ьп + 1, то либо (i) p\bd + l для некоторого собственного делителя d числа п, для которого n/d нечетно, либо (ii) P=I (mod 2п).
5. Положим m = 224 + 1 = 16777217. а) Найти простое число Ферма, делящее т. б) Доказать, что любой другой простой делитель сравним с 1 по модулю 48. в) Разложить m на простые множители.
6. Разложить на множители З15 — 1 и З24 — 1.
7. Разложить на множители 512 — 1.
8. Разложить на множители 105 — 1, 106 — 1 и 108 — 1.
9. Разложить на множители 233 — 1 и 221 — 1.
10. Разложить на множители 215 - 1, 230 - 1 и 260 — 1.
11. а) Доказать, что если d = НОД (тп, п) и а > 1 есть целое число, то НОД (о771 - 1,ап - 1) = ad - 1.
б) Пусть нужно перемножить числа а и 6, записывающиеся в двоичной системе счисления к битами, причем к очень велико. Пусть / — фиксированное целое число, много меньшее к, и г = [4k/l] + 1. Выберем множество чисел m,-, 1 ^ і ^ г, так, что 1/2 < т,- < / для всех t и НОД (т,-,го;) = 1 при і ф j. Предположим, что большое число о представлено г-набором (оі,...,аг), где а,- — наименьший положительный вычет числа о по модулю 2m' — 1. Доказать, что каждое из чисел о, b и ab однозначно определяется своим г-набором, и оценить число двоичных операций, необходимых для построения г-набора числа ab по г-наборам чисел о и 6.
§ 4. РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ
33
ЛИТЕРАТУРА к ГЛАВЕ I
1. Brillhart J., Lehmer D.H., Selfridge J.L., Tuckerman В., Wagstaff S.S., Jr. Factorizations of 6" = ±1, 6 = 2, 3, 5, 6, 7, 10, 11, 12, up to High Powers. Providence: Amer. Math. Soc, 1983.
2. Dickson L. E. History of the Theory of Numbers. 3 volumes. N.Y.: Chelsea, 1952.
3. Guy R. K. Unsolved Problems in Number Theory. Heidelberg etc.: Springer, 1982.
4. Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers. 5th ed. Oxford: Oxford Univ. Press, 1979.
5. LeVeque W.J. Fundamentals of Number Theory. Reading: Addison-Wesley, 1977.
6. Rademacher H. Lectures on Elementary Number Theory. Krieger, 1977.
7. Rosen K. H. Elementary Number Theory and Its Applications. 3rd ed. Reading: Addison-Wesley.
8. Schroeder M. R. Number Theory in Science and Communications. 2nd ed. Heidelberg etc.: Springer, 1986.
9. Shanks D. Solved and Unsolved Problems in Number Theory. 3rd ed. N.Y.: Chelsea, 1985.
10. Sierpinski W. A Selection of Problems in the Theory of Numbers. Oxford: Pergamon, 1964.
11. Spencer D. D. Computers in Number Theory. Oxford-N.Y.: Computer Science Press, 1982.
ГЛАВА II
КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ
В этой главе мы предполагаем знакомство читателя с основными определениями и свойствами полей. Кратко напомним то, что нам потребуется в дальнейшем.
1. Поле — это множество F с операциями умножения и сложения, которые удовлетворяют обычным правилам: как умножение, так и сложение ассоциативны и коммутативны; справедлив дистрибутивный закон; существует аддитивная единица 0 и мультипликативная единица 1; существуют аддитивные обратный элемент и для всех отличных от нуля элементов — мультипликативные обратные элементы. Следующие примеры полей являются основными во многих областях математики: (1) поле Q, состоящее из всех рациональных чисел; (2) поле R вещественных чисел; (3) поле С комплексных чисел; (4) поле Z/pZ классов вычетов целых чисел по модулю простого числа р.
2. Векторное пространство можно определить над любым полем F при помощи тех же свойств, которые используются при определении векторного пространства над вещественными числами. Любое векторное пространство имеет базис, и число элементов в базисе называется его размерностью. Расширение, т.е. большее поле, содержащее F, является векторным пространством над F. Мы называем его конечным расширением, если оно представляет собой конечномерное векторное пространство над F. Степень конечного расширения — это его размерность как векторного пространства. Один из способов получить расширение поля F — это присоединить к нему новый элемент: мы обозначаем через К = F(a) поле, состоящее из всех рациональных выражений, образованных элементом а и элементами F.
3. Аналогично, кольцо многочленов можно определить над любым полем F. Оно обозначается F[X] и состоит из всех конечных сумм степеней X с коэффициентами из F. Многочлены в F[X] складываются и перемножаются так же, как многочлены с вещественными коэффици-
ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ
35
ентами. Степень d многочлена — это наибольшая степень X, которая встречается с ненулевым коэффициентом; в нормированном многочлене коэффициент при Xа есть 1. Будем говорить, что д делит /, где f,g Є F[X], если существует такой многочлен h Є F[X], что / = gh. Неприводимые многочлены / Є F[X] — это те многочлены, которые не делятся ни на какие многочлены меньшей степени, кроме констант; они играют ту же роль среди многочленов, что простые числа среди целых. Кольцо многочленов обладает свойством единственности разложения, т.е. любой нормированный многочлен разлагается, притом единственным (с точностью до порядка сомножителей) способом, в произведение нормированных неприводимых многочленов. (Ненормированный многочлен может быть однозначно представлен в виде такого произведения, умноженного на константу.)
