if, ei + .--+e,; < ги

(pf.. .рш-)"-/ = (p!" .. .Рш-)-/ (по модулю 90 при 1 < г < d.

31. [М20] Используя результаты упр. 1.2.10-21, оцените вероятность того, что алгоритм разложения на простые множители Диксона (описанный перед изложением теоремы D) вычисляет менее чем 2т выходных значений.

► 32. [М21] Покажите, как улучшить RSA-схему кодирования так, чтобы не было проблем с сообщениями < в том смысле, что длина сообщений не должна существенно увеличиться.

33. [М50] Докажите или опровергните следующее утверждение: существует достаточно эффективный алгоритм, такой, что если для заданного числа N = pq, простые множители которого удовлетворяют условию р = q = 2 (по модулю 3), и заданного значения mod N он с вероятностью, не являющейся пренебрежимо малой, может найти значение х mod N, то существует достаточно эффективный алгоритм, способный с подобной вероятностью найти множители числа N. [Если данное утверждение удастся доказать, это будет означать не только то, что проблема кубического корня так же сложна, как и проблема разложения на простые множители, но и то, что как RSA-схема, так и SQRT-схема обладают одним и тем же неустранимым недостатком.]

34. [МЗО] (Петер Уайнбергер (Peter Weinberger).) Предположим, что в RSA-схеме N = pg и известно число тп, такое, что по меньшей мере для 10" всех положительных целых чисел X выполняется равенство xmodN = 1. Поясните, как без больших трудностей решить задачу разложения на простые множители числа N, если число тп не слишком велико (скажем, тп < N°).

► 35. [М25] (X. К. Уильяме (Н. С. Williams), 1979.) Пусть N -произведение двух простых чисел р и q, где р mod & = 3 и q mod 8 = 7. Докажите, что символ Якоби удовлетворяет равенству (j) = (j/) = -(7)1 и используйте его для построения схемы кодирования и/или декодирования, которая аналогична SQRT-блоку Рабина, исключив при этом двусмысленность сообщений.

36. [НМ24] Асимптотическая оценка времени выполнения алгоритма Е в виде уравнения (22) является слишком грубой для того, чтобы использовать ее для получения осмысленных значений числа N, если только оно не является очень большим, поскольку при значениях числа Л, с которыми обычно приходится иметь дело, величина InlnN всегда сравнительно мала. Выполните более тонкий анализ, позволяющий уточнить поведение уравнения (22) для приемлемых значений числа N. Поясните также, как выбирать значение 1птп, минимизирующее (22), за исключением случаев, когда множитель достигает величины exp(0(loglogA)).

37. [М27] Докажите, что квадратный корень из любого положительного целого числа D, если только оно не является точным квадратом, имеет периодическую цепную дробь вида

Vd = r + ai,... ,a„,2R,ai,... ,an,2R,au ... ,an,2R,... ,

где r = IVd\ и {ai,...,an) - палиндром (т. е. симметричная последовательность Oi = un+i-i при 1 < г < n).

38. [25] (Интересные простые числа.) Для О < d < 9 найдите наибольшее 50-разрядное простое число Pd, которое содержит максимально возможное количество десятичных разрядов, равных d. (Сначала найдите максимум по d, а затем - наибольшее такое число.)

39. [40] Для многих простых чисел р характерно свойство, состоящее в том, что числа 2р + 1 также являются простыми, например 5 - 11 -f 23 -f 47. Обобщая, можно сказать, что число q - преемник числа р, если pnq - оба простые числа и g = 2*р+1 для некоторого

к >0. Например, 2 -) 3 -) 7 -) 29 -) 59 -) 1889 3779 -) 7559 -) 4058207223809 ->• 32465 657 790473 -) 4462 046030 502692 971 872 257 -) 95(30 разрядов пропущено)37 -)•••; наименьший преемник для числа 95 ... 37 содержит 103 цифры.

Найдите максимально длинную цепочку преемников простых чисел.

► 40. [М36] (А. Шамир (А. Shamir).) Рассмотрим абстрактный автомат, который может в течение одного цикла выполнять операции х + у,х - у,хуи [х/у} над целыми числами X и у произвольной длины; длина таких чисел не имеет значения. Автомат хранит их в памяти с произвольным доступом и может выбирать для выполнения операций различные шаги программы в зависимости от того, будет ли для заданных чисел х и у выполняться равенство х = у. Назначение данного упражнения - показать, что в таком автомате можно применить изумительно быстрый способ разложения чисел на простые множители. (Поэтому, вероятно, будет достаточно трудно показать, что на реальных компьютерах разложение на простые множители выполнить исключительно сложно, хотя мы и подозреваем, что это так.)

a) Для заданного целого числа п > 2 найдите способ вычисления на таком гипотетическом автомате величины п\ за O(logn) циклов. [Указание. Если А-достаточно большое целое число, то биномиальные коэффициенты (™) = т\/{т - А)! А! можно легко вычислить по значению числа (А Ч-1)".]

b) Покажите, как на таком автомате вычислить число /(п) за 0(log п) циклов для заданного целого значения п > 2 со следующими свойствами: /(п) = п, если п - простое число, в противном случае /(п) -собственный делитель (необязательно простой) числа п. [Указание. Если п 4, то одной из таких функций /(п) является gcd(Tn(n),n), где тп(п) = т1п{тп тп! mod п = 0}.]

(Как следствие (Ъ), полное разложение на простые множители произвольно большого числа п можно найти, выполнив только O(logn) арифметических операций. Для заданного частичного разложения п = m ... Пг каждое из чисел п;, не являющихся простыми, можно заменить функциями /(п;) • (п( (п<)) за 0(lognj) = 0(logn) циклов. Этот процесс можно повторять до тех пор, пока все числа гц не станут простыми.)

► 41. [Afg(S] (Лагариас (Lagaiias), Миллер (Miller) и Одлыжко (Odlyzko).) Назначение этого упражнения - показать, что может быть вычислено количество простых чисел, меньших N, если принимать во внимание только простые числа, меньшие N, и, таким образом, вычислять величину n{N) за 0{N) шагов.

Положительное целое число, для которого все простые множители превышают число т, назовем т-долгожителем; так что один т-долгожитель останется в решете Эратосфена (упр. 8) после просеивания всех чисел, кратных простым числам, не превышающим т. Пусть f{x,m) - количество т-долгожителей, которое не превышает х, и пусть fk{x,m) - количество таких долгожителей; для которых имеется ровно к простых множителей (учитывая кратность).

a) Докажите, что n{N) = n{N) + f{N N) - 1 - f2{N\ N).

b) Поясните, как вычислить f2{N, N) no значениям 7г(х) для x < N. Используйте метод вычисления значения /2(1000,10) вручную.

c) Та же задача, что ив (Ь), но вместо f2{N,N) вычислите f2{N\N). [Указание. Используйте тождество f{x,pj) = f{x,pj-i) - f{x/pj,Pj-i), где pj есть j-e простое иро = 1.]

d) Проанализируйте структуры данных, необходимые для эффективного вычисления величин при решении задач (Ь) и (с).

42. [М35] (X. В. Ленстра (мл.) (Н. W. Lenstra, Jr).) Для заданного интервала О < г < S < N,B котором г ± S и N А. S, покажите, что можно найти все делители числа N, равные

= г (по модулю s), выполнив 0{\N/sY\ogs) хорошо подобранные арифметические операции над (IgУ)-битовыми числами. [Указание. Примените результаты упр. 4.5.3-49.]

► 43. [М4З] Пусть т = pq - г-битовое целое число Блюма, как в теореме 3.5Р, и пусть Qm = {у \ У = х niod m для некоторого х}. Тогда Qm имеет (р + l){q + 1)/4 элементов и каждый из этих элементов у € Sm имеет единственный квадратный корень х = у/у, такой, что X € Qm- Предположим, что G(y)-это алгоритм, который правильно предсказывает значение mod2 с вероятностью > + е, где у - случайный элемент Qm. Цель этого упражнения- доказать, что задача, решаемая при помощи G, почти так же трудна, как и задача разложения на простые множители числа тп.

a) Разработайте алгоритм A{G,m,e,y,S), который использует случайные числа, и алгоритм G для того, чтобы предсказать без обязательного вычисления л/у, будет ли данное целое число у принадлежать Qm- Результат выполнения алгоритма должен быть корректным с вероятностью > 1 - 5, а время Т{А) его выполнения не должно превышать величины 0{е~(log 5~)T{G)) в предположении, что T{G) > г. (Если T{G) < г2, в этой формуле замените T{G) величиной (T(G) + г).)

b) Разработайте алгоритм F{G, тп, е), который находит множители числа тп и ожидаемое время выполнения которого равно Т(Р) = 0(г(е~® + e~(log e~)Г(G))).

Указание. Для О < и < тп и фиксированного у € Qm положим ть = Vy/y mod тп и Ли = TV mod 2. Учтем, что \{-v) -\- \v = 1 и \{v\ -\- + Vn) = (Ani -f • + Xvn +

[{тvl-----1-rUm)/TnJ) mod 2. Имеем далее t{\v) = (tv + mXv); здесь величина

заменяет (D)modm. Если ±v € Qm, имеем t{±v) = Vvy, поэтому алгоритм G обеспечивает способ предсказания величины Ли для примерно половины всех v.

44. [МЗЗ] (Й. Хаастад (J. Hastad).) Покажите, что нетрудно найти х в случае, когда aw + aiix + ai2x + ацх = О (по модулю тп(), О < х < тп,, gcd(aio, аа, ai2, агз,тпг) = 1 и > 10 при 1 < г < 7, если тп{ ± rUj при 1 < г < j < 7. (Все переменные-целые числа, и все они, кроме X, известны.) Указание. Когда L - произвольная неособая матрица вещественных элементов, алгоритм Ленстра (Lenstra) и Ловача (Lovasz) [Matiematische Annalen 261 (1982), 515-534] эффективно находит ненулевой целочисленный вектор v = [vi,... ,Vn), такой, что длина {vL) < \/п2" det L".

► 45. [M4I] (Дж. М. Поллард (J. М. PoUaid) и Клаус-Петер Шнорр (Claus-Peter Schnorr).) Покажите, что для целых чисел х и у, заданных целых чисел а, Ь и п, для которых аЬ J. п и п нечетно, существует эффективный способ решения уравнения

х - ау = Ъ (по модулю п)

даже в том случае, когда неизвестно разложение на простые множители числа п. [Указание. Используйте тождество (х? - ау\){х2 - ау) = х - ау, где х = Х1Х2 - аухуг и

у = Х1У2 -ЬХ2У1.]

46. [НМЗО] (Л. Эдлеман (L. Adleman).) Пусть р-достаточно большое простое число и а - простой корень по модулю р; таким образом, все целые числа b в интервале 1 < Ь < р могут быть записаны в виде Ь = а" modp для некоторого единственного числа п из интервала 1 < п < р.

Используя идеи, аналогичные идеям из алгоритма Диксона разложения на простые множители, разработайте алгоритм, который почти всегда по заданному Ь находит число п за О(р) шагов для всех е > 0. [Указание. Начните с формирования набора чисел щ, таких, что число а" modp имеет только малые простые множители.]