Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
bdf(-a/b) - (-a)d-\-ad_l(-a)d 1b + ad_2(-a)d~2b2 -\-----axabd 1 +a0bd
— гладкие относительно данной факторной базы (т. е. делятся лишь на простые числа, принадлежащие факторной базе). Подробности того, как это делается и как это приводит к факторизации п, можно найти в книге [3] из списка литературы к данному параграфу. Чтобы процедура была успешной, нужно, чтобы доля гладких чисел среди значений многочлена / была приблизительно такой же, как доля гладких чисел среди всех чисел той же длины. Хотя это выглядит правдоподобно и выполняется во всех примерах, которые были просчитаны, тем не менее, утверждение выглядит чрезвычайно трудным для доказательства. Поскольку оценка времени работы алгоритма основана на этом недоказанном предположении, она является эвристической. Хотя это обстоятельство не очень существенно для практической факторизации чисел, оно указывает на некоторые важные нерешенные задачи теоретического анализа асимптотической сложности факторизации.
Автор хотел бы поблагодарить Дж. Булера (Joe Buhler), предоставившего для настоящей книги это краткое описание решета над числовым полем.
УПРАЖНЕНИЯ
1. В приведенном примере найти все отношения линейной зависимости по модулю 2 между строками матрицы и показать, что если P = 50 и A ^ 499, то получить нетривиальную факторизацию 1042387 этим методом невозможно.
2. Пусть п —> оо. Предположим, что P и А всегда выбираются величинами одинакового порядка (например, что с\ ^ (log yl)/(log P) ^ С2 для некоторых положительных констант Ci и с?). Какой из шагов 1-7 изложенной выше версии метода квадратичного решета является асимптотически наиболее трудоемким? Дать в терминах О-большого оценку числа двоичных операций на этом шаге.
§ 5. МЕТОД КВАДРАТИЧНОГО РЕШЕТА
187
3. Использовать метод этого параграфа с P = 50 и А = 500, чтобы разложить на множители: а) 1046603; б) 1059691; в) 998771.
ЛИТЕРАТУРА к § 5 ГЛАВЫ V
1. Сагоп Т., Silverman R. Parallel implementation of the quadratic sieve. — J. Supercomputing, 1988, v. 1, p. 273-290.
2. Gerver J. L. Factoring large numbers with a quadratic sieve. — Math. Сотр., 1983, v. 41, p. 287-294.
3. The Development of the Number Field Sieve./ Ed. by A. Lenstra, H. W. Lenstra, Jr.. Berlin-Heidelberg etc.: Springer, 1993.
4. Lenstra H. W., Jr., Pomerance C. A rigorous time bound for factoring integers. — J. Amer. Math. Soc, 1992, v. 5, p. 483-516.
5. Pomerance C. Analysis and comparison of some integer factoring algorithms. — In: Computational Methods in Number Theory./ Ed. by H. W. Lenstra, Jr., R. Tijde-man. Amsterdam: Mathematisch Centrum, 1982, p. 89-139.
6. Pomerance C. Factoring. — Crypt. Comput. Number Theory, Proc. Symp. Appl. Math., 1990, v. 42, p. 27-47.
ГЛАВА VI
ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
В последнее время одна из областей теории чисел и алгебраической геометрии — эллиптические кривые (точнее, теория эллиптических кривых над конечными полями) — нашла применение в криптографии. Основная причина этого состоит в том, что эллиптические кривые над конечными полями доставляют неисчерпаемый источник конечных абелевых групп, которые (даже если они велики) удобны для вычислений и обладают богатой структурой. Ранее (в § IV. 3) мы работали с мультипликативными группами полей. Во многих отношениях эллиптические кривые — естественный аналог этих групп, но более удобный, так как существует большая свобода в выборе эллиптической кривой, чем в выборе конечного ПОЛЯ.
Начнем с изложения основных определений и свойств эллиптических кривых. Мы ограничимся минимальным числом основных фактов, необходимых для понимания приложений к криптографии (см. §§2-4), уделяя больше внимания примерам и конкретным описаниям и меньше заботясь о доказательствах и общности. Более систематическое изложение этого предмета можно найти по ссылкам в кон-
B этом параграфе мы предполагаем, что К — поле: либо поле R вещественных чисел, либо поле Q рациональных чисел, либо поле С комплексных чисел, либо поле F9 из q = рг элементов.
Определение. Пусть К — поле характеристики, отличной от 2, 3, и X3+ax-j-b (где а, Ь Є К) — кубический многочлен без кратных корней. Эллиптическая кривая над К — это множество точек (х,у), х,у Є К, удовлетворяющих уравнению
це § 1.
§ 1. Основные факты
у = X + ах + о,
(1)
§ 1. ОСНОВНЫЕ ФАКТЫ
189
вместе с единственным элементом, обозначаемым О и называемым «точка в бесконечности» (о ней подробнее будет сказано ниже).
Если- К — поле характеристики 2, то эллиптическая кривая над К — это множество точек, удовлетворяющих уравнению либо типа
у2 4 су = х3 4 ах 4 Ь, (2а)
либо типа
у2 4. ху = X3 4 ах2 -f b (26)
(здесь кубические многочлены в правых частях могут иметь кратные корни), вместе с «точкой в бесконечности» О.
Если К — поле характеристики 3, то эллиптическая кривая над К — это множество точек, удовлетворяющих уравнению
у2 = X3 + ах2 4 Ьх + с (3)
(где кубический многочлен справа не имеет кратных корней), вместе с «точкой в бесконечности» О.
