Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 81

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 75 76 77 78 79 80 < 81 > 82 83 84 85 86 87 .. 125 >> Следующая


, /Ф(х,у)\ , f([u} + y)\\

% ([и] + у) log([u] + у) - ([и] + у)-

- ([и] log [и] - [и]) - (ylogy -у) - и logy.

Сделаем еще несколько приближений. Во-первых, заменим [и] на и. Затем, учитывая, что и значительно меньше у (в силу нашего предположения), заменим log (у + и) на logy. После сокращения получим:

log-- ~ -ulogu,

т. е.

V(x,у)

— и

и

Отсюда, например, следует, что если х 1048 и у « 106 (как выше), то вероятность того, что случайно выбранное целое число между 1 и X есть произведение простых чисел, не превосходящих у, равна примерно 1/88.

Теперь мы можем оценить число двоичных операций, используемых описанным выше алгоритмом факторных баз. Для простоты будем предполагать, что наша факторная база В состоит из первых h = тг(у) простых чисел, т.е. из всех простых, не превосходящих у. Для упрощения анализа мы будем также предполагать, что —1 не

§ 3. ФАКТОРИЗАЦИЯ ФЕРМА И ФАКТОРНЫЕ БАЗЫ

169

включается в В и что мы рассматриваем наименьшие положительные вычеты (а не наименьшие абсолютные вычеты) Ь\ (mod п).

Итак, мы оцениваем число двоичных операций, требующихся для выполнения следующих шагов.

Шаг 1. Выбираем случайно числа Ь{ в интервале от 1 до п; на-ходим наименьший неотрицательный вычет &г (mod п) и выражаем его, если это возможно, в виде произведения простых чисел, не превосходящих у; останавливаемся тогда, когда удается набрать 7г(у)+ 1 различных Ьг, для которых Ьг (mod п) записываются как такие произведения.

Ш а г 2. Находим множество из линейно зависимых строк в соответствующей (0,1)-матрице размера (к(у) + 1) Хтт(у), чтобы получить

2 2

сравнение вида Ь = с (mod п).

Ш а г 3. Если b = ±с (mod п), то повторяем шаги 1 и 2 с но-

2 2

выми Ьг до тех пор, пока не получим сравнение Ь = с (mod п) с Ь ф ±с (mod п). Тогда находим нетривиальный множитель п, вычисляя НОД (b + с,п).

Если предполагать, что b\ (mod п) (понимаемые как наименьшие неотрицательные вычеты по модулю п) распределены равномерно между 1 и л, то в соответствии с приведенными выше соображениями нам придется выбрать порядка ии (где и = logп/ logy) чисел до появления такого bi, что b\ (mod п) есть произведение простых чисел, не превосходящих у. Мы решим позднее, как выбрать у, чтобы минимизировать время ожидания. Суть дела заключается в том, что, выбирая у большим, мы делаем ии малым и поэтому будем часто встречать bi, для которых bi (mod п) — произведение простых, не превосходящих у. Однако в этом случае разложение &j (mod п) в произведение таких простых (для чего нам придется проводить тг(у) + 1 делений) и последующее обнуление строк матрицы становятся слишком трудоемкими операциями. С другой стороны, если выбрать у очень малым, то последние задачи станут легче, однако придется слишком долго ждать появления такого bi, что о; (mod п) разлагается в произведение простых чисел, не превосходящих у, так как в этом случае ии станет очень большим. Следовательно, у нужно выбирать в некоторой промежуточной области, чтобы избежать этих крайностей.

Чтобы решить вопрос о выборе у, мы сначала получим грубую оценку числа двоичных операций в терминах у (и, конечно, п). Затем мы минимизируем ее по у (используя элементарные вычисления и некоторые упрощающие приближения) и найдем временную оценку для того у, который дает минимальное время работы.

Предположим, что п — r-разрядное, а у — 5-разрядное числа;

170

ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ

тогда и весьма близко к r/s. Прежде всего, сколько нужно двоичных операций для каждой проверки случайно выбранного &*? Мы утверждаем, что это число операций полиномиально по г и у, т.е. что оно есть 0(rllks) для некоторых (довольно малых) целых чисел к и /. Для порождения случайного бита требуется некоторое фиксированное время и, таким образом, нужно 0(т) двоичных операций, чтобы породить случайное целое число между 1 и п. Далее, вычисление 6; (mod п) тре-бует 0(r ) двоичных операций. Затем нам придется последовательно делить bi (mod п) на все простые числа, не превосходящие у, на которые оно делится без остатка (или на степени таких простых), надеясь после всех делений получить 1. Простой способ проделать это (хоть и не самый эффективный) — делить на два и затем на все нечетные простые р от 3 до 2/, записывая по ходу дела, на какую степень р происходит деление без остатка. Заметим, что если р — не простое, то оно не делит без остатка, так как его простые сомножители были уже удалены из bi (mod п). Так как деление r-разрядного целого числа на 5-разрядное целое число в двоичной системе счисления проводится за время O(rs), то каждая проверка случайно выбранного bi требует O(rsy) двоичных операций.

При выполнении шага 1 придется проверить приблизительно ии(ж(у) + 1) значений 6,-, чтобы найти 7r(y) + 1 таких значений bi, что bi (mod п) представляется в виде произведения простых, не превосходящих у. Так как тт(у) « = Q{y/s), то на шаг 1 затрачивается

0(иигу2) двоичных операций.

Шаг 2 включает в себя операции со сложностью, полиномиальной по у и г (такие, как преобразования матриц и нахождение b и с по модулю п). Таким образом, шаг 2 выполняется за 0(y\h) двоичных операций для некоторых целых j и h. При каждом выполнении шагов 1-2 вероятность успеха, т.е. нахождения b ф ±с (mod п), не меньше 50%. Точнее, вероятность успеха равна 50%, если п делится в точности на два разных простых числа, и больше, если п имеет более двух простых делителей. Поэтому, если нас устраивает, скажем, ве-роятность 1-2 нахождения нетривиального делителя п, то шаги 1-2 нам достаточно пройти 50 раз. Принимая эту величину достаточной для практических целей, при подходящих целых к и h получаем окончательную оценку
Предыдущая << 1 .. 75 76 77 78 79 80 < 81 > 82 83 84 85 86 87 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed