Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 97
Текст из файла (страница 97)
[Попытка для делителей.[ Если ег = О, то вывести значение Лэ+ г во всех случаях, когда Лэ+ г делит Ь' и О < Л < В/ж Если иэ = О, вывести значение гг/(дэ + г') во всех случаях, когда де+ г' делит Ю и 0 < д < В/э. Б остальных случаях для всех Ь, таких, что [игег + Ьэ[ < В, если эг < О, или 0 < «гег + Ьэ < 2В. если иг ) О, и для о = +1 и -1 вывести значение Аз+ г, если г! = (могэ+Ьээ+иэг+егг~)~ — 4вгезггг— точный квадрат и если числа юегэ+ Йэ — ээг+ егг'+ аг7п' юегэ+ Йээ+ оэг — игг' — ог/й А— И— 2оээ 2еээ являются положительными целыми числами.
(Решения для Лггэ + лег = эгег + Ьэ, (Лэ+ т)(дэ+ г') = Ьг существуют) ! 3. [Выполненоу[ Если еэ = О, то выполнение алгоритма завершается. 14. [Разделить и вычесть.) Присвоить 9 г- [иэ/еэ). Если иэ = Вцг и ог < О, то уменьшить 9 на 1. Затем присвоить (!г, !э) е- (иг, из) — (щ, ггэ)9, (иг, иэ) г- (югг оз), (иг, еэ) э- (!г,ээ) и возвратиться к пшгу Е2. $ [См.
Магб. Сопср. 42 (1984), 331-340. Оценки для шага 12 можно уточнить, например, для того, чтобы обеспечить с! > О. Некоторые множители могут выводиться более одного раза.) 43. (а) Прежде всего убедимся в том, что сспивол Якоби (Ц равен +1. (Если он равен О, задача упрощается; если он равен — 1, то у ф г„!, .) Затем выберем случайные целые чнщса хс, ..., х„в интервале [О..т) и положим Х, = [С(узхсс шобси) = (ухэ шос)т) шоб2). Если у О !„с, то ЕХ. > -'+с; в противном случает — уб ! с и ЕХ! < 1~ — с.
Сообщить, что у б !Г,, если Хс .. + Х„> -'и. В силу результата упр. 1.2.10-21 вероятность неудачи не превышает величины е и ". Поэтому выбираем и = [со с!в 4 с), (Ь) Находим х с символом Якоби ( — *) = -1 н присваиваем у с- хз шобт. В этом случае множителнми числа т ОУдУт бес((х+ с/У, т) и бес((х — с/У, сл), так что задача тепеРь состоит в том, чтобы найти х,/у для заданного у б 1,!„. Если найти ги для любого ненулевого значения е, то поставленная задача будет решена, поскольку с/у = (о 'го) шобт, если боб(и, сп) не является множителем числа т. Предположим, что для некоторого е > 1 выполняется равенство г = 2 ".
Выберем в интервале [О .. т) случайные целые числа а и Ь н предположим, что известны двоичные функции оо и Ссо, такис, что выполняклся неравенства Здесь по — нечетное число, кратное с/64, а,Уо — нечетное число, кратное со/64. Положим также, что известны Ла и ЛЬ. Конечно, на самом деле нам не известны значения ао, !!о, Ла н ЛЬ, но мы попробуем применить все возможные значения 32с ' х 32с о х 2 х 2. Лажные ответвления программы, которые оперируют некорректными предположениями, не нанесут вреда. Определим числа в виде щ = 2 '(а+(!+-')Ь) шос) тиос = 2 ' '(а+ сЬ) шобт, Оба эти числа ис, н осс равномерно распределены в интервале [О ., сп), так как числа а и Ь были выбРаны слУчайными. Далее, дла фикснРованного ! числа исс пРи Уо < !' < /о+! Явлаютск попа!жо независимыми, то же самое относится к числам осс при уо < у < Уо + ! до тех пор, пока значение ! не достигнет наименьшего простого множителя числа т.
Числа вс, и о, можно использовать только для неравенства -2ге < з < 2гс~. Если для любого из этих чисел имеется множитель, общий с множителем для пс, то задача решена. Для всех и .!. т определим Ле +1, если о б О, хо = -1, если -о 6 с), и хо = О., если (-') = — 1. Заметим, что хв!сот!с = хасс с поскольку и,с = (2ка!сслсс) шоб пс, Поэтому можно определить увсс и хаасс для всех ! и У при помощи алгоритма .4, примененного к асс и асс для О < с < 1 и -2гс-о < 2 < 2--э. Установка 4 =,„с,о "г-с в этом алгоритме гарантирует, что все значения величины х верны с вероятностью > 1 — — '.
Выполнение алгоритма осуществляется не более чем за г этапов. В начале этапа с для 0 < ! < г полагаем, что известны значения величин Л2 'а, Л2 'Ь и дробей ас, !!с, такие, что Определим осес = -„'(ос + Л2 'а) и с1с с = ус(/!с + Л2 'Ь); зто обеспечивает выполнение неравенств. На слелсющем шаге находим Л2 ' 'Ь, которое удовлетворяет отношению Лиц+ Л2 а+уЛ2 Ь+Л2 Ь+ ~ ~ 0 (по модулю 2). -с -с-с [г2 'а+уг2 'Ь+г2 ' 'Ь! Пусть и = 4 шш(г, 2') 4 9; тогда, если !/! < -", получаем г2 'а,г2 '6 г2 ' 'Ь +/ — + — (о +/84+44-4)~ < —. т т т 1б Поэтому, если уиг, = 1, вероятно, что Л2 ' '6 = С,, где С.
= (С(игур пюг! пг) + Л2 'а + /Л2 Ь+ (ог/114+8441)) пюг) 2. Более точно, получим ((г2 'а+/г2 'Ь+ г2 ' 46)/тп) = (а, + Щ+ 8441), если только не выполняются неравенства гиг. < 19т и гиг; > (1 — — 49)т. Пусть 15 = (2С„- 1)Ашм Если 1! = +1, это довод в пользу Л2 ' 'Ь = 1; если 7' = -1, то в пользу Л2-' 'Ь = О, если У, = О, то никаких действий не предпринимаем, Будем демократичны и установим Л2 ' 'Ь = (2 "~ „1' > О).
Какова вероятность того, что Л2 ' 'Ь вЂ” корректное значение? Пусть 84 = -1, если Аигг 94 0 и (гим < вш или гиц > (1 — —,' )пз, или С(ит;9 шог(т) й Лиг,). В противном случае полагаем, что Я, = (Аиг (. поскольку оз — функция иг, случайные переменные л9 попарно независимы и одинаково распределены. Пусть 8 = 2 ~ „гг Я„. если Я > О, значение Л2 '"'Ь будет верным. Вероятность того, что 81 = О, равна -', а вероятность того, что Я, = +1, Равна > -'+ г — -', поэтомУ Е У! > зс Очевидно, что чаг(Я,) < 1. Таким образом, возможность появления ошибки в ветви программы, основанной на правильных предгюсылках, согласно неравенству Чебышева не превышает величины Рг(У < О) < Рг((У вЂ” п Его) > еп 4 ) < Ьэп 'г = ~~ шш(г,2') (см, упр, 3.5-42).
Аналогичный метод может быть использован для определения величины Л2 ' 'а с погрешностью < 9 ппв(г,2') ', если заменить величину нг; величиной 440. Возможно, окажется, что 49/2' 9 < 1/(2гп), так что число г2 'ь будет ближайшим целым к тД. В этом случае можно вычислить значение,/у = (2'6 ' г2 'Ь) пюб т. Выполнив возведение этого числа в квадрат, можно узнать, были ли мы правы. Суммарный шанс допустить шоибку ограничен величиной - 4,4>, 2 = 9 на стадии 4 -С 4 ! < !8п, а на последующих стадиях — величиной -' 2 4<, г ' — 9.
Таким образом, общая вероятность возникновения ошибки, включая возможность того, что не асе значения величины А были определены верно, ие превышает 9 + - + щ — — —,„. Выполнение 4 4 1 9 программы завершится успешным вычислением значения,/у не менее чем в 19 случаев; следовательно, множители числа гп будут получены после повторения процесса в среднем не более десяти раз. В общем времени выполнения программы доминируетвеличина О(гс 4!о8(гг 9)Т(С)), соответствующая времени вычисления й.
К ней следует добавить 0(ггс гГ(С)) — время, затрачиваемое на последующие прогнозы, и О(гзс 9) — время на вычисление значений аг,. 84, Л2 'а и Л2 'Ь ао всех ответвлениях программы. Эта процедура, которав ясно иллюстрирует основные парадоксы вероятностных алгоритмов, разработана Р. Фишлином (В.. Р!эсЬ!!в) и К.-П. Шнорром (С.-Р. 8сЬпогг) (Х.ос!иге Уогез ш Сошр. 8сй 1233 (1997), 287-279) на базе более ранних исследований, выполненных Алекси (А!ех!), Чором (СЬог), Голдрихом (Оо!Оге1сЬ) и Шнорром (8!СОМР 17 (1988), 194-209), а также Бен-Ором (Веп-Ог), Чором и Шамиром (8Ьапнг) (АТОС 15 (1983), 421-430).
Если объединить эту процедуру с леммой 3.5Р4, по. лучится тсореъга, аналогичная теореме 3.5Р, в которой последовательность 3.2.2-(ру) заменяется последовательностью 3.2.2 — (15). Фишлин и Шнорр показали, каи упорядо- чить вычисления, чтобы алгоритм разложения на простые множители выполнялся за 0(ге «1об(гс «)Т(0)) шагов; результирующая оценка времени "взлома" 3.2.2-(10) есть Т(Р) = 0(Я!у~о «!об(Я№ ~)(Т(1«)+«с~)). Постоянный множитель 0 в этом равенстве достаточно велик, но в обозримых пределах. Подобным методом можно получить х нз ВЗА-функции у = х' шо«! гп для случая, когда а ~. ш(т), если предсказывать ум" шоб 2 с ве1ювтностью > Зг + о.
44, Предполох«нм, что 2 ~~ о а«хг ш О (по модулю т,), боб(а о, ам,...,ац« .,м т.,) = 1 и !х!<т«двя1<«<ймЙ(Ы вЂ” 1)/2+1,гдегп;.!.т при1<«< 1<3, Положим также, что т = ш!п(тм.,.,гпь) > и"Гг2«)гб«, где 0 = «(+ Ь.
Сначала найдем такую последовательность значений им, иь, чтобы выполи«мчись равенства и, шоб т, = Ьп. Теперь сформируем матрицу размера и х и О о ... 'М а«ои«пгаыщ ... т ац«мш М/т«| агоиг пюпиг ... т 'аг!«Оиг 0 М/тг«! аьоиь таь«иь ... т~ 'аы«- !иь 0 0 ... М/тоЫ где М = т«тг... то. Все иаддиагонвльные элементы этой матрицы равны нулю, следовательно, «!есТ = М" 'ть 'Ы ь. Пусть теперь и = (го,...,!«мим...,ог) — ненулевой вектор с целочисленными компонентамн длиной(оХ) < «/п2«М/" '>г"т!«МГ"Ы Поскольку Мш МГ," < М/тьГ", длина (о1) < М/4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
