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

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

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 12 13 14 15 16 17 < 18 > 19 20 21 22 23 24 .. 125 >> Следующая


Другое доказательство состоит в переходе к системе счисления по основанию 6. Запись числа 6П — 1 в такой системе состоит из п цифр 6—1 (например, 106 - 1 = 999999). С другой стороны, число 6П 1 + Ьп 2 + • • ¦ + б2 + 6 + 1 состоит из п единиц. Умножая 111 ... 111 на однозначное число 6—1, получим ((6 — 1)(6 — 1)(6 — 1) ¦•• (6 — 1)(6 — 1)(6-1))6 = 6п-1.

Следствие. Для любого целого 6 и любых целых положительных пит выполняется равенство

bmn - 1 = (6т - 1)(6т(п-1} + 6т(п_2) + • • • + 62т + Ьт + 1).

Доказательство. Просто подставим 6Ш вместо 6 в последнем предложении.

В качестве примера применения этого следствия находим, что 2 — 1 делится на 2 — 1 = 31 и на 2 — 1 = 127. Действительно, положим 6 = 2 и либо т — 5, п = 7, либо т — 7, п = 5.

Предложение 1.4.2. Пусть bum взаимно просты, а числа а ис — целые положительные. Если 6" = 1 (mod т), b° = 1 (mod то) ud = НОД (а, с), то 6=1 (mod то).

Доказательство. Используя алгоритм Евклида, можно записать d в виде d = иа + vc с целыми коэффициентами и и v. Легко проверить, что одно из двух чисел и и V положительно, а другое отрицательно или нуль. Положим для определенности и > 0, v ^ 0. Возведем теперь обе части сравнения 6" = 1 (mod то) в степень и, а обе части сравнения 6=1 (mod то) возведем в степень —v. Поделив полученные сравнения, получим bau с' ^ = I (mod то). Но аи + cv = d; таким образом, утверждение доказано.

Предложение I. 4. 3. Если р — простой делитель числа 6™ - 1, то либо (i) р\Ь — 1 для некоторого собственного делителя d числа

ij 4. РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ

31

п, либо (ii) р=1 (mod п). Если р > 2, а п нечетно, то в случае (H) P=I (mod 2п).

Доказательство. По условию bn = 1 (mod п); кроме того, по малой теореме Ферма Ьр_1 = 1 (mod р). По предыдущему предложению это означает, что bd = 1 (mod р), где d = НОД (п,р— 1). Если d < п, это означает, что p|6d — 1 для некоторого собственного делителя d числа п, т.е. имеет место случай (i). С другой стороны, если d = п, то поскольку d\p — 1, имеет место сравнение р = 1 (mod га). Наконец, если рига нечетны и га|р — 1 (т.е. имеет место случай (ii)), то, очевидно, 2п|р - 1.

Покажем теперь, как можно применять это предложение при разложении на множители некоторых больших целых чисел.

Примеры.

1. Разложить на множители 211 — 1 = 2047. Если р|2П - 1, то согласно нашему предложению р = 1 (mod 22). Поэтому проверяем р = 23, 67,89,. .. (на самом деле достаточно проверить лишь числа до \/2047 = 45,.. .). Сразу получаем разложение 2047 = 23 • 89. Совер-

13

шенно аналогичным способом легко показать, что 2 - 1 = 8191 есть простое число. Простые числа вида 2" — 1 называются «простыми числами Мерсенна».

12

2. Разложить на множители 3 — 1 = 531440. В соответствии

1 2

с предложением 1.4.3 сначала проверяем делители чисел 3 — 1,3 — 1,3 — 1,34 — 1 и те делители числа 3 — 1 = (З3 — 1)(33 + 1), которых не было в разложении З3 — 1. Так получаем 2 •5-7-13. Так как 531440/(24 -5-7-13) = 73 есть простое число, задача решена. Заметим, что, как и следовало ожидать, простое число, отсутствующее среди делителей чисел вида 3d — 1, где d — собственный делитель числа 12, а именно 73, — сравнимо с единицей по модулю 12.

35

3. Разложить на множители 2 — 1 = 34359738367. Сначала рассмотрим делители чисел 2d — 1 для d = 1,5,7. Это даст нам простые множители 31 и 127. Имеем (235 - 1)/(31 • 127) = 8727391. По нашему предложению все остальные простые делители должны быть сравнимы с 1 по модулю 70. Поэтому проверим, не являются ли 71,211,281,... делителями числа 8727391. Может показаться, что необходимо проверить все такие числа до \/8727391 « 2954. Однако сразу получается 8727391 = 71-122921, и остается проверить лишь числа до л/122921 Ps 350. Получаем, что 122921 — простое число. Итак, 235 - 1 = 31 • 71 • 127 • 122921 — разложение на простые множители.

Замечание. Каким образом в примере 3 можно производить вычисления на калькуляторе, который показывает, скажем, всего 8 десятичных знаков? Нужно просто разбивать числа на части. На-

32

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

г.35

пример, при вычислении 2 мы достигаем предела возможностей нашего калькулятора уже при 226 = 67108864. Чтобы умножить это число на 29 = 512, запишем 235 = 512 • (67108 ¦ 1000 + 864) = 34359296 • 1000 + 442368 = 34359738368. Далее, когда приходится де-

35

лить 2 - 1 на 31 • 127 = 3937, сначала надо разделить 34359738 на 3937, взять целую часть дроби [34^y3---] = 8727, а затем записать 34359738 = 3937 ¦ 8727 + 1539. Далее,

34359738367 _ (3937•8727 + 1539)•1000 + 367

3937 ~ 3937

1539367

= 8727000 +-= 8727391.

3937

УПРАЖНЕНИЯ

1. Докажите двумя различными способами, что если п нечетно, то 6" + 1 = (b + l)(bn_1 — b"~2 + • • • + б2 — 6 + 1). В одном доказательстве используйте полиномиальное тождество, в другом — вычисления в системе счисления по основанию Ь.

2. Доказать, что если 2" — 1 — простое, то в — простое, а если 2™ + 1 — простое, то п есть степень двойки. В первом случае простые числа называются простыми числами Мерсенна, как уже упоминалось выше, а во втором случае — простыми числами Ферма. Первые несколько чисел Мерсенна — это 3, 7, 31, 127; первые несколько чисел Ферма — это 3, 5, 17, 257.
Предыдущая << 1 .. 12 13 14 15 16 17 < 18 > 19 20 21 22 23 24 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed