AOP_Tom2 (1021737), страница 205
Текст из файла (страница 205)
(Задача заключается в поиске всех пар целых чисел (Л, д), таких, что (Лз + г)(аз + г ) = Х; отсюда следует, что Ли+ р —щ и: (по модулю з) и л/Лрв < 6, Алгоритм 4.5.2Х будет выполняться без учета величин !з, иг, вг; отношения Лгз + рсс = югм Лиз + рис ш шис, Лез + рвс = швс (по модулю з) остаются инвариантными. ) Е2. [Попытка для делителей.[ Если вс = О, то вывести значение Ля+ г во всех случаях, когда Лз 4 г делит Х и О < Л < д/з. Если вз = О, вывести значение Х/(да + г') во всех случаях, когда да+ г' делит Х и 0 < д < 9/з В остальных случаях для всех !с, таких, что [ювс + !сз[ < д, если вс < О, или 0 < швс + йз < 29, если вз > О, и для а = +1 н — 1 вывести значение Лз+ г, если с! = (швс з+ Гсз + взг+ елг ) — 4щ взХ— точный квадрат и если числа ювсз+ !се + взс' — щг — ел/а Л— свесе + )сз~ — изг+ в~г'+ ел/а являются положительнычи целыми числами.
(Решения для Лвз + рвс — — швз + кз, (Лз+ г)(рз+ г') = Х существуют.) 1 3. [Выполнено?) Если вз = О, то выполнение алгоритма завершается. Ь4. [Разделить и вычесть.| Присвоить д с — [из/вз). Если из = Овз и вс < О, то уменьшить д на 1. Затем присвоить (ссЛз) +- (им из) — (вы аз)9, (им из) +- (вм ез), (вы аз) с- (!м Ь) и возвратиться к шагу Е2. $ (См. 64а!!ь Сошр. 42 (1984), 331 — 340, Оценки для шага 1.2 можно уточнить, например, для того, чтобы обеспечить д > О. Некоторые множители могут выводиться более одного раза.] Здесь ас нечетное число, кратное с/б4, а бо — нечетное число, кратное с~/04. Положим также, чта известны Ла и ЛЬ. Конечна, на самом деле нам не известны значения ое, бо, Ла и Л6, но мы попробуем применить все возможные значения 32с ' х 32г х 2 х 2.
Ложные ответвления программы, которые оперируют некорректными предположениями, не нанесут вреда. Определим числа в виде ип = 2 '(о+(/+-')6) шод пг и оц = 2 ' '(о+26) шоб пг. Оба эти числа ио и оо равномерно распределены в интервале [О., ш), так как числа о и 6 были выбраны случайными. Далее, для фиксираваннога ! числа ио при ус < у < !о+! явлнются попарно незоеисиммми, то же самое относится к числам оп прн уо < у < /о+!до тех пор, пока значение ! не достигнет наименьшего простата множителя числа т.
Числа ио и об можно использовать только для неравенства — 2тс ~ < у < 2тс~. Если для любога из этих чисел имеется множитель, общий с множителем для ш, та задача решена. Для всех о Л. т определим Хо = +1, если о б О, Хо = -1, если — о б О, н то = О, если ( — ") = -1.
Заметим, что Лицем = Хии, поскольку ио = (2 ирем ) шоб т. Поэтому 2 можяа определить Лин и Хоо для всех ! и / при помощи алгоритма А, примененного к ип и оо для 0< ! <1и -2те-' < у < 2те-~. Установка 4 = 1,'„с~т ' в этом алгоритме гаРантиРУет, что все значении величины Х веРны с воРаЯтнастью > 1 — эо. Выполнение алгоритма осуществляется не более чем за т этапов. В начале этапа ! для 0 < ! < т полагаем, что известны значения величин Л2 'а, Л2 'Ь и дробей ао Д, такие, что т2'а ] г тл ос) < 2 с+в т2 — сЬ з тп А < 2'е" Определим а~+1 — — 1(о~ + Л2 'а) и Д.ы = -'(Д + Л2 'Ь); это обеспечивает выполнение неравенств.
На следующем шаге находим Л2 ' 'Ь, которое удовлетворяет отношению Либ + Л2 'о+ 1Л2 Ь+ Л2 Ь+ ~ ~ ы О (по модУлю 2). ] т2 'о+ут2 'Ь+ т2 ' 'Ь ) гп 43. (а) Прежде всего убедимся в том, что символ Якоби ф) равен +1. (Если он равен О, задача упрощается; если он равен -1, то у к О .) Затем выберем случайные целые числа км, к„в интервале [О .. гл) и положим Х, = [С(у~в~ шос) тл) = (уз~ шоб гп) шоб 2[. Если у б !'„1, то ЕХ, > — +ц в противном случае гп — у б б)„, и ЕХг < — — е Сообщить, что у б Ц, если Х1 + Х„> -'и. В силу результата упр. 1.2.10 — 21 вероятность неудачи не превышает величины с м ". Поэтому выбираем и = [зс ~ !пав (Ь) Находим к с символом Якоби ( — ') = — 1 и присваиваем у +- кз шос) гп. В этом случае мнажителнми числа ш бУдУт боб(х+ т/У, гп) и бед(з — ~/У, гп), так чта задача тепеРь состоит в там, чтобы найти +~/у для заданного у б О . Если найти тс для любого ненулевого значении о, то поставленная задача будет решена, поскольку ~/у = (о 'то) шоб го, если боб(о, гп) не является множителем числа т.
Предположим, что для некоторога е > 1 выполняется равенства е = 2 '. Выберем в интервале [О .. гп) случайныо целые числа о и Ь и предположим, что известны двоичные функции ое и Во, такие, что выполняюгся неравенства Пусть и = 4тш(г, 2') г ~; тогда, если [/[ < "-, получаем т2 'а г2 '6 г2 ' '6 г + 1 + — (а + /3 + )3>+>) < †. >л т ги 16 Поэтому. если ти» вЂ” — 1, вероятно, что Л2 ' '6 = С„где С, = (С(ил,р >паб т) + Л2 'а+ /Л2 '6+ [и> у>5> + /?»]) пюб 2. Более точно, получим [(г2 'а+/г2 'Ь+ г2 '6)/гп] = [а> + г!3>+/?>л>), если толька не выполняются неравенства ги» < —,'„гв и ги», (1 — —,'„)т.
Пусть 1> (2ф— 1)ти>>. Если 1; = +1, это довод в пользу Л2 ' 'Ь = 1! если у) = -1, то в пользу Л2 ' 'Ь = О, если 1; = О, то никаких действий не предпринимаем. Будем демократичны и установим Л2 ' 'Ь = [х,"~ „1; > О]. Какова вероятность того, что Л2 ' 'Ь вЂ корректн значение? Пусть Е> = -1, если Ли» Ф 0 и (ги>! < >егп или ги», (1 — —,' )гп, или С(и»у шог! т) ф Ли> ).
В противном случае полагаем, что Е> = [1!ио[. Поскольку Š—.функция и>,, случайные перел>енные Я> попарно независимы и одинаково распределены. Пусть Е = ) ",~ ! Е>; если в > О, значение Л2 ' '6 будет верным. Вероятность того, что Е = О, равна -', а вероятность того, что Е> = +1, равна > > + -' — -'„, поэтому Ел» зг.
Очевидна, что гаг(Е>) < -'. Таким образам, возможность появления ошибки в ветви программы, основанной на правильных предпосылках, согласно неравенству Чебышева не превышает величины Рг(Е < 0) < Рг((Š— пЕЯ) > Дп~г~) < фп 'гз = $ ппп(г 2 ) (см. упр, 3.5 — 42). Аналогичный метод мажет быть использован для определения величины Л2 ' 'а с погрешностью < 1>п!п(г,2') л, если заменить величину и> величиной а>,. Возможна. окажется, что гл/2' е < 1/(2т), так чта число г2 'Ь будет ближайшим целыл> к тбо В этол> случае можно вычислить значение,/р = (2'Ь 'т2 'Ь) шог! т.
Выполнив возведение этого числа в квадрат, можно узнать, были ли мы правы. СУммаРный шанс допУстить >чвибкУ огРаничен величиной — 2„» 2 = э на стадии 1 — > 4 ! < )8п, а на последующих стадиях — величиной ~1 2 >с, г ' = э. Таким образам, общан веро>жнагть возникновения ошибки, включая возможность того, что не все значения величины х бь>ли определены верно, пе превьппает — + э- + — ' =,а Выполнение программы завершится успешным вычислением значаннэя,/у не менее чем в —,р случаев; 1 следовательно, мнохгители чиш>а гв будут получены после повторения процесса в среднем ие более десяти раз. В общем времени выполнения программы доминирует величина О(гг ~!об(гг ~)Т(С)), соответствующая времени вычисления х. К ней следует добавить 0(г~г "Т(С)) — время, затрачиваемое на последующие прогнозы, и 0(глг в) — время на вычисление значений о>, ,>3>, Л2 'и и Л2 'Ь ва всех ответвлениях программы.
Эта процедура, которая ясно иллюстрирует основные парадоксы вероятностных алгоритмов, разрабатана Р. Фи>алином (В.. Р!эсЬ!!и) и К -П Шнорром (С.-Р. ЯсЬ>>агг) [Бес!ага №Гев >и Сошр, Ясй 1233 (1997), 2б7-279] на базе бочге ранних исследований, выполненных Алекси (А1ех>), Чарам (СЬог), Галдрихол> (Сей!ге!сЬ) и Шнорром [о!СОМР 17 (1988), 194-209], а также Бен-Ором (Вев-Ог), Чаралг и Шамиролг (БЬагв!г) [БТОС 15 (1983), 421-430).
Если объединить эту процедуру с леммой 3.5Р4, получится теорема, аналогичная теореме 3.5Р, в которой последовательность 3.2 2-(17) заменяется последовательностью 3.2.2 — (1б). Фишлин и Шнарр показали, как упорядо- чить вычисления, чтобы алгоритм разложения на простые множители выполнялся за 0(т ~ 1ой(ге ')Т(С)) шагов; результирующая оценка времени "взлома" 3.2.2 — (1б) есть Т(Г) = 0(Ргйме 1ой(/1/гг ')(Т(С)+/1 )). Постоянный множитель О в этом рввегютвс достаточно велик, но в обозримых пределах. Подобным методом можно получить х из НЯА-функции у = х' шо8 т для случая, когда а 3. ог(т), если предсказывать уы' глоб 2 с вероятностью > -'+ е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
