времени. Если частными во время выполнения алгоритма являются Ai, А2, Am, то Al Аг ... Am < и, так что log Ai + • • + log Am < log и. В силу теоремы L имеем также т - O(logu).

46. Да, эта граница может быть уменьшена до величины 0(n(log n)(loglogn)), даже если придется вычислять последовательность частичных отношений, которые можно вычислить по алгоритму Евклида. (См. А. Schonhage, Acta Jnformatica 1 (1971), 139-144.) Более того, алгоритм Шёнхаге (Schonhage) является асимптотически оптимальным по отношению к выполняемым им операциям умножения и деления [V. Strassen, SICOMP 12 (1983), 1-27]. При не очень больших п на практике лучше применять алгоритм 4.5.2L, однако в книге А. Schonhage, А. F. W. Grotefeld, and Е. Vetter Fast Algorithms (Heidelberg: Spektrum Akademischer Verlag, 1994), §7.2, приводятся идеи эффективного использования алгоритма для чисел длиной до 1 800 бит.

48. Tj = {Kj-2(-a2,...,-aj-i), Kj-i(-ai,...,-Oj-i), Kn-j(aj+i,... ,an)d)

= {(-iyKj-2{a2,... ,aj-i), (-l)-A:, i(ai,... ,a, i), Kn-j(aj+u. .,an)d).

49. Поскольку Xxi + fizi = fiv и Xxn+i + fiZn+i = -Xv/d, существует такое нечетное значение j, что Xxj + pzj > О и Xxj+2 + liZj+2 < 0. Если Xxj + fizj > в и Xxj+2 + fiZj+2 < -в, то выполняется р > в/zj и А > -e/xj+2- Отсюда следует, что О < Axj+i + fizj+i < XfiXj+iZj/в - XfiZj+iXj+2/в < 2Xfiv/e = 29, так как для всех к выполняется a;fc+i2fc = Kk~i{a2,... ,ак)Кп-к(ак+1, . ,ап) < Kn-i{a2, .. ,ап) = v/d. [Н. W. Lenstra, Jr., JVfath. Сотр. 42 (1984), 331-340.]

50. Положим к = Г/З/а]. Если ка < 7, то результат равен к; в противном случае результат равен

к-1+ [•/((!/") modl,fc-7/a,fc-/3/a)-а

51. Если ах - mz = у и X 1. у, то имеем х ± mz. Рассмотрим дерево Стерна-Брокота из упр. 40 с заданным дополнительным узлом с меткой 0/1. Объединим помеченное значение у = ах - mz с каждым узлом с меткой z/x. Требуется найти все узлы z/x, для которых у по абсолютной величине не превышает и для которых знаменатель х тоже < в. Единственный возможный путь к таким узлам поддерживает положительный маркер влево и отрицательный - вправо. Это правило определяет единственный путь, который поворачивает вправо, когда маркер положительный, влево - когда маркер отрицательный, и останавливается, когда маркер становится равным нулю. Этот путь неявно поддерживается при выполнении алгоритма 4.5.2Х, когда и = mnv = а, исключая случай, когда алгоритм "прыгает" вперед-он просматривает узлы только перед тем, как маркер меняет знак (родители узлов "точки превращения", как в упр. 43).

Пусть z/x - первый узел пути, маркер которого у удовлетворяет условию \у\ < в. Если X > в, то решения нет, так как соответствующие значения на пути имеют даже ббльшие знаменатели. В противном случае (±а;, у) является решением, полученным при х 1. у.

Легко видеть, что если у = О, то решения не существует, и что если у ф О, то знак маркера на следующем узле пути не будет совпадать со знаком у. Поэтому узел z/x будет обработан алгоритмом 4.5.2Х и для некоторого j будет выполняться х = Xj = Aj-i(ai,...,aj-i), у = yj = (-l)(-->A„ j(a ;+i,...,a„)d, z = Zj = А г(аг,... ,aj i) (см. упр. 48). Следующим подходящим для решения узлом будет узел с меткой z /х = (zj-i + kzj)/{xj-i + kxj) с маркером у - yj-\ -Ь kyj, где к настолько мало, что \у\ < В; отсюда у у < 0. Однако теперь нужно увеличить в, иначе будем иметь т - Kn{ai,..., an)d = х\у\ + х\у\ < в + в = т и неравенство не будет удовлетворяться.

Эти рассуждения доказывают, что задача может быть эффективно решена путем применения алгоритма 4.5.2Х для случая, когда и = m и v = а, но при следующей замене операции шага Х2: "Если va < \fm/2, то выполнение алгоритма завершается. Пара (х, у) =

(«2, V3 sign(v2)) является, следовательно, единственным решением, обеспечивающим х ±у их < \/т/2; в противном случае решения нет". [Р. S. Wang, Lecture Notes in Сотр. Sci. 162 (1983), 225-235; P Kornerup, R. T. Gregory, BIT 23 (1983), 9-20.]

Подобный метод будет работать, если потребовать, чтобы О < а; < 6i и у < 82, когда 2612 < т.

РАЗДЕЛ 4.5.4

1. Если dk - не простое число, то его простые множители выделяются перед использованием пробного делителя dk.

2. Нет; при такой модификации в случае, когда pt-i = pt, алгоритм сделает ошибку, выдав в качестве простого множителя единицу.

3. Можно взять Р равным произведению первых 108 простых чисел. [Замечание. Для того чтобы только проверить, является ли число п простым, наименьший общий делитель для 416-разрядного числа Р = 19 590... 5 910 может быть вычислен значительно быстрее, чем потребуется для выполнения 168 операций деления.]

4. В обозначениях упр. 3.1-11 имеем

Е 2--"+ р(м, Л)=1 х: /С) п (i - ).

\ />1 *=1

где /(О = Ei<A<( 2Г«"*=(+1-1. Если I = 2*+* при О < в < 1, то

/(0=/(3-2--2-2-"),

где функция 3 2"* - 2 2-* достигает максимума в точке в = lg(4/3) и и.меет минимум, равный 1, при б = О и 1. Поэтому среднее значение величины 2"*+- находится между средними значениями величин р+ X, умноженными на постоянную в интервале от 1.0 до 1.125, откуда и следует результат.

Замечание. Ричард Брент (Richard Brent) заметил, что при m -> оо плотность

ni=i(l - к/т) = exp(-Z(Z - 1)/2ш + ОЦ/т))

стремится к нормальному распределению, поэтому можно положить, что значения в распределены равномерно. Тогда функция 3-2-* - 2-2-* имеет среднее значение 3/(4 In2), а среднее число итераций, необходимых для выполнения алгоритма В, стремится к зна чению (3/(41п2) + )s/mnj2 = 1.98277-v/m. В результате подобного анализа более общего метода, который выполнен в упр. 3.1-7, получен следующий результат: ~ 1.92600\/пг, где р к, 2.4771366 выбрано "оптимально" как корень из (р - 1) 1пр = р - р -I- 1 (см. BIT 20 (1980), 176-184),

Алгоритм В представляет собой уточненный алгоритм Полларда (Pollard), на базе которого было получено решение упр. 3.1-6(Ь) вместо еще не найденного решения упр. 3.1-7. Поллард показал, что минимальное число п, такое, что Х2п = АГ„, равно среднему значению ~ (7r/12)Q(m) и 1.0308v/ni; эта константа 7г/12 следует из уравнения 4.5.3-(21). Таким образом, общий средний объем вычислений оригинального алгоритма Полларда равен приблизительно 1.030811 - числу операций вычисления наибольших общих делителей (или умножений по модулю т) и 3.092431 операций вычисления квадрата. Это действительно лучше, чем при выполнении алгоритма В в случае, когда затраты на вычисление наибольшего общего делителя больше затрат на вычисление квадрата, умноженных на константу 1.17, как это обычно и случается для больших чисел.

Однако Брент обратил внимание на то, что алгоритм В может быть усовершенствован, если при к > 1/2 из него исключить поиск наибольшего общего делителя; если выполнение шага В4 повторяется до тех пор, пока не станет удовлетворяться неравенство к < 1/2, то цикл можно обнаружить и после выполнения последующих X[i{fi)/X\ = £(fi) - (£{fi) mod A) итераций. В этом случае средние затраты приблизительно равны (3/(41п2))\/7гт/2 и 1.35611v/m - числу итераций, на которых вьшолняется вычисление квадрата без вычисления наибольшего общего делителя, плюс ((1п7Г - 7)/(41п2) + \)\/-кт/2 я: .88 319v/ni - число итераций, на которых выполняются обе операции. [См. анализ Генри Кохена (Henri Cohen) в А Course in Computationai Aigebraic птЪет Theory (Berlin: Springer, 1993), §8.5.]

5. Примечательно, что И 111 = 8616 460 799 (по модулю 3-7-811), поэтому уравнение (14) справедливо и для iV = 11111 за исключением случая, когда модуль равен 5. Поскольку при вычислении (ж - N) mod 5 остатки равны 4, О, 3, 3, О, должно быть х mod 5 = О, 1 или 4. Первая проба х > [\/N] = 106, при которой удовлетворяются все условия, дает X = 144; но вычисление квадратного корня из числа 1442-1,111 = 9625 не дает в результате целое число. Однако следующая проба дает 15б - И 111 = 13225 = 115, и в результате получаем 11111 = (156 - 115) • (156 -1-115) = 41 • 271.

е. Подсчитаем число решений (х,у) конгруэнтных уравнений N = (х - у){х + у) (по модулю р), где О < ж,у < р. Поскольку iV О, а р-простое число, то х + у 0. Для каждого v О существует единственное и (по модулю р), такое, что N = uv. Далее, так как р - простое число, конгруэнтные уравнения х - у = и, x + y = v однозначно определяют а; modp и у modp. Таким образом, указанное выше уравнение имеет точно р - 1 решений (ж,у). Если (ж,у) - решение, то (х,р - у) тоже является решением при у Ф О, так как (р - у) = у; и, если (ж,у1) и (ж,у2)-решения, для которых yi ф уг, то у? = Уг, откуда yi = р - уг. Таким образом, количество различных значений х среди решений (ж, у) равно (р - 1)/2, если уравнение iV = ж не имеет решений, или (р -t- 1)/2, если N = ж имеет решения.

7. Одно из возможных решений состоит в то.м, чтобы для каждого модуля иметь два индекса: один - для адресации текущего слова, другой-для адресации текущего бита; загрузка двух слов таблицы и выполнение индексированной команды сдвига подравняет элементы таблицы. (Такими операциями манипулирования битами оснащены многие компьютеры.)

8. (Можно положить, что N = 2М, т. е. четно.) В следующем алгоритме используется вспомогательная таблица Х[1], Х[2], ..., А[М], где в Х[к] отражен признак принадлежности числа 2к+ 1 к простым числам.

51. Присвоить Х[к] ч- 1 для 1 < Лг < М. Присвоить также j ч- 1, р ч- 3, g ч- 4. (В ходе выполнения этого алгоритма p = 2j + lHq = 2j + 2j.)

52. Если X[j] = О, то перейти к шагу S4. В противном случае вывести р, которое является простым, и присвоить к к- q.

53. Если к < М,то присвоить Х[к] ч-О, /гч-/г-1-ри повторить этот шаг.

54. Присвоить + рр+2, qq+2p - 2. Если j < М, то возвратиться к шагу S2. I

Можно заметно ускорить большую часть вычислений, если на шаге S4 сравнить с М не j, а qr, и добавить новый цикл, который, подавляя манипуляции р и qr, выводит 2j Л- 1 для всех оставшихся X[j], равных 1.

Замечание. Оригинальное решето Эратосфена было описано в книге 1, главе 13 сочинений Никомаха (Nicomachus) /ntroduction to Arithmetic. Хорошо известно, что

i:p„pocxoe[P<]/P = InlniV + М + 0((l0giV)-<"""),