касающиеся тонкостей применения теоремы D, приведены Шнорром в J. Algorithms 3 (1982), 101-127.]

31. Чтобы показать, что Рт{Х < 2т) < e""*, присвоим п = М, рМ = 4т и еМ = 2т.

32. Пусть М = LvNJ и пусть все Xi каждого из сообщений ограничены интервалом О < X < - М. Если X > М, кодируем его в виде х modiV, как и ранее, но при X < М изменяем кодирование на (х+уМ) mod N, где у - случайное число, принадлежащее интервалу - М < у < М. При декодировании сначала вычисляем кубический корень и, если в результате получаем значение - или большее, берем остаток mod М.

34. Пусть Р - вероятность того, что выполняется равенство х" modp = 1; пусть также Q - вероятность того, что вьшолняется равенство х"* modg = 1. Вероятность того, что gcd(x" -\, N) =р или q, равна Р(1 - <?) -Ь <?(! - Р) = Р -Ь <? - 2PQ. Если Р < i или <3 < 2 Данная вероятность > 2(10- - 10-), поэтому есть хорошие шансы найти простой множитель после выполнения примерно 10* logm арифметических операций по модулю N. С другой стороны, если Р> тл Q > j, toP«Q«1, поскольку есть основдая формула Р = gcd(m, р - 1)/р; поэтому в подобном случае m крртно 1сш(р - 1, q - 1). Положим, что т = 2* г, где г нечетно, и построим последовательность х mod N, х mod N, ..., х mod N; так же, как и в результате выполнения алгоритма Р, получаем, что впервые 1 появится после значения у, не равного N - 1, с вероятностью, не меньшей j; следовательно, gcd(y- 1, N) =р или q.

35. Пусть / = (р- - q") modiV. Поскольку pmod4 = qmod4 = 3, то () = () = () = -() = -1 и, кроме того, () = -() = -1. Пусть для данного сообщения х в интервале 0<х< {N - Ь) имеем х = 4х -Ь 2 или 8х -Ь 4, любое из которых удовлетворяет условию () = 1. Тогда передаем сообщение х modTV.

Чтобы закодировать это сообщение, сначала используем SQRT-блок для нахождения единственного числа у, такого, чтобы выполнялись условия у = х mod N и () = 1 и у было четным. Тогда имеем у = х, поскольку три остальных квадратных корня из числа х равны N - х и (±/х) mod N; первый из этих корней нечетный, два других имеют отрицательные символы Якоби. Декодирование на этом завершается присвоением X <- [у/А\, если у mod4 = 2, и х <- [у/8\ -в противном случае.

Каждый, кто сможет декодировать такое закодированное сообщение, сможет найти множители числа N, поскольку декодирование ложного сообщения х mod N в случае, когда () = -1, позволяет обнаружить (±/) modNn ((±/) mod N)-l имеет нетривиальный наибольший общий делитель с числом N. [Си. IEEE Transactions IT-26 (1980), 726-729.]

36. Согласно выражению (4) m-e простое число равно

m Inm -Ь min Inm - m -Ь m In In m/ln m - 2m/lnm -I- 0(m(loglogm)(logm)-),

хотя для решения поставленной задачи достаточно более слабой оценки Рт = т\пт + 0(т log logm). (Полагаем, что Рт является т-м простым числом, учитывая предположе-ние, что значения Vi распределены равномерно.) Если выбрать Inm = cVlnNlninN, где с = 0(1), получим

г = c- v/ln N/\n\nN - с - с~{\п In In N/\n In N) - 2c-(ln с)/1п \nN + 0{V\R\nN/ln N).

Оценка (22) времени выполнения алгоритма Е несколько неожиданно упрощается:

ехр(/(с, N)V\nN\n\nN + 0(log log N)),

где функция /(с, iV) = с -Ь (l - (1 -Ь In 2)/lnlnN)c-. Значение числа с, минимизирующего функцию f{c,N), равно л/1 - (1 -Ь In 2)/. Таким образом, получаем оценку

ехр(2л/ Ь N In In Nv/l - (1 -Ь In 2)/ln In N + 0{\og log N)).

Для N = 10° эта оценка дает e{N) w .33, что по-прежнему существенно превыщает результаты наблюдений за поведением процесса.

Замечание. Поведение частичных отнощений числа \/D подчиняется распределению, полученному в разделе 4.5.3 для случайных вещественных чисел. Например, первый миллион частичных отнощений для числа Ю*-1-314159 содержит точно (415 236,169 719, 93 180, 58606) случаев, когда An соответствует (1, 2, 3,4). Более того, в соответствии с результатом упр. 4,5.3-12(с) и уравнением 4.5.3-(12) имеем Vn+i = \р1 - Dql \ = 2VDqn\pn - VDqn \ + 0{qn). Поэтому следует ожидать, что поведение величины Vnjs/D будет, по существу, аналогично поведению величины вп{х) - qn\Pn - xqn\, где х - случайное вещественное число. Для случайной переменной вп известна приближенная плотность распределения min(l,6~-l)/ln2 для О < б < 1, равномерная при б < 1/2 [см. Bosma, Jager, Wiedijk, Indag. Math. 45 (1983), 281-299]. Таким образом, при обнаружении неприемлемой эффективности алгоритма Е необходимо, кроме размера величин V„, принимать во внимание какие-то дополнительные условия.

37. Примените к числу y/D+R результат упр. 4.5.3-12, чтобы увидеть, начинается ли сразу же периодическая часть дроби, и затем проверьте свойство палиндромности, вычисляя период в обратном порядке. [Отсюда следует, что вторая часть периода дает те же значения V, что и первая, и выполнение алгоритма Е может прекратиться раньще, при выполнении щага Е5, когда U = U или V = V. Однако в общем случае этот период настолько длинен, что не удается добраться до его половины; поэтому для дополнительного усложнения алгоритма оснований нет.]

38. Пусть г = (Ю" - 1)/9. Тогда Ро = 10 -f 9; Pi = г -Ь 3 • 10" Рг = 2г -Ь 3 • Ю" + 7; Рз = Зг -Ь 2 • 10; Р4 = 4г -Ь 2 • 10 - 3; Р5 = 5г -Ь 3 • 10" -Ь 4; Ре = 6г -Ь 2 Ю"* + 3; Рг = 7г -I- 2 • 10 (прекрасно!); Pg = 8г -Ь 10* - 7; Рд = 9г - 8000.

39. Заметим, что в случае, когда число q-1 имеет 2 и р в качестве простых множителей, легко доказать, что q есть простое число. Преемниками числа 2 являются числа Ферма, а одной из наиболее известных нерещенных задач теории чисел для этого случая является существование или отсутствие шестого простого числа Ферма. Поэтому мы, возможно, никогда не узнаем, как определить, имеет ли произвольное целое число каких-либо преемников. Тем не менее в некоторых случаях это возможно; напри.мер, в 1962 году Джон Селфридж (John Selfridge) доказал, что числа 78 557 и 271 129 таких преемников не имеют [см. амм 70 (1963), 101-102]. Позже В. Серпиньский (W. Sierpinski) доказал существование бесконечного количества нечетных чисел без преемников [Elemente der Math. 15 (1960), 73-74]. Возможно, число 78557 является самым маленьким из них, хотя в настоящее время уже известно 69 претендентов на эту роль благодаря исследованиям, выполненным в 1983 году Г. Йешке (G. Jaeschke) и У. Келлером (W. Keller) [Math. Сотр. 40 (1983), 381-384, 661-673; 45 (1985), 637].

Сведения о более традиц110нной форме цепочек простых чисел (форме Каннингэма (Cunningham)), в которых переходами являются р 2р ± 1, приведены в статье Гюнтера Лоха (Giinter Loh) Math. Сотр. 53 (1989), 751-759. В частности, он нашел, что число 554 688 278 430 • 2* - 1 является простым при О < fe < 12.

40. [Jnf Ргос. Letters 8 (1979), 28-31.] Заметим, что в таком абстрактном автомате а; mod у = X - у [х/у\ может быть легко вычислено, в результате чего получим просто константы вида О = а; - ж, 1 = [х/х], 2 = 1-1-1. Убедиться в выполнении условия а; > О можно, проверив, будет ли а; = 1 или [а;/(а; - 1)J ф 0.

(а) Сначала за 0(log п) шагов вычислим I = [Ig nJ путем повторного деления на 2; одновременно вычислим fe = 2 и А = 2+ за 0(log п) циклов путем повторного присвоения fe <- 2fe, а <- а. Прежде чем выполнять основные вычисления, предположим, что известны значения t = А"", и = (A-t-l)"" иг; = т!. Теперь можно выполнить присвоения

т <- m + 1, t <- At, и <- (А + 1)и, v <- vm, увеличив таким образом значение т на 1; кроме того, можно удвоить значение т путем присвоения т <- 2т, и +- , v +- {[u/t] mod A)v, t +- t, учитывая, что число A является достаточно большим. (Подумайте над вариантом, когда число и представлено в системе счисления по основанию А; при этом А должно быть больше, чем {)-) Далее, если п = (а;... ао)2, положим uj = (щ... aj)2; если т = uj и к = 2 при j > О, то можно уменьшить j на 1, присвоив к <- [fe/2J, т <- 2m+([n/feJ mod 2). Следовательно, можно вычислить число пу! для j = Z - 1, ..., О за O(logn) циклов. [Джулия Робинсон (Julia Robinson) предложила другое решение, а именно: вычислять = L57(f)J тогда, когда В > (2п)"+ (см. AJVfM 80 (1973), 250-251, 266),] (b) Сначала, как и в (а), вычисляем А = 2 , .затем находим наименьшее fe > О, такое, что 2*4 modn = 0. Если gcd(n, 2*!) ф 1, полагаем /(п) равным этому значению; обратите внимание, что этот наибольший общий делитель может быть вычислен при помощи алгоритма Евклида за O(logn) циклов. Если gcd(n,2*!) = 1, можно найти наименьшее целое число т, такое, что (J2j) modn = О, и положить /(.п) = gcd(m,n). (Учтите, что в этом случае 2* < m < 2*+; следовательно, Гт/2] < 2* и [т/2]! взаимно просто с числом п, поэтому (2j) nod n = О тогда и только тогда, когда т\ mod п = 0. В дальнейшем п ф 4.)

При ограниченном количестве регистров для вычисления т можно использовать числа Фибоначчи (см. алгоритм 6.2.IF). Предположим, известно, что s = Fj, s - Fj..i t = A, t = A>+, u = (A + 1)>, и = (A + V = A, w = {A + If"", (;;) modn # 0 и

(m+a") d n = 0. Этого можно легко достичь при т = Py+i для достаточно больших j за O(logn) циклов; более того, А будет больше, чем 2"+*, Если 5 = 1, присваиваем /(п) = gcd(2m+ 1, п) или gcd(2m + 2, п), выбирая то из них, которое ф 1, Выполнение алгоритма на этом завершается. В противном случае уменьшаем j на 1 следующим образом: сначала присваиваем г <- s, s <- s - s, s <- г, г <- t, t <- {t/t\, t - r, r <r- u, и - \u/u\, u <- r, затем, если {\ wu/vt\ mod A) mod n 51 0, присваиваем m <- m + s, w <- wu, v <- vt.

[Можно ли решить эту задачу за менее чем 0(log п) операций? Можно ли вычислить наименьший или наибольший простой множитель числа п за 0(log п) операций?]

41. (а) Очевидно, что {х) = я-(т) + fi{x,m) = п(т) + f{x,m) - fo{x,m) - /2(1,m) -/з{х,т) - ... при 1 < m < ж. Присвоим х = N, т = N и учтем, что fk{N,N) = О при fe > 2.

(b) Получаем f2{N,N) = Ем<р<,[РЯ <N] = Zn<p<nMN/p) - (р) + l) =

Y,n<p<n3/ (Vp) ~ {""2) + {"2) где p и q определены на множестве простых чисел. Следовательно, /2(1 ООО, 10) = ж{) + ж{Щ) + ж{Щ) + ж() + ж() + ,г() +

iW) - ("2") + ("2°) = 24 + 21 + 16 + 15 + 14 + 11 + 11 - 55 + 6 = 63.

(c) Приведенное в указании тождество просто означает, что pj-долгожитель есть Pj-i-долгожитель, который не кратен pj. Очевидно, что f{N,N) = f{N,Pn(n))-Применяем это тождество до тех пор, пока не получим значения f(x,pj), где либо j - О, либо X < N. Найдем результат:

f{N\N) = Y ()/{ VO " Е Е М)/(,Р>-1)[-р.-ДОлгожитель].

fc=l J = l n/pj<k<n

Далее, f{x, 1) = [х], поэтому первая сумма равна 1 ООО - 500 - 333 - 200 + 166 - 142 = -9 (при N = 10), Вторая сумма такова: -f{,l) - /(,1) - /(,2) - /(if2,2) -/(iP,3) = -100 - 71 - 33 - 24 - 9 = -237, Отсюда /(1000,10) = -9 + 237 = 228 и я-(1 ООО) = 4 + 228 - 1 - 63 = 168,

(d) Если N < 2"*, можно сформировать массив, в котором элементы a2"-i+n = [п + 1 есть Pj-долгожитель] для 1 < п < N представляют решето после j проходов, а а„ =