Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
НЄ только «ВероЯТНО ПРОСТЫМ»), ТО ЖЄ Самое Справедливо для <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.