чить вычисления, чтобы алгоритм разложения на простые множители выполнялся за 0(гlog{rf ~)T{G)) шагов; результирующая оценка времени "взлома" 3.2.2-(16) есть T(F) = 0{RNe-log{RNe~){T{G)+R)). Постоянный множитель О в этом равенстве достаточно велик, но в обозримых пределах. Подобным методом можно получить х из RSA-функции 2/ = х" mod m для случая, когда о ± ifiim), если предсказывать у" mod 2 с вероятностью > 5 + е.

44. Предположим, что Ej=o*J = О (п° модулю тщ), gcd(oio,Oii,... ,a,(rf i),mi) = 1 и х < ТПг для 1 < i < А; = d(d - 1)/2 + 1, где тПг ± mj при 1 < г < j < fc. Положим также, что т = тш{ть..., т*,} > vP-llld, где п = d + fc. Сначала найдем такую последовательность значений Ui, и*,, чтобы выполнялись равенства Wj mod mi = Jij. Теперь сформируем матрицу размера п х тг

/ М О

Oiottl

020U2

тМ О

mautti

m02lU2

m"* 02(<i i)tt2

M/mid

0 M/mid

M/mkd/

где M = mim2...m*. Bee наддиагональные элементы этой матрицы равны нулю, следовательно, deti = M"-m*-d-*. Пусть теперь d = {to, ,td-i,vi,... ,Vk) - ненулевой вектор с целочисленными компонентами длинoй(г)L) < \/Ti2"M"-"m*-"d-*". Поскольку М"-"." < М/т", длина (vL) < M/d. Положим еще, что Cj = tjM + Е,*=1 fflijWiii и -РС) = со -I- cix -Н ••• -I- Cd-ix"*-. Тогда при ] < г < fc имеем Р(х) =

fiCaio-l-OiixH-----f-Oi(d i)x-) = О (по модулю mi); так что Р(х) = О (по модулю М). Кроме

того, m-cj < M/d, откуда следует, что Р(х) = 0. Но Р(х) не равно тождественно нулю, так как из условий DiOij = О (по модулю mt) и gcd(aio,... ,аца-1),т{) = 1 следует vi = О (по модулю mi), в то время как из неравенства DiM/mid < M/d следует неравенство \vi\ < mi; поэтому не может быть, чтобы одновременно vi = = Vk = 0. Таким образом, можно найти X (точнее, не более d - 1 возможных значений х). Общее время выполнения алгоритма выражается в виде полинома по IgM. [Lecture Notes in Сотр. Sci. 218 (1985), 403-408.]

45. Следствие 1. Решение всегда существует. Предположим сначала, что п - простое число. Если () = 1, то при у = О решение существует. Если () = -1, то пусть j > О принимает минимальное значение, при котором выполняется равенство () = - 1; тогда Xq - а = -ja и Ь = -ja{yoy для некоторых хо и уо (по модулю тг). Следовательно, {хоуоУ - ауо = Ь. Предположим теперь, что найдено решение уравнения х - ау = 6 (по модулю тг) и его нужно распространить на решение по модулю п. Можно всегда найти такие значения параметров cud, что (х + стг) - а{у + dn) = Ъ (по модулю тг), поскольку (х 4- cTif - а{у 4- dтг) = х - оу 4- (2сх - 2ayd)Ti и gcd{2x,2ay) ± тг. Следовательно, в случае, когда тг является степенью нечетного простого числа, решение всегда существует. (Необходимо еще положить, что число тг также нечетно, потому что, например, уравнение х ± = 3 (по модулю 8) решений не имеет.) Таким образом, в соответствии с китайской теоремой об остатках решение существует для всех нечетных тг.

Следствие 2. Для заданных а и тг, для которых а ± тг, число решений одинаково для всех Ь ± тг. Это следует из тождества, приведенного в указании, и факта 1, так как если xj - ayi = h, то (xiX2 - ayiy2,xiy2 + Xiyi) удовлетворяет всем решениям уравнения

- ay = 6, как только [хуг) удовлетворяет всем решениям уравнения х - у = 1. Другими словами, пара решений (х2,у2) однозначно определяется парами решений (х 1,2/1) и {х,у), как только получим xj - ayj ± тг.

Следствие 3. По заданным целым числам (о,в,г), таким, что = о (по модулю в), можно найти целые числа (х, у, т, t), для которых выполняется равенство х - ау = mst, где (x,j/) ф (0,0) п t < о. Действительно, если z = а + ms, то {u,v) будет парой ненулевых целых чисел, минимизирующих функцию (2tt+rm)) + ott. Значение этой пары можно найти, используя методы из раздела 3.3.4 и неравенство (2tt+rm)) + ott < (а) из упр. 3.3.4-9. Поэтому (zu+mv)-аи = mt, тдаЬ < о. Уравнениех-оу = {ms){mt) решается на основании тождества из указания.

Следствие 4. Уравнение х - у -Ь (по модулю п) решается просто, так как можно положить, что X = (6 + 1)/2, у =. [Ь- 1)/2.

Следствие 5. Нетрудно решить и уравнение х -\-у =.Ь (по модулю п), потому что при помощи рассмотренного в упр. 3.3.4-11 метода можно решить уравнение х -\- у = р для р простого и р mod 4 = 1; таким простым числом будет одно из чисел 6,6+ п, 6 + 2п,....

Теперь решать сформулированную задачу для случая, когда о > 1, можно следующим образом. Сначала выберем числа it и d как случайные в интервале между 1 и п - 1, затем вычислим значения w = (tt - av) modn и d = gcd(u;,n). Если 1 < d < n или gcd(ii,n) > 1, to можно уменьшить n; методы, используемые для доказательства следствия 1, переведут решения, полученные для множителей числа п, в решения для самих чисел п. Если d = п и d ± п, то (u/v) = а (по модулю п); значит, можно уменьшить а на 1. В противном случае d = 1; положим, что s = bwmodn. Это число s согласно следствию 2 равномерно распределено между простыми числами до п. Если () = 1, попытаемся найти решение уравнения z = а (по модулю в), полагая, что s - простое число (упр. 4.6.2-15). Если решение не удалось найти, предпринимаем вторую попытку при другом выборе случайных чисел и и v. Если же решение найдено, полагаем, что z = а + ms, и вычисляем d = gcd(ms, п). Если d > 1, то упрощаем задачу в соответствии с описанной выше процедурой. В противном случае используем следствие 3 для того, чтобы найти х - ау = msi при t < а; это приводит к уравнению (х/т) - а{у/т) = st (по модулю п). Если t = О, то уменьшаем а на 1. В противном случае для решения уравнения Х - tY = а (по модулю п) применяем этот алгоритм рекурсивно. (Так как t значительно меньше, чем а, то потребуется только O(loglogn) уровней рекурсии.) Если gcd(y, п) > 1, можно уменьшить параметры п и а; в противном случае получим (X/Y) - a{l/Y) = t (по модулю Л). В итоге указанное тождество дает решение уравнения х" - ау" = s (см. следствие 2), которое приводит к искомому решению, так как и - av = s/b.

На практике, как правило, требуется только 0(log п) случайных пробных чисел для того, чтобы гарантировать успешное выполнение этого алгоритма в соответствии со сделанным предположением. Но для формального доказательства потребуется принять во внимание расширенную гипотезу Римана [ШЕЕ Trans. IT-33 (1987), 702-709]. Более сложный и медленный алгоритм, который не основывается ни на одном из недоказанных предположений, предложили Эдлеман (Adleman), Истее (Estes) и Мак-Керли (McCurley) [Math. Сотр. 48 (1987), 17-28].

46. [FOCS 20 (1979), 55-60.] После того как числа а"< modp = IljIiP получены для достаточного количества п;, можно найти целочисленное решение Xijk, tjk, 1 <: j,k < т уравнения J2i Xijkeij+{p-l)tjk = Sjk (например, как для уравнения 4.5.2-(23)), подставляя известные решения Nj = (Ej Xijkejk) mod (p- 1) в aj modp = pj. Тогда, если 6a" modp = njLi Pfij получим n + n = Eji jNj (no модулю p - 1). [Известны усовершенствованные алгоритмы (см., например. Coppersmith, Odlyzko, Schroeppel, Alg-orithmica 1 (1986), 1-15).]

РАЗДЕЛ 4.6

1. + 7х + 7; 5х + Чх" + 2х + 6.

2. (а) Истинно. (Ь) Ложно, если алгебраическая система 5 содержит делители нуля, т. е. ненулевые числа, произведение которых равно нулю, как в упр. 1; в противном случае - истинно, (с) Истинно при т ф п, но, вообще говоря, ложно при т = п, так как старщие коэффициенты могут сократиться.

3. Положим, что г < S, При О < к < г максимум равен mim2{k + 1), при г < А; < s он равен mim2(r + 1) и при з < к < г + з равен mim2(r + з + I - к). Наименьщая верхняя граница, справедливая для всех к, равна mim2(r + 1). (Тот, кто рещил эту задачу, теперь знает, как разделить на множители полином х + 2х* + Зх° + Зх + Зх + Зх + 2х + 1.)

4. Если один из полиномов имеет меньще 2* ненулевых коэффициентов, произведение можно найти, поместив ровно t - 1 нулей между всеми коэффициентами, а затем выполнив умножение в двоичной системе счисления и использовав побитовую операцию AND (которая имеется в больщинстве двоичных компьютеров; см. алгоритм 4.5.4D) для обнуления лищних битов. Например, при t = 3 умножение, приведенное в тексте раздела, будет иметь вид (1001000001)2 X (1000001001)2 = (1001001011001001001)2. Искомый ответ может быть получен с помощью побитовой операции AND с константой (1001001... 1001)2- Подобная методика применима для умножения полиномов с не очень большими неотрицательными коэффициентами.

5. Полиномы степени < 2п могут быть записаны как J7i(x)x" + Uo{x), где deg(J7i) < п и deg{Uo) < п, и ([7i(x)x" + Uo{x))(Vi{x)x" + Vo{x)) = Ui{x)Vi{x){x" + x") + (J7i(x) + Uo{x)){Vi(x) + Vo{x))x" + Uo{x)Vo{x){x + 1). (B уравнении предполагается, что арифметические действия выполняются по модулю 2.) Таким образом, выполняются соотнощения 4.3.3-(3) и 4.3.3-(5).

Примечание. С. А. Кук (S. А. Cook) показал, что алгоритм 4.3.3Т можно расширить таким же способом. А. Шёнхаге (А. Schonhage) [Acta Informatica 7 (1977), 395-398] показал, как можно умножить полиномы по мод,лю 2 при помощи 0(пlog nlog log п) битовых операций. В действительности полиномы над любым кольцом S могут быть умножены с помощью 0(п log nlog log п) алгебраических операций, даже когда S представляет собой алгебраическую систему, в которой умножение может не быть коммутативным пли ассоциативным [D. G. Cantor and Е. Kaltofen, Acta Infornjatica 28 (1991), 693-701]. См. также упр. 4.6.4-57 и 4.6.4-58. Однако эти идеи практически бесполезны для разреженных полиномов, большинство коэффициентов которых нулевые.

РАЗДЕЛ 4.6.1

1. q{x) = 1 • 2х + О • 2x2 - 2 • 2х -f 8 = 8х - 4х -f 8; г(х) = 28x2 -f 4х -f 8.

2. Последовательность нормированных полиномов, полученная при работе алгоритма Евклида, имеет коэффициенты (1,5,6,6,1,6,3), (1,2,5,2,2,4,5), (1,5,6,2,3,4), (1,3,4,6),0. Следовательно, наибольщий общий делитель равен х + Зх -f- 4х -f 6. (Наибольший общий делитель полинома и "обратного" к нему всегда симметричен в том смысле, что он равен своему "обратному", умноженному на обратимый элемент.)

3. Алгоритм 4.5.2Х остается корректным при замене целых чисел полиномами над S. По завершении алгоритма мы получим U{x) = И2(х), V(x) = Ui{x). Пусть m = deg(w), п = deg(D). По индукции легко доказать, что после шага ХЗ в процессе выполнения алгоритма deg(w3) -t- deg(Di) = п, deg(w3) -t- deg(D2) = m при условии, что m > п. Следовательно, если тип больше, чем d = deg(gcd(M, г;)), то deg{U) < m-d, deg(V) < n-d; точные степени равны m - di ип - di, где di - степень предпоследнего ненулевого остатка. При d = шт(тп, п), скажем, d = п, имеем U{x) = О и V(x) = 1.