а2п + а2п+\ для 1 < п < 2"". Затем, если х < легко вычислить функцию f{x,pj) за 0{т) шагов и удалить из решета числа, кратные р, за 0(Nm/p) шагов. Общее время вычисления функции f{N,N) будет равно 0{Nlog NloglogN), так как E]iy-l/pj = O(loglogN).

Требования к объему памяти могут быть снижены от значения 2Nm до 2Nm, если разбить решето на N фрагментов размером N каждое и работать с каждым из них отдельно. Могут пригодиться вспомогательные таблицы значений pj для 1 < j < n{N) и р{к), а также наименьших простых множителей чисел к, 1 < к < N, которые можно просто сформировать перед выполнением основных вычислений.

[См. Math. Сотр. 44 (1985), 537-560. Впервые подобный метод был предложен Д. Ф. Э. Мейселем (D. F. Е. Meissel, Math. AnnaJen 2 (1870), 636-642; 3 (1871), 523-525; 21 (1883), 304; 25 (1885), 251-257. Д. Г. Лемер (D. Н. Lehmer) опубликовал в журнале Illinois j. Math. 3 (1959), 381-388, ряд уточнений этого метода. Но ни Мейсель, ни Лемер не нашли правила, по которому рекуррентная процедура останавливалась бы с той же эффективностью, что в описанном выше методе. Кроме того, Лагариас (Lagarias) и Одлыжко (Odlyzko), используя принципы аналитической теории чисел, разработали совершенно иное приближение, посредством которого величина tt(N) может быть вычислена за 0(iV+) шагов (см. J. Algorithms 8 (1987), 173-191). При помощи уточненного метода, выполняющего вычисления за 0{N ) шагов, Делеглиз (Deleglise) и Рива (Rivat) [Math. Сотр. 65 (1996), 235-245] установили мировой рекорд вычисления простых чисел; я-(10") = 2 220 819 602 560 918 840.]

42. L1. [Начальная установка.] Найти г, такое, что гг = 1 (по модулю s); затем присвоить г <- nfmod,s, и <- rfmods, i; <- s, w <- (п - rr)f/smods, в [yiV/sJ, (и1,из) <- (l,u), ivi,V3) <- (0,1»). (Задача заключается в поиске всех пар целых чисел (Л, р), таких, что (As + r){ps + r) = N; отсюда следует, что Хи + р = xv (по модулю s) и л/Xpv < в. Алгоритм 4.5.2Х будет выполняться без учета величин t2,U2,v2; отношения

Xt3+ pti =wti, Хиз + рщ = wui, Xv3 + pvi = wvi (no модулю s)

остаются инвариантными.)

L2. [Попытка для делителей.] Если vi = О, то вывести значение As + г во всех случаях, когда As -- г делит N и О < А < в/s. Если vs = О, вывести значение N/(ps + г) во Bcejf случаях, когда ps+r делит N иО < р < в/s. В остальных случаях для всех к, таких, что \wvi + ks\ < в, если vi < О, или О < wvi + ks < 2в, если di > О, и для а = -1-1 и -1 вывести значение As-1-г, если d = (wvis + ks + vsr + vir) - AvivsN - точный квадрат и если числа

д wvis + ks - Узг + vir + a\fd wvis -f ks Л- vr - v\r - a\fd 2v3S ~ 2s

являются положительными целыми числами. (Решения для Аз -- pvi = wvi + ks, (As + r)(ps -i-r) = N существуют.)

L3. [Выполнено?] Если vs = О, то выполнение алгоритма завершается.

L4. [Разделить и вычесть.] Присвоить q <- [из/«з]. Если из = и vi < О, то уменьшить q на 1. Затем присвоить

(<1,<з) <-(И1,из) - ("1,«з)9, (и1,из) <-("1,из), ("1,из) <-(<1,<з) и возвратиться к шагу L2.

[См. Math. Сотр. 42 (1984), 331-340. Оценки для шага L2 можно уточнить, например, для того, чтобы обеспечить rf > 0. Некоторые множители могут выводиться более одного раза.]

43. (а) Прежде всего убедимся в том, что символ Якоби () равен +1. (Если он равен О, задача упрощается; если он равен -1, то у Qm-) Затем выберем случайные целые числа Xl, Хп В интервале [0..т) и положим Xj = [G{yXj modm) = (j/xy mod m) mod 2]. Если у e Qm, TO E Aj > I + e; в противном случае m - у e Qm и E Aj < - e. Сообщить, что у e Qm, если Al • • • + Xn> n. В силу результата упр. 1.2.10-21 вероятность неудачи не превышает величины е"" Поэтому выбираем п = \е~ InSl.

(b) Находим X с символом Якоби () = -1 и присваиваем у <- х mod т. В этом случае множителями числа m будут gcd(x + т) и gcd(x - /у, т), так что задача теперь состоит в том, чтобы найти ±/у для заданного у 6 Qm- Если найти rv для любого ненулевого значения v, то поставленная задача будет решена, поскольку ,/у = {vtv) modm, если gcd(i;, т) не является множителем числа т.

Предположим, что для некоторого е > 1 вьшолняется равенство б = 2~. Выберем в интервале [О.. т) случайные целые числа а и t> и предположим, что известны двоичные функции ао и /Зо, такие, что выполняются неравенства

Здесь ао -нечетное число, кратное б/64, а /Зо - нечетное число, кратное 6/64. Положим также, что известны Ха и ХЬ. Конечно, на самом деле нам не известны значения ао, /Зо, Ха и ХЬ, но мы попробуем применить все возможные значения 32б~ х 32- х 2 х 2. Ложные ответвления программы, которые оперируют некорректными предположениями, не нанесут вреда.

Определим числа в виде = 2~{a + (j+)b) modm и vtj = 2~*~ (a+jb) modm. Оба эти числа utj и vtj равномерно распределены в интервале [О .. т), так как числа а и 6 были выбраны случайными. Далее, для фиксированного t числа utj при jo < j < jo + l являются попарно независимыми, то же самое относится к числам vtj при jo < j < jo +1 до тех пор, пока значение I не достигнет наименьшего простого множителя числа т. Числа utj и vtj можно использовать только для неравенства -2ге~ < j < 2гб. Если для любого из этих чисел имеется множитель, общий с множителем для т, то задача решена.

Для всех V ±т определим xv = +1, если v 6 Qm, X" - -1, если -v 6 Qm, и х = О, если () = -1. Заметим, что Х"((+2)у = Xtj, поскольку = {2U(t+2)j) modm. Поэтому можно определить xltj и xutj для всех t и j при помощи алгоритма А, примененного к Utj и Vtj для о < t < 1 и -2гб- < j < 2ге~. Установка 5 = jer в этом алгоритме гарантирует, что все значения величины х верны с вероятностью > 1 - .

Выполнение алгоритма осуществляется не более чем за г этапов. В начале этапа t для О < t < г полагаем, что известны значения величин Х2~а, Х2~% и дробей at, /3t, такие, что

--at

г2-б

-I3t

2<+в

Определим a(+i = {at + Л2 а) и /3t+i = jC/? + -2 Ь); это обеспечивает выполнение неравенств. На следающем шаге находим Л2--Ь, которое удовлетворяет отношению

Xutj + Х2*а + jX2~b + Х2--Ь +

г2-а + jr2-b + r2-

= О (по модулю 2).

Пусть n = 4min(r,2)e ; тогда, если \j\ < j, получаем

г2-а .г2~б г2"~б , -а а ч -+J-+--(at+jfit+fit+i)

Поэтому, если xtj = 1, вероятно, что Л2"*~б = Gj, где Gj = {G{ujjy modm) + Л2~*а + jA2~b+ [atjft +/9(+iJ) mod 2. Более точно, получим

L(r2-a + jr2-b4-r2--6)/mJ = [at + Jl3t + 0t+i\,

если только не выполняются неравенства TUtj < jm и TUtj > (l - fg)m. Пусть Yj - (2Gj - l)xM(j. Если Yj = +1, это довод в пользу Л2"~6 = 1; если Yj = -1, то в пользу Л2~~Ь = О, если Yj = О, то никаких действий не предпринимаем. Будем демократичны и установим Л2--Ь = [E;=1"„/2>j > О].

Какова вероятность того, что Л2~*~б - корректное значение? Пусть Zj = -1, если XUtj Ф О и (rutj < jgm или TUtj > (l - Je)m, или G{ujy modm) ф Xutj). В противном случае полагаем, что Zj - \хщ\- Поскольку Zj-функция Utj, случайные переменные Zj попарно независимы и одинаково распределены. Пусть Z = Е"=1/2 -J если Z > О, значение Л2~~б будет верным. Вероятность того, что Zj = О, равна , а вероятность того, что Zj = +1, равна > + f - ; поэтому ЕZj > е. Очевидно, что var{Zj) < . Таким образом, возможность появления ошибки в ветви программы, основанной на правильных предпосылках, согласно неравенству Чебышева не превышает величины

Pr(Z< 0) < PT{{Z~nEZj) > пе) < п-е = min(r,2)-

(см. упр. 3.5-42).

Аналогичный метод может быть использован для определения величины Л2~~а с погрешностью < min(r, 2)", если заменить величину Utj величиной Vtj. Возможно, окажется, что 6/2*+ < 1/(2т), так что число г2~*6 будет ближайшим целым к mfft-В этом случае можно вычислить значение = (2б~г2"б) modm. Выполнив возведение этого числа в квадрат, можно узнать, были ли мы правы.

Суммарный шанс допустить пцтибку ограничен величиной Eoi 2"* = на стадии t < Ign, а на последующих стадиях - величиной Е«<г~ ~ э- Таким образом, общая вероятность возникновения ошибки, включая возможность того, что не все значения величины X были определены верно, не превышает + + = Выполнение

программы завершится успешным вычислением значения л/у не менее чем в случаев; следовательно, множители числа т будут получены после повторения процесса в среднем не более десяти раз.

В общем времени выполнения программы доминирует величина 0(r6"log(re~)T(G)), соответствующая времени вычисления Х- К ней следует добавить 0(re~T(G))-время, затрачиваемое на последующие прогнозы, и 0{ге~)-время на вычисление значений at, fit, Х2~а и Л2~6 во всех ответвлениях программы.

Эта процедура, которая ясно иллюстрирует основные парадоксы вероятностных алгоритмов, разработана Р. Фишлином (R. Fischlin) и К.-П. Шнорром (С.-Р. Schnorr) [Lecture JVotes in Сотр. Sci. 1233 (1997), 267-279] на базе бо.нее ранних исследований, выполненных Алекси (Alexi), Чором (Chor), Голдрихом (Goldreich) и Шнорром [SICOMP 17 (1988), 194-209], а также Бен-Ором (Веп-Ог), Чором и Шамиром (Shamir) [STOC 15 (1983), 421-430]. Если объединить эту процедуру с леммой 3.5Р4, получится теорема, аналогичная теореме 3.5Р, в которой последовательность 3.2.2-(17) заменяется последовательностью 3.2.2-(16). Фишлин и Шнорр показали, как упорядо-