Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
2 2
но выше. Тогда Ь = с (mod п). Если b = ±с (mod п), повторяем действия с начала, с другой совокупностью 5-чисел (или, что более эффективно, выбираем в матрице из E1 другое подмножество строк с нулевой суммой, находя, если необходимо, несколько большее количество 5-чисел и соответствующих им строк). Когда мы, наконец,
2 2
получим Ъ = с (mod ті) и Ь ф ±с (mod ті), вычисляем НОД (b + с, п), который и будет нетривиальным делителем п.
Эвристическая временная оценка. Мы дадим теперь очень грубый вывод оценки числа ,двоцчных операций, требующихся для факторизации очень большого п при применении описанного выше алгоритма. Мы воспользуемся несколькими упрощающими предположениями и приближенными соотношениями; в любом случае наш результат — лишь вероятностная оценка. Если нам очень не повезло при выборе 6j, алгоритм будет работать дольше.
Нам потребуются следующие факты.
Факті (формула Стирлинга). Приближенное значение log п\ есть пlogп — п.
Слово «приближенное» означает, что разность величин растет при п —> оо много медленнее, чем п. Это соотношение можно доказать, заметив, что log п! — сумма Римана для определенного интеграла J1"(log x)dx = п log п — п + 1, построенная по крайним правым точкам разбиения [1,п] на отрезки единичной длины.
Ф а к т 2. Если N — натуральное число и и > 0, то общее число таких iV-выборок (q1, а2,..., Qjv), состоящих из неотрицательных целых чисел, что X^j=I aj ^ ui Равно биномиальному коэффициенту
(ЫГ)-
§ 3. ФАКТОРИЗАЦИЯ ФЕРМА И ФАКТОРНЫЕ БАЗЫ
167
Здесь [и] обозначает функцию целой части (наибольшее целое число, не превосходящее и). Факт 2 можно доказать, если сопоставить каждой TV-выборке а некоторую iV-выборку ? из чисел 1, 2,..., N + [и] по правилам: ?i = O1 + 1 и ?j+l = ?j + aJ+1 + 1 для j ^ 1, т.е. мы выбираем числа ?j так, что между /3j_i и ?j имеется ctj чисел. Это дает взаимно однозначное соответствие между множеством А-выборок а с Oi I ¦•• + ?jv ^ ии множеством способов выбора N чисел из совокупности N + [и] чисел.
Основным этапом при оценке времени работы нашего алгоритма является оценка вероятности того, что случайное число, меньшее х, будет произведением простых чисел, меньших у (где у — число, значительно меньшее х). Прежде всего, обозначим через и дробь ]^|-|. Таким образом, если х есть r-разрядное целое число в двоичной записи, а у — s-разрядное целое число в двоичной записи, то и близко к отношению r/s.
По ходу оценок удобно делать некоторые упрощения, пренебрегая малыми членами. Для этого будем предполагать, что и значительно меньше у. Как обычно, мы обозначаем через к (у) количество простых чисел, не превосходящих у. Так как по теореме о простых числах я (у) приближенно равно у/ logy, мы предполагаем также, что и значительно меньше я (у). В типичном практическом применении алгоритма мы можем выбирать для х,у,и приблизительно такие по величине значения:
X ~ 10 ;
у и 106 (так что тг (у) « 7 • 104 и log у к 14); um 8.
Как обычно, пусть Ф(х,г/) обозначает число всех целых, не превосходящих х, которые не делятся ни на какие простые числа, большие у, т.е. число целых, которые можно записать в виде ]Jp"' ^ х, где произведение берется по всем простым, не превосходящим у, и ctj — неотрицательные целые числа. Существует очевидное взаимно однозначное соответствие между такими 7г(?/)-выборками неотрицательных целых чисел ctj, что YIj р"1 ^ х, и целыми числами, не превосходящими х, которые не делятся на простые числа, большие у. Логарифмируя, находим, что Ф(х,у) равно числу целочисленных
решений ctj неравенства YH1J=I aj ^0E, Pj ^ log ж. Заметим теперь, что большинство простых pj имеет логарифмы, не намного меньшие, чем logy. Действительно, большинство простых, меньших у, имеют почти то же число цифр, что и у; лишь относительно немногие имеют существенно меньшее число цифр и, следовательно, много меньший логарифм. Поэтому мы позволим себе в предыдущем неравенстве заменить logpj на log у. Поделив обе части получившегося неравенства
168
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
на logy и заменив logх/log у на и, мы можем сказать, что Ф(х,у) примерно равно числу решений неравенства Y^j=I aj ^ и-
Сделаем теперь еще одно важное упрощение: заменим число переменных 7г(у) на у. Это может, на первый взгляд, показаться довольно-таки опрометчивой модификацией нашей задачи. В самом деле, при замене 7г(у) на у появляются дополнительные ненулевые слагаемые; однако оказывается, что они сокращаются, и итоговый результат получается тем же самым, что при значительно более точной аппроксимации Ф(х,у). Таким образом, мы будем предполагать, что Ф(х,у) приближенно равно числу неотрицательных целочисленных решений неравенства =1 aj ^ и.
Используя факт 2 с N = у, мы получаем, что Ф(х, у) приближенно равно Оценим теперь величину log (Ф(х, у)/х) — логарифм вероятности того, что случайно взятое целое число между 1 и X представляется в виде произведения простых чисел, не превосходящих у. Заметим теперь, что logx = и logy по определению и, и применим полученное приближение для Ф(х, у) и факт 1:
