Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
фициенты. Этот степенной ряд называется дзета-функцией эллиптической кривой (над F9) и представляет собой весьма важный объект, связанный с Е.
«Еипотеза Вейля» (ныне теорема Делиня (P. Deligne)) в значительно более общем контексте (алгебраические многообразия произвольной размерности) утверждает, что дзета-функция имеет весьма специальный вид. В случае эллиптической кривой E/Fq Вейль (А. Weil) доказал следующее утверждение.
Гипотеза (теорема) Вейля для эллиптической кривой. Дзета-функция есть рациональная функция от T вида
где от эллиптической кривой E зависит лишь целое число а. Значение а связано с числом N = Ni соотношением N = q + I - а. Кроме того, дискриминант квадратного трехчлена в числителе отрицателен (т. е. а2 < Aq — теорема Хассе), таким образом, этот трехчлен имеет два комплексно сопряженных корня а и ?, оба по модулю равные ^Jq (точнее, корнями являются 1/а и l/?, а a,? — корни «возвратного» уравнения).
Доказательство см. в § V. 2 упомянутой выше книги Сил-вермена.
Замечание. Если записать числитель (8) в виде (1 — CtT)(I — ?T) и затем взять производную от логарифмов обеих частей (заменяя
S 1. ОСНОВНЫЕ ФАКТЫ
199
левую часть по формуле (7), определяющей дзета-функцию), то нетрудно убедиться, что формула (8) эквивалентна последовательности соотношений
Nr = q + 1 -ar -?r, г = 1,2,...
Так как а и ?, наряду с а, определяются значением N = N1, то число точек над F9 однозначно определяет число точек над любым его расширением. Таким образом, теорему Вейля для эллиптических кривых можно использовать, в частности, для нахождения числа точек над расширениями высокой степени.
Пример 5. Легко вычисляется дзета-функция эллиптической
2 3
кривой у + у = X над F2, так как имеется всего три F2-to4kh. Она равна (1 + 2Г )/((1 - T)(I - 2T)). Таким образом, обратные корни числителя — это ±г\/2. Отсюда следует формула
J 2r + 1, если г нечетно,
Г= 12г + 1-2(-2)г/2, если г четно. (9)
В заключение этого параграфа заметим, что существует много аналогий между группой Fg-точек на эллиптической кривой и мультипликативной группой F*. Например, по теореме Хассе они имеют примерно одинаковое число элементов. Однако абелевы группы, которые строятся по эллиптическим кривым, имеют одно значительное преимущество, которое объясняет их ценность для криптографии: для одного и того же (большого) q существует богатый выбор различных эллиптических кривых с разными значениями N. Эллиптические кривые составляют богатый источник «естественно возникающих» конечных абелевых групп. Мы воспользуемся этой возможностью в последующих трех параграфах.
УПРАЖНЕНИЯ
1. Пусть E — эллиптическая кривая, определенная над С, уравнение (1) которой имеет коэффициенты а, 6 Є R; тогда точки E с вещественными координатами образуют подгруппу. Описать все возможные виды структуры такой подгруппы комплексной кривой E (которая как группа изоморфна произведению окружности на себя). Приведите пример для каждой из них.
2. Сколько точек P порядка п (т.е. таких, что пР = О) имеется на эллиптической кривой над С? Сколько таких точек на эллиптической кривой над R?
3. Привести пример эллиптической кривой над R, имеющей в точности 2 точки порядка 2, и пример кривой, имеющей в точности 4 точки порядка 2.
4. Пусть P — точка на эллиптической кривой над R. Предположим, что P не есть точка в бесконечности. Найти геометрическое условие, эквивалентное тому, что P — точка порядка а) 2; б) 3; в) 4.
200
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
5. Каждая из следующих точек имеет конечный порядок на данной эллиптической кривой над Q. Найти в каждом случае порядок Р.
а) P = (0, 16) на у2 = х3 + 256.
б) P = (I1I) на у2= X* +Lx.
в) P = (3, 8) на у2 = X3 - 43i + 166.
г) P = (0,0) на у2+у = X3 —X2 (уравнение можно привести к виду (1) заменой переменных у —* у — I,i—* X + |).
6. Вывести формулы сложения, аналогичные (4)-(5), для эллиптических кривых над полем характеристики 2, 3 (см. уравнения (2)-(3)).
7. Доказать, что число Fq-точек на каждой из следующих эллиптических кривых равно 9+1:
а) у2 = X3 — X, когда q = 3 (mod 4);
б) у2 = X3 — 1, когда q = 2 (mod 3) (q нечетно);
c) У2 + У — 23i когда g = 2 (mod 3) (здесь q может быть четным).
8. Для всех степеней нечетных простых чисел q = рт до 27 включительно найти порядок и тип группы F?-T04eK на эллиптических кривых у2 = х3 — х и у2 = X3 — 1 (в последнем случае — при р ф 3). В некоторых случаях вам нужно будет проверить, сколько точек имеют порядок 3 или 4.
9. Пусть q = 2Г и пусть эллиптическая кривая E над F, имеет уравнение у2 +у = X3.
а) Выразить координаты — P и 2Р в терминах координат Р.
б) Показать, что при ? = 16 каждая P Є E есть точка порядка 3.
в) Показать, что любая точка E с координатами в Fi6 фактически есть точка с координатами в F4. Далее с помощью теоремы Хассе при q = 4 и 16 определить число точек на кривой.
10. Вычислить дзета-функцию двух кривых из упражнения 8 над Fp для р = 5, 7, 11, 13.
11. Вычислить дзета-функцию кривой у2 + у = х3 — х + 1 над Fp для р = 2 и 3. (Сначала покажите, что в обоих случаях ./Vi =\1.) Пусть N(x) = х ¦ х обозначает норму комплексного числа. В терминах нормы най~ги простую формулу для Nr.
