Значения для 𝑥 от 0 до 22

𝑥	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
	1	3	11	8	0	16	16	6	15	3	22	9	16	3	22	10	19	9	9	2	17	14	22

Теперь сравниваем числа в нижних строках табл. 5 и 6. Число, попавшее в обе строки, определяет две точки кривой. Так, число 1 содержится и в нижней строке табл. 5, и в нижней строке табл. 6. Число 1 определяет точки (0,1) и (0,22); число 8 дает тоже две точки, находим по верхним строкам их координаты: это (3, 10) и (3, 13), и т. д. Таким образом, выбираем точки (отличные от 𝒪), являющиеся элементами Получаем табл. 7. Пара чисел (𝑥, 𝑦), для которой , включается в таблицу соответствий: это точка кривой.

Таблица 7

Точки кривой

(0, 1)	(6, 4)	(12, 19)
(0, 22)	(6, 19)	(13, 7)
(1, 7)	(7, 11)	(13, 16)
(1, 16)	(7, 12)	(17, 3)
(3, 10)	(9, 7)	(17,20)
(3, 13)	(9, 16)	(18,3)
(4, 0)	(11, 3)	(18,20)
(5, 4)	(11, 20)	(19,5)
(5, 19)	(12, 4)	(19,18)

Легко видеть, что эллиптическая кривая может иметь не более 2q + 1 различных -точек, т. е. точку в бесконечности и не более чем 2q пар (х, у), х, у , удовлетворяющих (1), или (18) или (19), если р = 2 или 3. А именно, для каждого из q возможных значений 𝑥 имеется не более двух значений 𝑦, удовлетворяющих (1).

Но так как лишь у половины элементов есть квадратные корни, естественно ожидать (если бы были случайными элементами поля), что количество -точек примерно вдвое меньше этого числа. Точнее, пусть – квадратичный характер . Это – отображение, переводящее x в 1 или –1 в зависимости от того, является или нет элемент 𝑥 квадратом элемента из (полагаем также (0) = 0). Например, если q – это простое число р, то (𝑥) = называется символом Лежандра. В любом случае число решений 𝑦 уравнения = 𝑢 равно 1 + (𝑢) и, значит, число решений уравнения (с учетом точки в бесконечности) равно

(20)

Следует ожидать, что одинаково часто принимает значения 1 и –1. Вычисление суммы очень похоже на «случайное блуждание», когда мы подбрасываем монету q раз, продвигаясь на шаг вперед, если выпал герб, и назад – если решка. Из теории вероятностей известно, что после q бросаний результат случайного блуждания оказывается на расстоянии порядка от исходного положения. Сумма ведет себя в чем-то аналогично случайному блужданию. Точнее, удалось доказать, что она ограничена величиной . Этот результат – теорема Хассе.

Теорема 6 (Теорема Хассе). Пусть N – число – точек на эллиптической кривой, определенной над . Тогда

. (21)

В дополнение к числу N элементов на эллиптической кривой над нам бывает нужно знать строение этой абелевой группы. Она не обязательно циклическая, но можно показать, что она всегда является произведением двух циклических групп. Это означает, что группа изоморфна произведению р-примарных групп вида ℤ/ , где произведение берется по всем простым делителям N (здесь ). Под типом абелевой группы -точек на 𝛦 мы понимаем список – порядков циклических р-примарных сомножителей в упомянутом представлении в виде произведения (если = 0, то опускаем). Найти тип не всегда легко.

Пример 12. Найти тип для кривой над .

Решение. Находим сначала число точек N. Из свойств квадратичного характера и (–1) = –1 следует, что в сумме (20) члены для 𝑥 и для –𝑥 взаимно уничтожаются: Следовательно, N = q + 1 = 72. Далее, имеется в точности четыре точки порядка 2 (включая «бесконечную» точку 𝒪): они соответствуют корням многочлена ^*. Это означает, что 2-примар-ная часть группы имеет тип (4, 2) и, таким образом, тип группы – это (4, 2, 3, 3) или (4, 2, 9), в зависимости от того, равно 9 или 3 число точек порядка 3. Следовательно, остается выяснить, существует ли 9 точек порядка 3. Заметим, что условие 3Р = 𝒪 при Р 𝒪 эквивалентно условию 2Р = ±Р, т. е. тому, что x-координаты точек 2Р и Р одинаковы. Согласно (17) это означает, что , т. е. . Упрощая, получаем Это уравнение имеет максимум 4 корня в . Каждый корень может давать не более двух точек (при у = , если есть квадрат по модулю 71), и если было бы 4 корня, то получилось бы 9 точек порядка 3 (включая точку 𝒪). В противном случае должно было бы быть меньше 9 точек порядка 3 (и, стало быть, в точности 3 таких точки). Но если корень 𝑥 биквадратного уравнения таков, что есть квадрат по модулю 71, то для другого его корня –𝑥 получаем, что не есть квадрат. Значит, число точек порядка 3 не может быть равно 9 и потому тип группы – (4, 2, 9).

Расширения конечных полей, гипотеза Вейля. Если эллиптическая кривая определена над , то она определена также над , r = 1, 2, … и имеет смысл рассматривать -точки, т. е. решения (1) над расширениями поля. Отправляясь от поля как поля, над которым задана Е, определяем число как число -точек на Е (таким образом, есть число точек с координатами в нашем «основном поле» ).

Для чисел можно рассмотреть «производящий ряд» Z(T, E/ ) – формальный степенной ряд в ℚ[T]:

𝑍(𝑇, 𝐸/ ) = , (22)

где Т – неизвестная; обозначение E/ указывает эллиптическую кривую и поле, которое мы берем в качестве основного, а сумма в правой части берется по всем r = 1, 2, … . Можно показать, что ряд справа (рассматриваемый как бесконечное произведение экспоненциальных степенных рядов ) имеет положительные целые коэффициенты. Этот степенной ряд называется дзета-функцией эллиптической кривой (над ) и представляет собой весьма важный объект, связанный с Е.

«Гипотеза Вейля» (ныне теорема Делиня, P. Deligne) в значительно более общем контексте (алгебраические многообразия произвольной размерности) утверждает, что дзета-функция имеет весьма специальный вид. В случае эллиптической кривой E/ Вейль (А. Weil) получил следующее утверждение.

Теорема 7 (теорема Вейля для эллиптической кривой). Дзета-функция есть рациональная функция от Т вида

𝑍(𝑇, 𝐸/ ) = , (23)

где от эллиптической кривой Е зависит лишь целое число 𝑎. Значение 𝑎 связано с числом N = соотношением N = q + 1 – 𝑎. Кроме того, дискриминант квадратного трехчлена в числителе отрицателен (т. е. – теорема Хассе), таким образом, этот трехчлен имеет два комплексно сопряженных корня и , оба по модулю равные (точнее, корнями являются 1/ и 1/ , а , – корни «возвратного» уравнения).

Пример 13. Легко вычисляется дзета-функция эллиптической кривой над , так как имеется всего три -точки. Она равна . Таким образом, числа, обратные корням числителя – это . Отсюда следует формула

(24)

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

, r = 1, 2, ... . (25)

Так как и , наряду с 𝑎, определяются значением N = , то число точек над полем однозначно определяет число точек над любым его расширением. Таким образом, теорему Вейля для эллиптических кривых можно использовать, в частности, для нахождения числа точек над расширениями высокой степени.

Краткий обзор методов построения кривых. Соотношение (25) дает возможность по значению вычислить значения для всех . Величины = образуют так называемую последовательность Люкá и для их вычисления используются простые рекуррентные соотношения:

Отсюда следует самый простой метод построения эллиптической кривой и определения ее порядка.

Выберем небольшое конечное поле GF (2^l) и в качестве базового конечного поля возьмем расширение этого небольшого поля степени k, т. е. базовое поле имеет вид GF(2^m), m = kl для некоторого k. Для каждого допустимого значения w порядка кривой над GF(2^l) вычислим величину  порядок некоторой эллиптической кривой над полем GF(2^m). Допустимые значения w определяются неравенством Хассе, Перебор значений w продолжаем до тех пор, пока не найдем такое значение N, которое содержит большой простой делитель. Порядок эллиптической кривой в криптографических применениях должен удовлетворять также дополнительному условию, о котором речь пойдет ниже. Теперь перебором по парам (𝑥, 𝑦) , 𝑦 0 остается найти эллиптическую кривую над малым полем, имеющую выбранный порядок w, число точек кривой над малым полем легко найти полным перебором.

Пример 14. Построим эллиптическую кривую. Возьмем небольшое поле GF(2⁸) и построим эллиптическую кривую над расширением этого небольшого поля степени k = 23, т. е. над полем GF(2¹⁸⁴). Область перебора в данном случае есть интервал (225,289), при w = 230 находим

Далее,

,

где

Это простое число. Перебором находим, что порядок w = 230 над небольшим полем имеет эллиптическая кривая

Следовательно, полученная эллиптическая кривая, если ее рассматривать над полем GF(2¹⁸⁴), имеет порядок N, содержащий простой множитель u.

Этот метод позволяет строить эллиптические кривые только в расширениях малых полей, т. е. применим не ко всем полям, но главный его недостаток состоит в том, что он дает небольшое множество эллиптических кривых, Так, для 𝑚 = 168 вообще нет кривых, пригодных для криптографических применений. Однако этот метод вполне пригоден для получения начального набора эллиптических кривых для экспериментальных целей.

Второй метод  метод комплексного умножения, более универсален, но и более сложен. В этом методе существенно используется кольцо эндоморфизмов эллиптической кривой.

Третий метод построения эллиптических кривых по существу самый логичный, мы выбираем наугад эллиптическую кривую и вычисляем ее порядок до тех пор, пока не найдем кривую с нужными свойствами. Р. Схоф предложил полиномиальный алгоритм определения порядка произвольной эллиптической кривой над простым конечным полем нечетной характеристики.

Приведем еще два полезных утверждения о порядке эллиптической кривой над конечным полем.

Теорема 8. Для порядка эллиптических кривых над полем 𝐺𝐹(𝑞), 𝑞 = , справедливы следующие утверждения: порядок имеет вид 𝑞 + 1 – 𝑡, где 𝑡 удовлетворяет одному из условий:

1. 𝑡 ≢ 0(mod 𝑝) и ≤ 4𝑞;

2. 𝑛 нечётное и либо 𝑡 = 0, либо = 𝑝𝑞 при 𝑝 = 2, 3;

3. 𝑛 чётное и либо 𝑡 = 4𝑞, либо = 𝑞 при 𝑝 ≢ 1(mod 3), либо 𝑡 = 0 при 𝑝 ≢ 1(mod 4).

Определение. Если 𝑝 делит 𝑡, то кривая называется суперсингулярной, иначе она называется несуперсингулярной.

Из этой теоремы следует, что для суперсингулярных кривых = 0, 𝑞, 2𝑞, 3𝑞, 4𝑞. Структура групп суперсингулярных кривых описывается следующей теоремой.

Теорема 9. Если = 𝑞, 2𝑞, 3𝑞, то группа циклическая. Если = 4𝑞, то группа изоморфна в случае 𝑡 = , или изоморфна в случае 𝑡 = – . Если 𝑡 = 0, 𝑞 ≢ 3(mod 4), то группа циклическая. Если 𝑡 = 0, 𝑞 ≡ 3(mod 4), то группа или циклическая или изоморфна .

В заключение заметим, что существует много аналогий между группой -точек на эллиптической кривой и мультипликативной группой . Например, по теореме Хассе они имеют примерно одинаковое число элементов.

Однако абелевы группы, которые строятся по эллиптическим кривым, имеют одно значительное преимущество, которое объясняет их ценность для криптографии: для одного и того же большого q существует богатый выбор различных эллиптических кривых с разными значениями N. Эллиптические кривые составляют богатый источник «естественно возникающих» конечных абелевых групп, и это открывает большие возможности для применения в криптографии.