Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 98
Текст из файла (страница 98)
Положим еще, что сг . 1«М+ 2"~,аои«о«и Р(х) = со+ с«х+ .. + а««х~ ', Тогда при 1 < «< Ь имеем Р(х) ы о;(а«о+апх+ +ан«мх ') ш О (по модулю т«); так что Р(х) ш О (по модулю м). кроме того, (пг" сг) < М/«1, откуда слелует, что Р(х) = О, Но Р(х) не равно тождественно нулю. так как из условий о,ап ш 0 (по модулю т;) н бс«!(а,о,..., ако го т,) = 1 следует о«ш 0 (по модулю т,), в то время как иэ неравенства ) с«М/«пьб! < М/4 следует неравенство (о,( < гпп поэтому не может быть, чтобы одновременно о~ = . = оь ы О, Таким образом, можно найти х (точнее, не более «! — 1 возможных значений х).
Общее время выполнения алгоритма выражается в виде полинома по !8 М. (1,осгпге ««огхэ !л Сагир. Яс«'. 218 (1935), 403-408.) 43. Следствие 1. Решение всегда существует, Предположим сначала, что и — простое число, Если (-„) = 1, то при у = 0 решение существует. Если (-„) = -1, то пусть у > О принимает минимальное значение, прн ко~ором выполняется равенство Я-") = -1; тогда хо — а ш -уа и Ь ш -уа(уо) для некоторых хо н уо (по модулю и). Следовательно, г г (хоуо) — ауо ш Ь.
Предположим теперь, что найдено решение уравнения х — ау ш Ь (по г г— г г модулю и) и его нужно распространить на решение по модулю и . Можно всегда найти г такие значения параметров с и 4, что (х+ сп) — а(у+ Ии) ш Ь (по модулю и ), поскольку (х + сп)г — а(у + 4п)г ш хг — аут + (2сх — 2ау«()п н боб(2х,2ау) .1. и. Следовательно, в случае, когда и является степенью нечетного простого числа, решение всегда существует. (Необходимо еще положить, что число н также нечетно, потому что, например, уравнение хг ш уг ш 3 (по модулю 8) решений не имеет,) Таким образом, в соответствии с китайской теоремой об остатках решение существует для всех нечетных и. Следствие 2. Для заданных а и и, для которых а .!.
и, число рен«ений одинаково дли всех Ь .1. и. Это следует из тождества, приведенного в указании, и факта 1, так как если х~« — ау«~ ш Ь. то (х«хг — ау«уг,х«уз+лгу«) удовлетворяет всем решениям уравнения х — ау ш Ь, как только (хз,уз) удовлетворяет всем решениям уравнения х — у ш 1. з з 3 2 Другими словами, пара решений (хг, уг) однозначно определяется парами решений (хм у~) н (х, у), как только получим хз — ар~ .!.
и. Следствие 3. По задавнмм целым числам (а, э, э), таким, что эз ш а (по модулю е), можно найти целые числа (х, у, ш,1), для которых выполняется равенство х — ау = гп эг, где (х,р) !4 (0,0) и гз < з]а]. Действительно, если зз ы а+ шэ, то (н,в) будет парой ненулевых целых чисел, минимизирующих функцию (хи+те) +]а]вз.
Значение этой пары можно найти, используя методы из раздела 3 3 4 и неравенство (эв+шэ)'+]а]в' < (3]о]) ы' из упр. 3 3 4 — 9. Поэтому (хи+те)з-аиз ш тг, где 1з < 4]а]. Уравнение хе-ауз = (пзэ)(шг) решается иа основании тождества из указания. Следствие 4. Уравнение хэ — рз и Ь (по модулю и) решается просто, так как можно положить, что х = (Ь+ 1)/2, у = (Ь вЂ” 1)/2. Следствие 5. Нетрудно решить и уравнение хе+ уз ш Ь (по модулю и), потому что при помощи рассмотренного в упр. 3.3.4-11 метода можно решить уравнение х + у = р 3 3 для р простого и р шод 4 = 1; таким простым числом будет одно из чисел Ь, Ь+ и, Ь+ 2п,.... Теперь решать сформулированную задачу для случая, когда ]а] > 1, можно сле- дующим образом. Сначала выберем числа в и е как случайные в интервале между 1 и и — 1, затем вычислим значения ю = (вз — оез) шоб и и б = йсб(ю, и).
Если 1 < 6 < и нли йсб(о,п) > 1, то можно уменьшить и; методы, используемме для доказательства следствия 1, переведут решения, полученные для множнтелей числа п, в решения для самих чисел и. Если 6 = и и э .!. и, то (и/е)з ш а (по модулю и); значит, можно уменьшить о на 1.
В противном случае 6 = 1; положим, что э = Ьышобп. Это число э согласно следствию 2 равномерно распределено между простыми числамн до и. Если ('-,) = 1, попытаемсн найти решение уравнения эз и а (по модулю э), пошзгая, что э — простое число (упр. 4.6.2-15). Если решение не удалось найти, предпринимаем вторую попытку при другом выборе случайных чисел к и и. Если же решение найдено, полагаем. что эз = а+ эпэ, и вычисляем 6 = бег)(гпэ, и). Если Ы > 1, то упрощаем задачу в соответствии с описанной выше процедурой. В противном случае используем следствие 3 для того, чтобы найти х — ау = ш в! при Ф < -]о]; это приводит к уравнению (х/т) — а(9/га) ш е! (по модулю и).
Если Г = О, то уменьшаем о на 1. В противном случае для решения уравнения Х вЂ” !У ш о (по модулю и) применяем этот алгоритм рекурсивно. (Так как ! эначитеяьно 3 3 меньше, чем о, то потребуется только О(!об !ой и) уровней рекурсии.) Если йсб(1; и) > 1, можно уменьшить парачетры и и а; в противном случае получим (Х/У) — о(1/1') ш Г (по молулю я). В итоге указанное тождество дает решение уравнения х — ау ш е м ~з (см.
следствие 2), которое приводит к искомому решению, так как и — ое ш э/Ь. 2 3— На практике, как правило, требуется только О(!ойп) сэучайньп пробнык чисел для того, чтобы гарантировать успешное выполнение этого алгоритма в соответствии со сделанным предположением, Но для формального доказатечьства потребуется принять во внимание расширенную гипотезу Римана ~(1ЕЕЕ Тгалз. 1Т-33 (1987), 702-709]. Более сложный и медленный алгоритм, который не основывается ни на одном из недоказанных предположений, предложили Эдлеман (Ао!ешал), Истес (Евсея) н Мак-Керлн (МсСвг!еу) (Магй. Сошр.
48 (1987), 17-28], 46. (РОСЯ 20 (!979), 55 — 60.] После того как числа оьч шобр = ]'1'", р " получены для достаточного козшчества п„можно найти целочисленное решение хеь, !ы, 1 < у, Й < ш уравнения ~, хпэ со+(р — 1)г э ш 5 ь (иапример, как для уравнения 4.5.2-(23)), подставляя известные решения Д', = (2, х, .ьезь ) пшб (р — 1) в ал, шоб р = рз.
Тогда, если Ьа"' шоб р = Ц,, р,'], получим и+ и' ш 2 ',", е' т, (по модулю р — 1). [Известны усовершенствованные а.згоритмы (см., например, Соррешписп, Об!уэко, Зсйгоерре1, А!бог!1Ьш1са 1 (1986), 1-15).] РАЗДЕЛ 4.б 1. 9хз+ ух+7; бхз+ Тхз+ 2х+6. 2. (а) Истинно. (Ь) Ложно, если алгебраическая система о содержит делители мулл, т. е. ненулевые числа, произведение которых равно нулю, как в упр. 1; в противном случае — истинно. (с) Истинно при ш ээ п, ио, вообще говоря, ложно при ш = и, так как старшие коэффициенты могут сократиться. 3.
Положим, что г < з, При 0 < х < г максимум равен ш~гпз(й+ 1), при г < я < з он равен шатт(г+ 1) и при з < й < г+ в равен тгшз(~ + з+ 1 — й). Наименьшая верхняя граница, справедливая для всех я, равна тгтт(г+ 1). (Тот, кто решил эту задачу, теперь знает, как разделить иа множители полипом хг + 2хе + Зх~ + Зхэ + Зх + Зх~ + 2х + 1 ) 4. Если один из полиномов имеет меньше 2' ненулевых коэффициентов, произведение можно найти, поместив ровно ! — 1 нулей между всеми коэффициентами, а затем выполнив умножение в двоичной системе счисления и использовав побитовую операцию АМО (которая имеется в большинстве двоичных компьютеров; см. алгоритм 4.5.411) для обнулеиня лишних битов.
Например, при ! = 3 умножение, приведенное в тексте раздела, будет иметь вил (1001000001)з х (1000001001)з = (1001001011001001001)з Искомый ответ может быть получен с помощью побитовой операпии 190 с константой (1001001...1001)з. Подобная методика применима для умножения полиномов с не очень большими неотрицательными коэффициентами.
5. Полиномы степени < 2п могут быть записаны как У~(х)х" + Уе(х), где г!еб(У~) < 68((Т,) <, ((Т,() "+и.(х))(~;(*)*"+ ц,()) = и,()1:,( Н '+х")+ (Уз(х) + Уо(х))(г)(х) + 1е(х))х" + Уо(х))ге(х)(х" + 1). (В уравнении предполагается. что арифметические действия выполняются по модулю 2.) Таким образом, выполняются соотношения 4.3.3-(3) и 4,3.3-(5). Примечание. С. А. Кук (8. А. СооЬ) показал, что алгоритм 4.3.3Т можно расширить таким же способом.
А. Шеихаге (А. ЯсЬбпЬабе) (Асса Тлгогшаг!са 7 (1977), 395-398) показал, как можно умножить полииомы по модулю 2 при помощи 0(п!обо!об!обо) битовых операций. В действительности полииомы иад любым кольцам Я могут быть умножеиы с помощью 0(п 1об и!об 1об и) алгебраических операций, даже когда Я представляет собой жпебраическую систему, в которой умножение может не быть коммутативным пли ассопиативным (О. С. Свпсог апб Е. Ка!со!со, Асса Елгогшас1са 28 (1991), 693-701]. См. также упр. 4.6.4-57 и 4.6.4-58. Однако зти идеи практически бесполезны для разреженных полиномов, большинство коэффициентов которых нулевые. РАЗДЕЛ 4.6.1 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
