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