Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 54
Текст из файла (страница 54)
Следовательно, на шаге ЬЗ выводится вектор х'(Ь) = х((Ь+ Ву) шос1 2) +аз по модУлю 2. ПосколькУ Ь пРобегает все стРоки. состоЯщне из Ь двоичных разрядов, (Ь+ В ) пкк1 2 также пробегает эти строки, следствием чего является дополнение у-м двоичным разрядом каждого х на выходе. Следовательно, достаточно доказать, что вектор х = 0... 0 можно вывести, как только С(г) хорошо аппроксимнрует постоянную функцию О. В действительности мы покажем, что х(0...
О) равняется 0... 0 иа шаге ЕЗ с большой вероятностью всякий раз, когда С(х) с большей вероятностью принимает значение О, чем 1, н к является достаточно большим. Точнее говоря, условие выполняется для 1 < 1 < В с вероятностью > -', если в = Е(( — 1)обб) положительно, где среднее берется по всем 2л возможным х и если й достаточно велико.
Ключом исследования является утверждение, что для каждого фиксированного с = сы .. сь З~ 0... О строка Н = сВ равномерно распределена: каждое значение И появляется с вероятностью 1/2", так как двоичные разряды В случайны. Более того, когда с ф с' = с', . сь, строки Н = сВ и Н' = с'В независимы: каждое значение пары (г1, г(') происходит с вероятностью 1/2з~. Следовательно, можно рассуждать, как при доказательстве неравенства Чебышева: для любого фиксированного 1 сумма ~,яэ( — 1):~" +"> отрицательна с вероятностью, не большей, чем 1/((2" — 1)вэ). (Подробности содержатся в упр. 42.) Поэтому В/((2" — 1)вз) — верхняя грань вероятности того, что х(0) не является нулем на шаге 1.3.
Теорема С. Если ь = Е((-1)об~+'-') > 0 и 2ь > (2В/вэ), то алгоритм Е вьиюдпт х с вероятностью > -'. Время счета равно О(Й2"В) плюс время получения 2~В оценок С. 1 Сейчас мы готовы доказать, что последовательность смешанно-квадратнчного метода, заданная в 3.2.2-(17), является хорошим источником (псевдо)случайных чисел. Предположим, что 2л ' с Лу = РЯ < 2к, где Р и Π— простые числа вида 4Ь+3, удовлетворяющие неравенствам 2~к з17з С Р < 2~л 1пэ., 2луз с я < 2'и+О~э. Назовем Л/, состоящее из В двоичных разрядов, целым числом Блюма, поскольку на важность таких чисел для криптографии было впервые указано Мануэлем Блюмом (Манне! Б1шп, СОЛЗРСОХ 24 (Зрбпй, 1982), 133-137). Блюм первоначально предложил выбрать Р и О так, чтобы они оба имели В/2 двоичных разрядов, но алгоритм 4.5.40 показал, чта лучше выбрать Р и ф, как сформулировано здесь: чтобы Я вЂ” Р > .29 х 2л~з.
Выбрать Ло наугад среди чисел 0 < Хэ < ЛТ с Ла 1. М. Пусть также 2— случайная, состоящая из В двоичных разрядов, маска. Можно построить итеративный Акисточник Б, полагая Х множеством всех (х... т), которые возможны для (Хе, л, М) с дополнительным ограничением х ьз аз (по модулю т) для некоторых о. Легко показать, что функция д(х,г,т) = (хз шос) гп,х,т) — это перестановка Л' (см., например, упр. 4.5.4-35).
Функция /(х,х,т), извлекающая двоичные разряды в этом итеративном источнике, равна х шос) 2. Наше начальное значение (Хе, х, М) не является необходимым в Л; на д(Хе, л, М) имеет равномерное распределение в Х, так как точно четыРе значениЯ Хе имеют данный квадРат Хез пюо М. Теореме Р. Пусть Б — Х-нсточнггк, который определен смешанно-квадратичным методом согласно модулю, содержащему В двоичных разрядов, и предположим, что Б ие удовлетворяет некоторому статистическому крлгерпю А с допустимым отклонением с > 1/2~. Тогда можно построить алгоритм Г, который найдет множт тели состоящего пз В двоичных разрядов случайного целого числа Блюма М = Рс'./, имеющего внд, описанный выше, с вероятностью по крайней мере с/(4М) н временем счета Т(Г) = О(А'зВзс зТ(А) + ХэВсс э).
Доказательство. Ъ'множение по модулю М можно осуществить за О(Вз) шагов: следовательно, Т(/) + Т(д) = О(Вз). Поэтому лемма Р4 утверждает существование оценочного алгоритма С с успешной оценкой с/Х и Т(О) < Т(А) + О(/уВ ). Построить С по А ьюжно, используя метод нз упр.
41. Этот алгоритм О имеет такое свойство, чта э = Е((-1) 1э - "0+э*) > (-' + с/У) — (з — с//д) = 2с/Х, где среднее значение взято по всем (х,х,т) й Хи где (д,х,т) =д(х,х,т). Требуемый алгоритм Г получается следующим образом. Задано случайное число М = Рй с неизвестными Р и сг. Алгоритм вычисляет случайное число Хэ между 0 и М н немедленно останавливается с известным разложением, если ксб(Хе, ЛГ) ф 1. В других случаях применяется алгоритм 1 с О(г) = С(Хеэ пюс1 Л4, э, ЛХ) и Й = (15(1+ 2А'~В/сз)1. Если одно нз 2~ значений х на его выходе удовлетворяет хэ: — Лээ (по модулю М), существует 50:50 шансов, что х ф *Хе.
Тогда йсс)(Хе — х, М) и йсс)(Хе + х, ЛХ) являются простыми множителями М (см. "Яс)КТ-ящик" Рабина (Ва1нп) в разделе 4.5,4), Ясно, что время счета этого алгоритма равно О(ХэВ~с ~Т(А) + /дэВсс э), так как с > 2 ь. Вероятность, что алгоритм достигнет цели в разложении Л4, можно оценить следующим образом. Пусть и = (Х)/2л — чнею выборов (х,т) и пусть э,„, = 2 'л 2",( — 1)о~" "" 'э1+Я'* — суммирование по всем содержащим В двоичных разрядов чнглам х.
Тогда э = 2 ", э„„/и > 2с/Ас. Пусть с — число таких (х,т), чта э„„> с/Х Вероятность, что наш алгоритм оперирует подобиымн парами (х, т), равна — > ~~~ 18~~ >с/А) — = ~~~ (1 — [э~~ <с//У)) ™ и 2с Эяг» > — — ~ (э,„, < с/)у) — > —,. И в таком случае алгоритм по теореме 6 найдет х с вероятностью > т, поскольку мы имеем 2 > (2В/а~„,). Значит, он находит множитель с вероятностью > ~7.
1 Что дает теорема Р с практической точки зрения? Наше доказательство по. казывает, что константы, включенные в О, малы. Предположим, что время счета для разложения на множители равно самое большее 10(МзВзс еТ(А) + Мзде з). Многие известнейшие математики мира работали нвд проблемой разложения на множители больших чисел, в особенности после того, как в конце 70-х годов было показано, что разложение н» множители в высшей степени связано с криптографией. Так как они не могли найти хорошее решение, мы имеем основание считать, что разложение на множители является трудным делом.
Следовательно, теорема Р показывает, что Т(А) должно быть большим для всех алгоритмов, которые обнаруживают неслучайность двоичных разрядов, полученных смешанно-квадратичным методом. Длительные вычисления удобно измерять в М?Р-годах (зто число операций, выполняемых за год машпной, которая совершает миллион операций в секунду, т. е.
31,556,952,000,000 ж 3.16 х 10ш). В 1995 году время разложении на множители числа из 120 десятичных цифр (400 двоичных разрядов) при использовании в высшей степени совершенных алгоритмов было больше 250 М1Р-лет. Наиболее оптимистически настроенные исследователи, работающие над разложением на множители, могут удивиться, если алгоритм обнаружит, что требуется всего ехр(В~7~(?п В)зЧ) команд, когда В ~ оо. Только допустим, что зто количество может быть достигнуто для по крайней мере не слишком малых частей целых чисел Блюма М, состоящих из В двоичных разрядов. Тогда можно будет умножить много чисел, состоящих нз приблизительно 50 000 двоичных разрядов (15 000 цифр), за 2 х 10са М1Р-лет. Если генерировать Л = 1000 случайных двоичных разрядов смешанно-квадратичным методом с В = 50000 и если предположить, что все алгоритмы достаточно хороши, то умножение по крайней мере 75 — ' — на состоящие из 50 000 двоичных разрядов числа Блюма должно выполняться минимум 2 х 10ж М1Р-лет.
Из теоремы Р следует, что каждое такое множество из 1 000 двоичных разрядов проходит все статистические критерии на случайность, время счета Т(А) которых меньше 70 000 М1Р-лет: не существует алгоритма,4, который мог бы отличить такие двоичные разряды от истинно случайной последовательности с вероятностью > е =,ее. Впечатляет? Нет. Такой результат вряд ли является сюрпризом, так как необходимо точно определить около 150 000 истинно случайных двоичных разрядов, точно начинающихся в смещанио-квадратичном методе с Хе, Е и ЛХ, когда В = 50000. Конечно, можно получить 1 ООО случайных двоичных разрядов из такого вклада! Но вообще, формула Т(А) > ~г-аВ-з ехр(Вц'(?и В)з~') ~"Вз 1 100000 справедлива при наших умеренных предположениях, когда е = —, ХВз членов являются незначительными и когда В велико.
Положим, В = 200000 и Х = 10'е. Тогда смешанно-квадратичным методом получим десять миллиардов псевдослучайных двоичных разрядов из ЗВ ж 600000 истинно случайных двоичных разрядов, проходящих все статистические критерия, которые требуют меньше 7.486 х 10'е М1Р-лет, что равно 74.86 гигаМ?Р-годам. При Х = 10'з и В = 333333 время вычисления, необходимое для определения статистического смещения, возрастает до 53.5 тераМ1Р-лет, Простой псевдослучайный генератор 3.2.2-(16), который избегает случайной маски У, что также можно показать, прохцлнт все полиномнальные критерии случайности, если разложение на множители трудно осуществить (см.
упр. 4,5.4-43). Но известные преобразования гарантируют для методов, которые отчасти слабее смешанно-квадратичного метода. порядок роста О(!у4Вс " !о8(УВс ')) по сравнению с О(ХзВзс ~) теоремы Р. Каждый думает, что не существует алгоритма разложения на множители для чисел, состоящих из В двоичных разрядов, время счета которых равно полнному в степени В. Если это предположение верно в строгом виде, то нельзя будет получить даже 1/В" для целого числа Блюма, состоящего из В двоичных разрядов, за пониномиальное время для любого фиксированного Ь. Теорема Р доказывает, что смешанно-квадратичный метод генерирует псевдослучайные числа, проходящие все полиномиальные критерии случайности. Сформулнруелс это другим способом: если генерировать случайные двоичные разряды смешанно-квадратичным методом для подходящим образом выбранных Х и В, можно также получить числа, проходящие все разумные статпстическне критерии, или открыть новый алгоритм разложения на множители. О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
