AOP_Tom2 (1021737), страница 53
Текст из файла (страница 53)
Для этого существует только тонкий общий способ— Е(( 1)с)сь..сл]-~с,с,~-" еслссу ) с (40) где усреднение берется по всем возможным значениям в1... хя. Это сумма правильных оценок минус неправильные оценки деленная на 2; так, если р — вероятность я. того, что О правильно, то получим в = р — (1 — р) или р = -' + з в. Например, предположим, что й = 4 и С(зсвзвзхс) = [хз Ф хз][хз + х4 < 2] фУнкция дает хорошую оценку в = з (и р = -"), если х = 1100, твк как она равна х зшо82 = (зс + вз) шоб2 для всех строк х, содержащих 4 двоичных разряда, исключая 0111 или 1011. Она также дает хорошую оценку „-', когда х = 0000, 0011, 1101 или 1110, так что существует пять вероятных возможностей для х.
Остальные одиннадцать хв дают в < О. Следующий алгоритм магически находит х в большинстве случаев, когда С успешна оценивает в только что описанном смысле. Точнее, алгоритм строит короткий перечень элементов, имеющих хорошую иозможность содержать х. Алгоритм 1 (Усиление линейных оценок). Пусть задана бинарнозначная функция С(хс ...
зп) и положительное целое число 1ь Этот алгоритм дает таблицу 2" двоичных последовательностей х = х,... хя с таким свойством, что'х, вероятно, находится в этой таблице, когда С(хс... хя) является хорошим приближением функции (хз хс + .. + хявя) шос( 2.
11. [Построение случайной матрицы.1 Генерировать случайные двоичные разряды ВО для 1 < 1 < Й и 1 < з < Д. Е2. [Подсчет знаков.] Для 1 < с < В и для всех двоичных разрядов строк Ь = Ьз... Ьь вычислить с (6) ~~; ( 1)з с.~-а)сп.~.с,) сФО (41) где е, — строка, содержащая В двоичных разрядов, 0... 010... О с 1 на позиции с и где с — строка 4... с(я с Иу = (Всусс+ + Вв,св) шос( 2. (Другими словами, двоичный вектор сс... св является кратным двоичной матрице В размера 6х Л.) Сумма взята по всем 2" — 1 строкам двоичных разрядов, сы ..
св ф 0... О. Для каждого 1 можно оценить )зз(6) )с. 2в сложениями и вычитаниями с помощью метода Ятеса (Уазев) для преобразования Уолша (см. замечание к равенству 4.б.4 — (38)). 1,3. [Вывод оценок.] ДлЯ всех 2ь выбоРов Ь = Ьз... Ьз вывод стРоки х(Ь) = [Ьс (Ь) < О] ... [Ья(6) < О]. использовать свойства булевых функций, если расширить 5 так, что появится потребность прцближенно оценивать множество различных функций у(х). (Однако метод является несколько техническим. Так, при первом чтении следует, возможно, перейти к теореме О, прежде чем внимательно рассматривать следующие ниже детали.) Предположим, С(хы ., зя) — бинарнозначная функция (принимающая значения 0 или 1) на строках из й двоичных разрядов, которая хорошо приближает функцию вида ) (вы ..
зя) = (хсх1 + . + хяхя) шод 2 для некоторого фиксированного х = хз... хя. Удобно измерять, насколько зто приближение успешно, вычисляя среднее значение Для доказательства того, что алгоритм Е хорошо работает, необходимо показать, что заданная строка х, вероятно, выводится всякий раз, когда она этого заслуживает, Сначала заметим, что, если заменить С на О', где О'(л) = (С(г) + лу) шой 2, начальное О(л) будет хорошим приближением х л шоО1 2 тогда и только тогда, когда новое С'(в) будет хорошим приближением (х + е,) г шос1 2, где е,— единичный вектор-строка, определенная на шаге 12. Кроме того, если применить алгоритм С' вместо С, можно получить ('(Ь) = ~~( — Цэс+Гдсв+е )+1сн+с ) с = ( — 1)~сй;((Ь+ В,) шос1 2) сГО где Вз — у-й столбец В. Следовательно, на шаге 1Д выводится вектор х'(Ь) х((Ь+ В,) пюй 2) +еу по модулю 2.
Поскольку Ь пробегает все строки, состоящие из Ь двоичных разрядов, (Ь+ В.) шос1 2 также пробегает эти строки, следствием чего является дополнение чм двоичным разрядом каждого х на выходе. Следовательно, достаточно доказать, что вектор х = 0... 0 можно вывести, как только л'(л) хорошо аппроксимирует постоянную функцию О. В действительности мы покажем, что х(0...0) равняется О...0 на шаге ЕЗ с болыпой вероятностью всякий раз, когда О(в) с большей вероятностью принимает значение О, чем 1, и Ь является достаточно большим.
Точнее говоря, условие 1)СЦсВтс,) > О сссэ выполняется для 1 < л < Л с вероятностью > —,', если э = Е(( — 1)обю) положительно, где среднее берется по всем 2В возможным а и если Ь достаточно велико. Ключом исследования является утверждение, что для каждого фиксированного с = сы .. сл ф О... 0 строка а' = сВ равномерно распределена: каждое значение Н появляется с вероятностью 1/2Я, так как двоичные разряды В случайны.
Более того, когда с ~ с' = гм .. с'„, строки И.= сВ н ьи = с'В неэаеисимвс каждое значение пары (с1., И') происходит с вероятностью 1/2эн. Следовательно, можно рассуждать, как при доказательстве неравенства Чебышева: для любого фиксированного л сумма ~,гя( — 1)~~'Вс'~ отрицательна с вероятностью, не большей, чем 1/((2л — 1)ээ).
(Подробности содержатся в упр. 42.) Поэтому Л/((2" — 1)ээ) — верхняя грань вероятности того, что х(0) не является нулем иа шаге ЕЗ. Теорема С. Егля э = Е((-1)о~цч' с) > 0 я 2" > (2Л/яэ), го алгоритм Б выводит х с вероятностью > -'. Время счета равно О(lс2ОЛ) плюс врелля получения 2лЛ оценок С. Сейчас мы готовы доказать, что последовательность смешанно-квадратичного лсетода, заданная в 3.2.2 — (17), является хорошим источником (псевдо)случайных чисел. Предположим, что 2Я " < ХХ = РО < 2н, где Р и л1 — простые числа вида 4»+3, удовлетворяющие неравенствам 2~н эиэ < Р < 2~я лил, 2В7э < Я < 2~ясц7".
Назовем ЛХ, состоящее из Л двоичных разрядов, целым числом Блюма, поскольку на, важность таких чисел для криптографии было впервые указано Мануэлем Блюмом (Манне! В1шп, СОМРСОХ 24 (Брппк, 1982), 133-137). Блюм первоначально предложил выбрать Р и О так, чтобы они оба имели Л/2 двоичных разрядов, но алгоритм 4.5.4В показал, что лучше выбрать Р и 1Х, как сформулировано здесьс чтобы Я вЂ” Р > .29 х 2и~з.
Выбрать Хо наугад среди чисел 0 < Ло < М с Ло з М. Пусть также Х— случайная, состоящая из Й двоичных разрядов, маска. Можно построить итеративный Х-источник Б, полагая Х множеством всех (х,х,т), которые возможны для (Ло, х', М) с дополнительным ограничением х ив а аз (по модулю т) для некоторых а.
Легко показать, что функция д(х,х,т) = (х шос1т,х,т) — - это перестановка Х (см., например, упр. 4.54-35). Функция /(х,х,т), извлекающая двоичные разряды в этом итеративном источнике, равна х х шоо 2, Наше начальное значение (Хо, Х. М) не является необходимым в Х, но д(Хо, л, ЛХ) имеет равномерное распределение в Х, так как точно четыре значения Хо имеют данный квадрат Ход шод М. Теорема Р.
Пусть о — гз'-источник, который определен смешанно-квадратичным методом согласно модулю, содержащему Й двопчных разрядов, и предположим, что Б не удовлетворяет некоторому статистическому критерию А с допустимым отклонением е > 1/2~. Тогда можно построить алгоритм Р, который найдет множители состоящего из Й двоичных разрядов случайного целого числа Блюма М = РЯ, имеющего впд, описанный выше, с вероятностью по крайней мере с/(4Ф) и временем счета Т(Р) = 0(Л"ойзе оТ(А) + Л'эйое з), Докаэагпельстиоо. Умножение по модулю М можно осуществить за 0(Й~) шагов: следовательно, Т(/) + Т(д) = 0(Йз). Поэтому лемма Р4 утверждает существование оценочного алгоритма С с успешной оценкой г/ь' и Т(С) < Т(А) + 0(1г'Йз).
Построить С по А можно, используя метод из упр. 41. Этот алгоритм С имеет такое свойство, что э = Е[( — 1)~!ж" 1+.'*) > (-' + е/Х) — (-' — е/Г~") = 2с/Х, где среднее значение взято по всем (х,х,т) б Хи где (д, х, ои) = д(х,х, т). Требуемый алгоритм Р получается следующим образом. Задано случайное число М = Р1З с неизвестными Р и Я. Алгоритм вычисляет случайное число Ло между 0 и ЛХ и немедленно останавливается с известным разложением, если бед(Хо.
М) ~ 1. В других случаях применяется алгоритм 1, с С(г) = С(Хоз шва ЛХ,х,ЛХ) и й = [!к(1+2Лгзй/ез)). Если одно из 2ь значений х на его выходе УдовлетвоРЯет хо= :Хоз (по модулю ЛХ), существует 50:50 шансов, что х ф хХо. Тогда йсй(Хо — х, М) и бей(Хо + х, М) ЯвлЯютсЯ пРостыми множителЯми М (см. "512ЙТ-Ящики Рабина (ЙаЫп) в разделе 4.5.4). Ясно, что время счета этого алгоритма равно 0(М'Йзе оТ(А) + Л'эй4е о), так как е > 2 "~. Вероятность, что алгоритм достигнет цели в разложении ЛХ, можно оценить следующим образом.
Пусть и = [Х[/2п — число выборов (х,т) и пусть а,„, = 2 2 ( — 1)~!" = "О"='* —. суммирование по всем содержащим Й двоичных разрядов числам ж Тогда э = 2 э,„,/и > 2е/ЛО Пусть 1 — число таких (х.ги), что ои > е/Х. Вероятность, что наш алгоритм оперирует подобными парами (х, т), равна > Х, [ах~и > С/Л) — Х~' (! [Эвы < Е/"' !) п и и и,ы иол 2е эхы > ~ [атп1 < с/М) — * > И в таком случае алгоритм по теореме С найдет х с вероятностью > з, поскольку мы имеем 2 > (271/а~~„,). Значит, он находит множитель с вероятностью > ~1. 1 Что дает теорема Р с практической точки зрения? Наше доказательство показывает, что константы, включенные в О, малы. Предположим, что время счета для разложения на множители равно самое большее 10(Мз)1зе зТ(А) + Хай~с з).
Многие известнейшие математики мира работали над проблемой разложения на множители больших чисел, в особенности после того, как в конце 70-х годов было показано, что разложение на множители в высшей степени связано с криптографией. Так как они не могли найти хорошее решение, мы имеем основание считать, что разложение на множители является трудным делом. Следовательно, теорема Р показывает, что Т(А) должно быть большим для всех алгоритмов, которые обнаруживают неслучайность двоичных разрядов, полученных смешанно-квадратичным методом. Длительные вычисления удобно измерять в М1Р-годах (это число операций, выполняемых за год машиной, которая совершает миллион операций в секунду, т, е. 31,556,952,000,000 3,16 х 10'з). В 1995 году время разложения на множители числа из 120 десятичных цифр (400 двоичных разрядов) при использовании в высшей степени совершенных алгоритмов было больше 250 М1Р-лет. Наиболее оптимистически настроенные исследователи, работающие над разложением на множители, могут удивиться, если алгоритм обнаружит, что требуется всего ехр(В'7~(1п А) ~74) команд, когда В -+ оо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
