где М = 7 + Ylk>2 f(k) \п(к)/к - константа Мертенса, равная

0.26149 72128 47642 78375 54268 38608 69585 90516;

см. F. Mertens, Crelle 76 (1874), 46-62; Greene, Knuth, Mathemsitics for the Analysis of Algorithms (Boston: Birkhauser, 1981), §4.2.3. В частности, число операций, выполняемых оригинальным алгоритмом Никомаха, равно N\nlnN+0(N). В упр. 5.2.3-15 и разделе 7.1 рассматриваются пути повышения эффективности методов просеивания для генерирования простых чисел.

9. Если р -делитель числа п для некоторого простого числа р, то р есть делитель числа А(п), но не числа п - 1. Если п = pip2, где pi < рз - все простые числа, то рз - 1 является делителем числа А(п), и поэтому pipj - 1 S О (по модулю р2 - 1). Поскольку рг = 1, то pi - 1 кратно р2 - 1, но это противоречит предположению, что pi < рг. [Значения п, для которых А(п) есть собственный делитель числа п - 1, называются числами Кармайкла (Carmichael). Например, приведем несколько малых чисел Кармайкла, содержащих более шести множителей: 3 11 17, 5-13 17, 7 11 13-41, 5-7 17 19-73, 5-7 17-73-8ai07. Имеется 8 241 число Кармайкла, меньшее 10, и существует хотя бы Cl{N) чисел Кармайкла, меньших N [см. W. R. Alford, А. Granville, С. Pomerauce, Annais of M&th. (2) 139 (1994,, 703-722].

10. Пусть kp - порядок числа Хр по модулю п и А - наименьшее общее кратное всех таких кр. Тогда А является делителем числа п - 1, но не делителем любого (п - 1)/р, поэтому А = п- 1. Поскольку Хр" mod п = 1, то <(п) кратно кр для всех р; следовательно. (р{п) > А. Но ip{n) < п - 1, если п - не простое число. (Другой способ доказательства заключается в том, что при помощи метода, рассмотренного в упр. 3.2.1.2-15, из элементов Хр строится элемент х, имеющий порядок п-1.)

Разложение 199 • 991 получается из первых или последних выходных данных. Краткость цикла и появление хорошо известного числа 1984 - это, вероятно, просто совпадение.

12. В следующем алгоритме используется вспомогательная [т + \) х {т + 1)-матрица с целочисленными элементами Ejk, О <j,k <т, входной вектор {bo,bi,... ,Ьт) с элементами однократной точности и вектор (xo,Xi,... ,х-т) с элементами многократной точности, заданными в интервале О < Хк < N.

F1. [Начальная установка.] Присвоить Ы <--1 для О < i < т; затем присвоить j <- 0.

F2. [Очередное решение.] Из алгоритма Е взять очередное решение (х, ео, ei,..., em). (Алгоритмы Е и F удобно рассматривать как сопрограммы.) Присвоить к <- т.

F3. [Найти нечетное число.] Если к <0, перейти к шагу F5. В противном случае, если Cfc четно, присвоить к - к - 1 и повторить этот шаг.

F4. [Векторы линейно зависимы?] Если bk > О, присвоить i <- 5*,, х <- (х;х) mod N, вг вг + Егг ДЛЯ О < Г < т; присвоить к < к - 1 и возвратиться к шагу F3. В противном случае присвоить bk <- j, Xj <- х, Ejr <- вг для О г < ш; присвоить j i- j + 1 и возвратиться к шагу F2. (В последнем случае получаем новое линейно независимое решение по модулю 2, первым нечетным компонентом

которого является Ck- Значения Ejr могут и не быть значениями однократной точности, но они, скорее всего, будут оставаться малыми при уменьшении fe от m до 1 согласно предположениям Моррисона (Morrison) и Бриллхарта (Brillliart).)

F5. [Попытаться выполнить разложение.] (Теперь ео, ei, ..., em четные.) Присвоить

Если X = у или х + у = N, возвратиться к шагу F2. В противном случае вычислить gcd(a; - у, N), который является собственным делителем числа N, и завершить выполнение алгоритма.

Этот алгоритм находит простые множители, когда есть возможность найти множитель из тайного набора результатов гшгоритма Е. [Доказательство. Пусть результатами выпол-чения алгоритма Е будут (Л,, J.o,..., Eim) при 1 < г < t, и положим, что удалось найти разложение на простые множители числа N = N1N2, когда выполняются соотношения ж = Л7... А7 из/ = (-1)°/р!--Рт" (по модулю N), гдее> = aiEij + - +atEtj четно для всех j. Тогда х = ±у (по модулю Ni) и х = Цу (по модулю N2). Нетрудно увидеть, что это решение можно преобразовать в пару {х,у), которая появляется при выполнении шага F5, путем выполнения ряда операций, на которых пары {х,у) последовательно 1аменяются парами {хх,уу), где х = ±у (по модулю N).]

13. Имеется 2"* значений величины х, имеющих одинаковые показатели степени (ео,...,ет), поскольку, если N = .. q"", знак величины х по модулю q{ можно выбирать произвольно. Множители отсутствуют точно для двух из этих 2 значений.

14. Поскольку Р = kNQ (по модулю р) для любого простого делителя р числа V, получим 1 = р2(р-1)/2 = (лгд2)(р-1)/2 = (лг)Ср-1)/2 модулю р) при Р 0.

15. Un = (а" -Ь")/ч/, где а = {Р + VD), b = {Р- VD), D = P-4Q.Тогда 2"-[/„ = Eki2k+i)P"~~I°i поэтому Up = £)(p-i)/2 (no модулю p), если p - нечетное простое число. Аналогично, если К, = а" + Ь" = Un+i - QUn-u то 2"-К = (2"*)"""° " Vp = Р" = Р. Таким образом, если Up = -1, получаем, что Up+i modp = 0. Если Up = 1, то (QUp-i) modp = 0. Здесь, если Q кратно р, то Un = Р"~ (по модулю р) для п > О, поэтому Un никогда не будет кратно р; если Q не кратно р, то Up-i modp = 0. Поэтому, как и в теореме L, Ut mod N = О, если N = р... р, N 1 Q и t = lcmi<j<r(p~ (pj +ej)). При предположениях из этого упражнения ранг появления числа N равен N + 1; значит, N взаимно просто с Q, а t кратно N + 1. Кроме того, из предположений этого упражнения следует, что каждое Pj является нечетным и каждое ej равно ±1, поэтому t < 2~Ylpy~\pj + ipj) = 2{1УМ; следовательно, г = 1 и t = р + eipf - Поэтому ei = 1 и ei = 1.

Замечание. Для того чтобы "выполняемая проверка оказалась эффективной, следует подбирать Р и Q таким образом, чтобы проверка выполнялась с некоторой вероятностью. Лемер (Lehmer) предложил выбрать Р = 1, чтобы D = 1 - 4Q, а Q выбрать таким образом, чтобы N ± QD. (Если последнее условие не соблюдается, значит, число N не простое, если только выполняется условие \QD\ < N.) Далее, из приведенного выше рассуждения видно, что желательно иметь ei = 1, т. е. £)(-i)/2 = i (по модулю N). Это еще одно условие, налагаемое на выбор Q. Если D удовлетворяет этому условию и если Un+i mod N О, то известно, что N - не простое.

Пример. Если Р = 1 и Q = -1, то получаем последовательность Фибоначчи и D = 5. Поскольку 5 = -1 (по модулю 23), можно было бы попытаться доказать, что 23 - простое число, используя последовательность Фибоначчи:

{Еп mod 23) = 0,1,1,2,3,5,8,13,21,11,9,20,6,3,9,12,21,10,8,18,3,21,1,22,0.....

Поэтому 24 есть ранг появления 23, и проверка сработала. Однако при помощи последовательности Фибоначчи не удается установить подобным образом тот факт, что числа 13 и 17 - простые, так как Fr mod 13 = О и Fg mod 17 = 0. Если р = ±1 (по модулю 10), то 5Ср-1)/2 juodp = 1 и, следовательно, Fp i (но не Fp+i) делится на р.

17. Пусть f{q) = 21gq - 1. Если q = 2 или 3, то дерево содержит не более f{q) узлов. Для простого числа q > 3 положим q = 1 + qi... qt, где t > 2, а qi, ..., qt -простые числа. Размер дерева < 1 4-/(9*) = 2 + fiq-l)-t< fiq). [SICOMP 7 (1975), 214-220.]

18. Величина x(G{a) - F{a)) равна количеству таких п < х, для которых второй по величине простой множитель не превышает х", а наибольший по величине простой множитель > х". Следовательно,

xG{t)dt = Ых+*) - п{х)) x-iGit/il - t)) - F(t/(1 - t))).

Вероятность того, что pt-i < y/pt, равна /jF(t/2(l - t))t~ dt. [Кстати, можно показать, что она равна F(t/(1 - t)) dt, т. е. среднему значению величины \ogpt/k>gx; она равна и константе Дикмана-Голомба (Dickman-Golomb) .62433, приведенной в упр. 1.3.3-23 и 3.1-13. Можно показать также, что производная G"{0) равна

F(t/(1 - t))t-dt = F(l) + 2F(i) + 3F(i) + ... = еГ

Для третьего по величине простого множителя Я(а) = J°{H{t/{l-t)) - G{t/{l - t)))t~ dt, а Я"(0) = 00. См. Р. Billingsley, Period. Math. Hungar. 2 (1972), 283-289; J. Galambos, Acta Arith. 31 (1976), 213-218; D. E. Knuth, L. Trabb Pardo, Theoretical Сотр. Sci. 3 (1976), 321-348; J. L. Hafner, K. S. McCurley, J. Algorithms 10 (1989), 531-556.]

19. Число M = 2 - 1 кратно всем числам p, для которых порядок 2 по модулю р делит число D. Разовьем эту идею, положив ai = 2 и aj+i = mod TV, где qj = p, Pj есть j-e простое число и Cj = [log lOOO/logpjJ. Пусть A = aieg. Вычислим теперь 5, = gcd(A - 1, N) для всех простых чисел q, расположенных между 10 и 10*. Это можно сделать, если начать вычисления с числа mod N, а затем умножить его на А* mod N или А modW. (Похожий метод в 1920 году применил Д. Н. Лемер (D. N. Lehmer), но он не опубликовал результатов.) Так же, как и в алгоритме В, можно путем группирования исключить из рассмотрения почти все наибольшие общие делители; например, поскольку Ьзог-к = gcd(A"" - А*, N), можно использовать группы из 8, вычисляя сначала Сг = (зог 29)(зог 23) (зог ) j дг затем - gcd(cr, N) для 33 < г < 3334.

20. См. Н. С. Williams, Math. Сотр. 39 (1982), 225-234.

21. Интересная теория, имеющая отношение к условиям этой задачи, была предложена Эриком Бахом (Eric Bach), Information and Computation 90 (1991), 139-155.

22. Алгоритм P не достигает цели только тогда, когда для случайного числа х не подтверждается тот факт, что число п не простое. Будем называть число х плохим, если ж modn = 1 или одно из чисел хч удовлетворяет условию = - 1 (по модулю п) для О < j < fc. Поскольку число 1 плохое, получаем р„ = (Ь„ - 1)/(п - 2) < Ь„/{п - 1), где Ь„ -количество плохих чисел х,, таких, что I < Xi < п, если число п не является простым.

Каждое плохое число х удовлетворяет условию х"" =1 (по модулю п). Если число р простое, число решений уравнения х = 1 (по модулю р) для 1 < х < р" равно числу решений уравнения qy = О (по модулю р°-(р - 1)) для О < у < р~{р - 1), т. е. gcd(q, p~{j> - 1)), поскольку можно заменить число х числом а", где а - простой корень.

Пусть п = п\...п/, где все щ - различные простые числа. Согласно китайской теореме об остатках число решений уравнения х"" =1 (по модулю п) равно

Ш=, gcd(n-l,n->(n<-l)).