Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Пример 1 (продолжение). Чтобы представить 7 в виде линейной комбинации 1547 и 560,запишем
7 = 28 - 1 • 21 = 28 - 1 • (133 - 4 • 28) = 5 • 28 - 1 • 133 = 5 • (427 - 3 • 133) -1-133 = 5 • 427 - 16 • 133 = 5 • 427 - 16 • (560 - 1 • 427) = 21 • 427 - 16 • 560 = 21 • (1547 - 2 • 560) - 16 • 560 = 21-1547 - 58-560.
Определение. Говорят, что два целых числа а и Ь взаимно просты, если НОД (a, b) = 1, т.е. если а и Ь не имеют общих делителей, больших 1.
§ 2. ДЕЛИМОСТЬ И АЛГОРИТМ ЕВКЛИДА
17
Следствие. Если а и b— взаимно простые числа и а > Ь, то можно найти представление 1 в виде целочисленной линейной комбинации этих чисел за полиномиальное время, точнее, за O(log3 а) двоичных операций.
Определение. Для любого целого положительного п функция Эйлера f(n) определяется как число неотрицательных целых Ь, меньших п и взаимно простых с п:
?>{п)= |{0 < b < п J НОД (Ь,п) = 1}| .
def
Легко проверить, что ip(l) = 1 и что if(р) — р — 1 для любого простого р. Можно убедиться также, что для любого простого р
/ с*\ et Q-I a ( . I \
?{Р ) = P - P = Р \ р) '
Для этого достаточно заметить, что числа от 0 до ра — 1, которые не взаимно просты с ра, — это в точности те числа, которые делятся
а-1
на р, а их количество равно р
В следующем параграфе главе будет показано, что функция Эйлера <f(n) обладает «мультипликативными свойствами», что дает возможность быстро вычислять значение f(n), используя разложение числа п на простые множители. А именно, если п записано в виде произведения степеней различных простых чисел ра, то if(n) является произведением чисел ip(pa).
УПРАЖНЕНИЯ
1. а) Доказать следующие свойства отношения ра||Ь: (і) если ра]\а и р^\\Ь, то pa + ?\\ab; (ii) если ра||а, p0\\Ь и а < ?, то ра\\а ± 6.
б) Найти пример, опровергающий утверждение: если ра\\а тлра\\Ь, то ра\\а + Ь.
2. Сколько делителей имеет число 945? Перечислить их все.
3. Пусть п - положительное нечетное число.
а) Доказать, что существует взаимно однозначное соответствие между такими делителями числа п, которые меньше у/п, и такими, которые больше у/п. (В этой части п может быть и четным.)
б) Доказать, что существует взаимно однозначное соответствие между множеством тех делителей числа п, которые не меньше у/п, и множеством представлений п в виде разности s2 — t2 квадратов двух неотрицательных целых чисел. (Например, 15 имеет два делителя 5, 15, которые не меньше л/Г5, и 15 = 42 - I2 = 82 - 72.)
в) Укажите все возможные способы записи числа 945 в виде разности квадратов двух неотрицательных целых чисел.
4. а) Показать, что степень простого р, точно делящая га!, равна [п/р] + [п/р2] + [п/р3] + • • •• (Заметим, что эта сумма конечна.)
18
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
б) Найти степени чисел 2, 3, 5, 7, точно делящие 100!, а затем выписать разложение 100! на простые множители.
в) Пусть S(,(n) означает сумму цифр числа п в системе счисления по основанию 6. Доказать, что степень числа 2, точно делящая п!, равна n —S2(n). Вывести аналогичную формулу для произвольного простого р.
5. Найти d = НОД (360, 294) двумя способами: а) найдя разложение обоих чисел на простые множители, найти затем разложение d; и б) при помощи алгоритма Евклида.
6. При помощи алгоритма Евклида найти наибольший общий делитель для следующих четырех пар чисел и выразить его как линейную комбинацию этих чисел с целыми коэффициентами, а) 26, 19. б) 187, 34. в) 841, 160. г) 2613, 2171.
7. Часто можно ускорить поиск НОД по алгоритму Евклида, если использовать деление с отрицательным остатком, т.е. выбирать из равенств Tj = qj + 2rj + \ — ri+2 и rj = Я] +2rj +1 + ri + 2 то, в котором значение Tj+2 наименьшее. При этом всегда будет Tj + ? г; + ]/2. Решить все четыре примера из упражнения 6, используя этот метод. ¦- " -
8. а) Доказать, что следующий алгоритм находит d = НОД (а, 6) за конечное число шагов. Сначала заметим, что НОД (а, 6) = НОД (|а|, |6|), т. е. без ограничения общности можно предполагать, что а и 6 — положительные числа. Если а и Ъ оба четные, положим d = 2d', где d' = НОД (а/2, Ь/2). Если одно из этих двух чисел нечетное, а другое (скажем, 6) четное, то положим d = d1, где а" = НОД (а, 6/2). Если оба числа нечетные и различные, скажем, а > 6, то положим d = d', где d' = НОД (а — 6,6). Наконец, если а = 6, положим d = а. Повторяем этот процесс, пока не получаем последний случай (когда числа равны между собой).
б) Воспользоваться алгоритмом из пункта а) для нахождения НОД (2613, 217]), производя все действия в двоичной системе счисления, т.е. найти
НОД ((10100011010I)2, (10000111101I)2).
в) Доказать, что алгоритм в пункте а) требует всего 0(log2 о) двоичных операций (если а > 6).
г) Почему этот алгоритм в приведенном выше виде не всегда лучше алгоритма Евклида?
9. Пусть о много больше 6. Найти временную оценку сложности вычисления НОД (а, 6) в терминах О-большого, которая была бы лучше, чем О (log3 а).
10. Цель этой задачи — найти «наилучшую» оценку для числа делений в алгоритме Евклида. Числа Фибоначчи можно определить правилом /i = 1, /2 = 1, /п + 1 = /n + /п-1 для п ^ 2, или, что то же самое, матричным равенством
