Для доказательства того, что алгоритм L хорошо работает, необходимо показать, что заданная строка х, вероятно, выводится всякий раз, когда она этого заслуживает. Сначала заметим, что, если заменить G на где G{z) = {G{z) + Zj) mod 2, начальное G{z) будет хорошим приближением х z mod 2 тогда и только тогда, когда новое G{z) будет хорошим приближением (х + ej) z mod 2, где ej - единичный вектор-строка, определенная на шаге L2. Кроме того, если применить алгоритм G вместо G, можно получить

/г.(Ь) = ( l)6c+G(cB+eO+(cB+e,).ej (-1) hi{{b + В j) mod 2) ,

где Bj - j-vi столбец В. Следовательно, на шаге L3 вьшодится вектор х{Ъ) - х{{Ь + Bj) mod 2) + Cj по модулю 2. Поскольку Ь пробегает все строки, состоящие из к двоичных разрядов, {Ь + Bj) mod 2 также пробегает эти строки, следствием чего является дополнение j-м двоичным разрядом каждого х на выходе.

Следовательно, достаточно доказать, что вектор х = О... О можно вывести, как только G{z) хорошо аппроксимирует постоянную функцию 0. В действительности мы покажем, что х{0... 0) равняется О... О на шаге L3 с большой вероятностью всякий раз, когда G{z) с большей вероятностью принимает значение О, чем 1, и к является достаточно большим. Точнее говоря, условие

J2(-l)OicB+e,) > О

выполняется для 1 < г < Л с вероятностью > , если s = Е(( -1)) положительно, где среднее берется по всем 2 возможным z и если к достаточно велико.

Ключом исследования является утверждение, что для каждого фиксированного с = ci...Ck ф О-.-О строка d = сВ равномерно распределена: каждое значение d появляется с вероятностью 1/2, так как двоичные разряды В случайны. Более того, когда с ф с = cj... с, строки d - cBwd - сВ независимы: каждое значение пары {d,d) происходит с вероятностью 1/2. Следовательно, можно рассуждать, как при доказательстве неравенства Чебышева: для любого фиксированного г сумма Хдо(~"-) отрицательна с вероятностью, не большей, чем 1/((2* - l)s-). (Подробности содержатся в упр. 42.) Поэтому В/{{2 - l)s) - верхняя грань вероятности того, что х{0) не является нулем на шаге L3.

Теорема G. Если s = Е((-1)*(+) > О и 2* > \2R/s\, то алгоритм L выводит X с вероятностью > . Время счета равно 0{k2R) плюс время получения 2*Л оценок G. I

Сейчас мы готовы доказать, что последовательность смешанно-квадратичного метода, заданная в 3.2.2-(17), является хорошим источником (псевдо)случайных чисел. Предположим, что 2~ < М = PQ < 2, где Р и Q - простые числа вида 4к + 3, удовлетворяющие неравенствам 2(-2)/2 < р < 2(-i)/2, 2/ <Q < 2(+/2 Назовем М, состоящее из R двоичных разрядов, целым числом Блюма, поскольку на важность таких чисел для криптографии было впервые указано Мануэлем Блю-Moi (Manuel Blum, COMPCON 24 (Spring, 1982), 133-137). Блюм первоначально предложил выбрать Р и Q так, чтобы они оба имели R/2 двоичных разрядов, но

алгоритм 4.5.4D показал, что лучше выбрать Р и Q, как сформулировано здесь: чтобы Q - Р > .29 X 2/2

Выбрать Хо наугад среди чисел О < Хо < М с Х"о J- М. Пусть также Z - случайная, состоящая из R двоичных разрядов, маска. Можно построить итеративный iV-источник 5, полагая X множеством всех (x,z,m), которые возможны для {Xo,Z,M) с дополнительным ограничением х = (по модулю т) для некоторых а. Легко показать, что функция g{x,z,m) = (х mod m, z, m) - это перестановка X (см., например, упр. 4.5.4-35). Функция f{x,z,m), извлекающая двоичные разряды в этом итеративном источнике, равна x-z mod 2. Наше начальное значение (Хо, Z, М) не является необходимым в X, но д{Хо, Z, М) имеет равномерное распределение в X, так как точно четыре значения Ао имеют данный квадрат Xq mod М.

Теорема Р. Пусть S - N-источник, который определен смешанно-квадратичным методом согласно модулю, содержащему R двоичных разрядов, и предположим, что S не удовлетворяет некоторому статистическому критерию А с допустимым отклонением е > 1/2. Тогда люжно построить алгоритм F, который найдет множители состоящего из R двоичных разрядов случайного целого числа Блюма М = PQ, имеющего вид, описанный выше, с вероятностью по крайней мере e/{4N) и временем счета T{F) = 0{NRe-T{A) + NR-).

Доказательство. Умножение по модулю М можно осуществить за 0{R) шагов; следовательно, Г(/) + Т{д) - 0{R). Поэтому лемма Р4 утверждает существование оценочного алгоритма G с успешной оценкой e/N и Т{0) < Т{А) -Ь 0{NR). Построить G по Л можно, используя метод из упр. 41. Этот алгоритм G имеет такое свойство, что S = E((-l)=(s-")+--) > (I + e/N) - ( - e/N) = 2e/N, где среднее значение взято по всем {х, z,m) £ X и где {у, z, т) = д{х, z, т).

Требуемый алгоритм F получается следующим образом. Задано случайное число М = PQ с неизвестными PuQ. Алгоритм вычисляет случайное число Ао между О и м и немедленно останавливается с известным разложением, если gcd(Xo, М) ф 1. В других случаях применяется алгоритм L с G{z) = G{XvsxodM,z,M) и к - "lg(l + 2NR/c)\. Если одно из 2* значений х на его выходе удовлетворяет = Xq (по модулю М), существует 50:50 шансов, что х ±Хо. Тогда gcd(Ao - х, М) и gcd(Xo + X, М) являются простыми множителями М (см. "SQRT-ящик" Рабина (Rabin) в разделе 4.5.4).

Ясно, что время счета этого алгоритма равно 0{NRe~T{A) + NR*e~), так как е > 2~. Вероятность, что алгоритм достигнет цели в разложении М, можно оценить следующим образом. Пусть п = А/2 - число выборов (х, т) и пусть Sxm - 2" Е(-1)*("+ - суммирование по всем содержащим R двоичных разрядов числам z. Тогда s = J2x тт/п > 2e/N. Пусть t - число таких {х,т),

что Sxrn

> e/N. Вероятность, что наш алгоритм оперирует подобными парами (х, т),

равна

а;,т х,т

>%-i:\m<e/Nf~>.

и в таком случае алгоритм по теореме G найдет х с вероятностью > \, поскольку мы имеем 2* > "2i?/s2]. Значит, он находит множитель с вероятностью > \.

Что дает теорема Р с практической точки зрения? Наше доказательство показывает, что константы, включенные в О, малы. Предположим, что время счета для разложения на множители равно самое большее \Q(NF?eT{A) + NR*e~). Многие известнейшие математики мира работали над проблемой разложения на множители больших чисел, в особенности после того, как в конце 70-х годов было показано, что разложение на множители в высшей степени связано с криптографией. Так как они не могли найти хорошее решение, мы имеем основание считать, что разложение на множители является трудным делом. Следовательно, теорема Р показывает, что Т{А) должно быть большим для всех алгоритмов, которые обнаруживают неслучайность двоичных разрядов, полученных смешанно-квадратичным методом.

Длительные вычисления удобно измерять в М1Р-годах (это число операций, выполняемых за год машиной, которая совершает миллион операций в секунду, т. е. 31,556,952,000,000 « 3.16 х 10). В 1995 году время разложения на множители числа из 120 десятичных цифр (400 двоичных разрядов) при использовании в высшей степени совершенных алгоритмов было больше 250 М1Р-лет. Наиболее оптимистически настроенные исследователи, работающие над разложением на множители, могут удивиться, если алгоритм обнаружит, что требуется всего ехр(Л/(1п Л)/*) команд, когда Л - 00. Только допустим, что это количество может быть достигнуто для по крайней мере не слишком малых частей целых чисел Блюма м, состоящих из Л двоичных разрядов. Тогда можно будет умножить много чисел, состоящих из приблизительно 50 ООО двоичных разрядов (15 ООО цифр), за 2 х 10 МХР-лет. Если генерировать N = 1000 случайных двоичных разрядов смешанно-квадратичным методом с Л = 50000 и если предположить, что все алгоритмы достаточно хороши, то умножение по крайней мере 5500 состоящиеиз 50 ООО двоичных разрядов числа Блюма должно выполняться минимум 2 х 10 МХР-лет. Из теоремы Р следует, что каждое такое множество из 1 ООО двоичных разрядов проходит все статистические критерии на случайность, время счета Т{А) которых меньше 70 ООО МХР-лет: не существует алгоритма А, который мог бы отличить такие двоичные разряды от истинно случайной последовательности с вероятностью > е = jg.

Впечатляет? Нет. Такой результат вряд ли является сюрпризом, так как необходимо точно определить около 150 ООО истинно случайных двоичных разрядов, точно начинающихся в смешанно-квадратичном методе с Xq, Z и м, когда Л = 50000. Конечно, можно получить 1 ООО случайных двоичных разрядов из такого вклада!

Но вообще, формула

- 1оЛ~й"ехр(Л(1пЛ)/) -ТУЛ

справедлива при наших умеренных предположениях, когда € = jqo членов

являются незначительными и когда R велико. Положим, Л = 200000 и N = 10°. Тогда смешанно-квадратичным методом получим десять миллиардов псевдослучайных двоичных разрядов из ЗЛ « 600000 истинно случайных двоичных разрядов, проходящих все статистические критерии, которые требуют меньше 7.486 х 10° МХР-лет, что равно 74.86 гигаМ1Р-годам. При N = 10 и Л = 333333 время