7. [25] Проанализируйте задачи программирования метода решета - алгоритм D - для двоичного компьютера в случае, когда табличные значения для модулей rrii заполняют не точно целое число слов памяти.

► 8. [23] {Решето Эратосфена, 3 в. до н. э.) Следующая процедура позволяет найти все нечетные простые числа, меньшие данного целого числа N, поскольку она, удаляет все непростые числа. Выполнение процедуры начинается с того, что для всех нечетных целых чисел от 1 до N последовательно вычеркиваются числа р, Рк{рк + Рк{рк + А), ..., кратные к-му простому числу рк при к = 2, 3, 4, ..., пока не будет найдено такое простое число Pk, для которого р1 > N.

Покажите, как превратить описанную процедуру в алгоритм, пригодный для прямой реализации в компьютере, без использования операций умножения.

9. [М25] Пусть п - нечетное целое число и п > 3. Покажите, что если число Л(п) из теоремы 3.2.1.2В является делителем числа п - 1, но не равно п - 1, то п должно иметь вид pip2 - Pt, где все pi -различные простые числа и t >3.

► 10. [М26] (Джон Селфридж (John Selfridge).) Докажите, что если для любого простого делителя р числа п - 1 существует такое Хр, что Хр"" modn ф 1, а Хр~ modn = 1, то п-простое число.

11. [М20] Что выведет алгоритм Е, если N = 197209, = 5, m = 1? [Указание. x/S-197209 = 992 + 1,495,2,495,1,1984 .]

► 12. [М2(?] Разработайте алгоритм, который, используя выходные данные алгоритма Е, находит подходящий простой множитель Л, который обеспечивает возможность алгоритму Е формировать достаточно данных для вывода решения уравнения (18).

13. [НМ25] (Дж. Д. Диксон (J. D. Dixon).) Докажите, что как только алгоритм из упр. 12 представляется решением (х, ео,..., бт), показатели степени в котором линейно зависят по модулю 2 от показателей степени в предыдущих решениях, когда число N имеет различные простые множители, а величина х выбирается случайно, вероятность того, что разложение на простые множители не будет найдено, равна 2".

14. [М20] Докажите, что при выполнении шага ЕЗ алгоритма Е число Т никогда не кратно нечетному простому множителю р, для которого выполняется неравенство

(fcN)p-Vodp> 1.

► 15. [МЗ4] (Люка (Lucas) и Лемер (Lehmer).) Положим, что Р и Q - взаимно простые целые числа, и пусть С/о = О, C/i = 1,,1+1 = РСп-QCn-i при п > 1. Докажите, что если N - положительное целое число, взаимно простое с числом 2Р - 8Q, и если Un+i mod N = 0, а С/(лг+1)/р mod Л ф О для каждого простого числа р, делящего Л + 1, то Л - простое число. (В результате получаем .метод проверки принадлежности чисел к простым числам в случае, когда известны делители числа N + \, а не делители числа N - 1. Значение Um можно вычислить за O(logm) шагов, как в упр. 4.6.3-26.) [Указание. См. доказательство теоремы L.]

16. [М50] Бесконечно ли множество простых чисел Мерсенна?

17. [М25] (В. Р. Пратт (V. R. Pratt).) Полное доказательство принадлежности чисел к простым при помощи обратной теоремы Ферма принимает вид дерева с узлами {q,x), где q и X - положительные целые числа, удовлетворяющие следующим условиям, (i) Если узлы {qi,xi), {qt,Xt) порождены узлом {q,x), то q = q\...qt + l- [В частности, если (9, х) -младший потомок, то q = 2.] (ii) Если узел (г, у) порожден узлом (9, х), то х(9-1)/mod? 1. (iii) Для каждого узла {q,x) выполняется условие х~ mod? = 1.

Из этих условий следует, что число q простое и х есть простой корень по модулю q для всех узлов {q,x). [Например, дерево

.(1009,11).

(2,1)2,1)(2,1) (2,1) (7,3)(3,2)(3,2)

X \ \ \

(2,1) (3,2) (2,1) (2,1)

(2,1)

показывает, что 1009-простое число.] Докажите, что подобное дерево с корнем {q,x) содержит не более f{q) узлов, где функция / довольно медленно возрастает.

► 18. [НМ23] Приведите эвристическое доказательство соотношения (7) по аналогии с выводом соотношений (6), рассмотренных в этом разделе. Чему равна приближенная вероятность того, ЧТ0р(-1 < y/ptf

► 19. [М25] (Дж. М. Поллард (J. М. Pollard.) Покажите, как вычислить число М, которое делится на все нечетные простые множители р, такие, что р - 1 является делителем некоторого заданного числа D. [Указание. Рассмотрите числа вида а" - 1.] Такое число М полезно при разложении чисел на простые множители, поскольку множитель числа Л может быть получен в результате вычисления gcd{M,N). Постарайтесь развить эту идею и сформулировать эффективный метод нахождения с высокой вероятностью простых множителей р данного числа N для случая, когда все простые степенные множители для чисел р - 1 меньше 10, кроме, может быть, одного, меньшего 10. [Например, при помощи такого метода будет обнаружен второй по величине простой множитель, который делит (15), так как он равен 1 -f 2 • 5 • 67 • 107 199 • 41231.]

20. [М4О] Рассмотрите упр. 19, подставив в условие р + 1 вместо р - 1.

21. [М49] (Р. К. Ги (R. К. Guy).) Пусть тп(р) - число итераций, необходимых алгоритму В для выделения простого множителя р. Будет ли выполняться равенство тп(р) = 0(y/p\ogp) при р -+ оо?

► 22. [МЗО] (М. О. Рабин (М. О. Rabin).) Пусть для данного числа п р„-вероятность того, что алгоритм Р дает ошибочный результат. Покажите, что Рп < для всех п.

23. [МЗЗ]. Символ Якоби (2) по определению равен -1, О или +1 для всех целых чисел р > О и всех нечетных целых чисел q > 1 в соответствии со следующим правилом: (2) = р(9-1)/2 модулю q), когда q - простое число, (2) = () ... (), когда число q равно произведению q\...qt и t простых чисел (необязательно различных). Таким образом, символ Якоби является обобщением символа Лежандра (см. упр. 1.2.4-47).

a) Докажите, что () удовлетворяет следующим зависимостям, которые позволяют эф-

фективно его вычислять: (2) = 0; (i) = 1; () = (); () = {-Х-У; (f) =

()(); (2) = (-l)p~"~/(), если оба числар и 9 нечетны. [Последняя закономерность, которая представляет собой обратную зависимость и сводит вычисление () к вычислению (J), доказана в упр. 1.2.4-47(d) для pviq, являющихся простыми числами; поэтому в таком особом случае можно считать данную закономерность справедливой.]

b) (Соловей (Solovay) и Штрассен (Strassen).) Докажите, что если п - нечетное число, но не простое, то количество целых чисел х, таких, что 1<х<пи0 () s х"" (по модулю п), не превышает величины ip{n). (Значит, следующая процедура с вероятностью, равной как минимум 1/2, для всех фиксированных чисел п корректно

определяет, является ли данное число п простым. "Сгенерировать случайное число X в интервале 1 < х < п. Если О ф () = х"" (по модулю п), сказать, что п является, вероятно, простым; в противном случае сказать, что число п, определенно, не является простым.") с) (Л. Моньер (L. Monier).) Докажите, что если п и х -числа, для которых алгоритм Р делает вывод, что "п, вероятно, простое", то О () s x"~i (по модулю п). [Следовательно, алгоритм Р является основным при выполнении проверки в случае (Ь).]

► 24. [М25] (Л. Эдлеман (L. Adleman).) Если п > 1 и нечетно, а х > 1-целое число, будем говорить, что число п "проходит проверку алгоритмом Р посредством х", если либо X mod п = О, либо выполнение шагов Р2-Р5 приводит к заключению, что число п, вероятно, простое. Докажите, что для любого N существует множество положительных целых нечетных чисел xi, ..., Хт < А для т < [Ig N], такое, что положительное нечетное целое число в интервале 1 < п < Л будет простым тогда и только тогда, когда оно проходит проверку алгоритмом Р посредством чисел х для х = xi mod n, ..., х = Xm mod п. Таким образом, процесс вероятностной проверки "простоты", в принципе, может быть превращен в эффективный инструмент проверки, устраняющий всякие сомнения. (Сейчас не требуется приводить эффективный способ вычисления величин xj; нужно только доказать, что та,кие величины существуют.)

25. [НМ41] (Б. Риман (В. Riemann).) Докажите, что

где суммирование выполняется по всем комплексным числам <т + ir, таким, что г > О и С(<т + гт) = 0.

► 26. [М25] (Г. К. Поклингтон (Н. С. Pocklington), 1914.) Пусть N = fr+1, где О < г < f+1. Докажите, что число Л будет простым тогда, когда для каждого простого делителя р числа / существует такое целое число Хр, что х" modN = gcd{xp~ - I, N) = I.

► 27. [МЗО] Покажите, что существует способ проверки принадлежности к простым числам чисел вида Л = 5-2" + 1, использующий приблизительно столько же операций вычисления квадратов по модулю N, сколько применялось в способе Люка-Лемера (Lucas-Lehmer) проверки чисел Мерсенна в теореме L. [Указание. См. предыдущее упражнение.]

28. [М27] .Для данных простого числа р и положительного целого числа d найдите значение функции f{p,d), среднее число случаев, когда число р делит - dB (учитывая кратность), если А и В - независимые случайные целые числа за исключением условия ALB.

29. [М25] Докажите, что кол11чество положительных целых чисел < п, простые множители которых принадлежат множеству простых чисел {pi,... ,ртп}, не меньще m/г!, если

г = [log n/log PmJ и Pi < • • < pm-

30. [HM35] (Дж. д. Диксон (J. D. Dixon) и Клаус-Петер Шнорр (Claus-Peter Schnorr).) Пусть pi < • • • < Рт-простые числа, не делящие нечетное число N, и пусть г - четное целое число, не превышающее величины log Ayiog рт Докажите, что количество целых чисел А, принадлежащих интервалу Q < X < N к таких, что Х mod N = р\... р, не меньше irf/r\. Указание. Положите, что разложение числа N на простые множители имеет вид q/. Покажите, что последовательность показателей (е i,..., бт) приводит к 2** решениям X в случае выполнения неравенства ei + • • + вт < г и что р... р есть квадратичный остаток по модулю qi при 1 < г < d.. Такие последовательности показателей могут быть вычислены как упорядоченные пары (ei,..., е; е/,... ,ет), где el Н-----\-ет <