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

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

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 96 97 98 99 100 101 < 102 > 103 104 105 106 107 108 .. 125 >> Следующая


НЄ только «ВероЯТНО ПРОСТЫМ»), ТО ЖЄ Самое Справедливо для <7t_2 и

далее, до qi = q, и, наконец, получаем, что само п — действительно простое. Этим описание критерия простоты, использующего эллиптические кривые, завершено.

С данным критерием связаны две трудности, одна — практическая, а другая — теоретическая. Во-первых, хотя алгоритм Шуфа и работает полиномиальное время от logn, для практических применений он очень сложен. В последнее время были достигнуты некоторые успехи в его разработке и упрощении, но все равно приходится подсчитывать число точек на большом количестве кривых E, пока мы не найдем, наконец, кривую, у которой т имеет нужный нам вид — т = kq. Чтобы справиться с этой проблемой, Эткин (А. О. L. Atkin) разработал вариант критерия простоты, использующего эллиптические кривые, с тщательным подбором эллиптических кривых с комплексным умножением, для которых значительно легче находить число точек в их редукциях по модулю п. Более подробно о методе Эткина см. статью Ленстры и Ленстры из приведенного ниже списка литературы.

Вторая трудность — теоретическая. Чтобы найти эллиптическую кривую E над Fn (предполагая, что п — простое), у которой число точек — «почти простое» (т. е. имеет вид т = qk для малого к и простого q), мы должны знать кое-что о распределении простых чисел (вернее, «почти простых») в интервале р + 1 — 2^фр,р + 1 + 2^/р, где по теореме Хассе находится число т. Пока что не доказаны теоремы, гарантирующие, что в результате полиномиально зависящего от logn числа попыток с высокой вероятностью будет обнаружена кривая Е, число точек которой имеет указанный вид и лежит в интервале столь (относительно) малой длины. Однако существует весьма правдоподобная гипотеза, которая могла бы это гарантировать, чего вполне достаточно для практических целей. Построение доказуемо полиномиального вероятностного алгоритма значительно сложнее: такой критерий простоты, разработанный Адлеманом (L. Adleman) и Хуа-

216

ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ

ном (M.Huang), использует двумерные абелевы многообразия, представляющие собой обобщение эллиптических кривых на размерность' 2. Однако этот алгоритм очень громоздок и совершенно неприменим на практике.

УПРАЖНЕНИЯ

1. а) Пусть в критерии простоты Поклингтона п — простое число, га — 1 делится на простое число q, как в предложении VI. 3. 1, и а выбирается случайно в (Z/raZ)*. Какова вероятность того, что а будет удовлетворять условиям этого предложения?

б) Пусть в критерии простоты, использующем эллиптические кривые, га — простое число, имеется эллиптическая кривая, порядок которой делится на простое число q, как в предложении VI. 3.2, и P — случайно выбранная точка на ней. Какова вероятность того, что P будет удовлетворять условиям этого предложения?

2. Обобщить критерий простоты Поклингтона на случай, когда известен делитель s числа га — 1, больший у/п — 1, и известны все его простые делители q. Условие 2) должно выполняться для всех q\s.

3. а) (Критерий простоты Пепина (Pepin) для чисел Ферма). Доказать, что число Ферма га = 2 4-1 простое тогда и только тогда, когда существует такое

2*- 1

целое число а, что а2 = —1 (mod га). Доказать, что если га — простое, то 50% из всех о Є (Z/raZ)* обладают этим свойством. Доказать также, что если к > 1, то в качестве а всегда можно выбрать одно из чисел 3, 5, 7.

б) Доказать, что число Мерсенна га = 2Р — 1 является простым в том и только том случае, когда на кривой Е: у2 = z34-z (mod га) найдется такая точка P = (х, у), что 1) при вычислении 2P_1 P не возникают необратимые по модулю п знаменатели и 2) !/-координата точки 2Р~1Р равна нулю. Для этого покажите, во-первых, что если га = 2Р — 1 является простым, то группа точек на E (mod га) — циклическая порядка 2Р и 50% всех P Є E (mod га) имеют отмеченные выше свойства 1)-2). Объясните, как можно порождать случайные точки E (mod га). Вы можете пользоваться любым алгоритмом, который предполагает, что б"-1 = 1 (mod га) (т. е. что га — псевдопростое по различным основаниям 6), так как, если вы когда-либо столкнетесь с Ь, для которого это сравнение не выполняется, то ваш критерий прекратит работу, выдав заключение, что га — составное число.

Заметим, что этот критерий простоты — вероятностный в том смысле, что если га — простое число, то нет никаких гарантий относительно времени, за которое нужная нам точка P обнаружится. Но, как только такая точка P найдена, критерий заключает, что га — простое число. В этом отношении он отличается от критериев псевдопростоты из § V. 1. Обобщенную процедуру проверки на простоту любого нечетного га можно найти в работе Босма (W. Bosma) из приведенного ниже списка литературы.

ЛИТЕРАТУРА к § 3 ГЛАВЫ VI

1. Adleman L., Huang М. Recognizing primes in random polynomial time. — In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, p. 462-469.

§ 4. РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ

217

2. Bosma W. Primality testing using elliptic curves. — Report 85-12. Amsterdam: Mathematisch Instituut, Universiteit van Amsterdam, 1985.
Предыдущая << 1 .. 96 97 98 99 100 101 < 102 > 103 104 105 106 107 108 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed