Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Эллиптические кривые над конечным полем. До конца параграфа предполагаем, что К — конечное поле F? с q = рт элементами. Пусть E — эллиптическая кривая, определенная над F?. Если р = 2 или 3, то E задается уравнением вида (2) или (3) соответственно.
Легко усмотреть, что эллиптическая кривая может иметь не более 2q + 1 различных Fg-точек, т. е. точку в бесконечности и не более чем 2q пар (х,у), х, у ? F9, удовлетворяющих (1) (или (2) или (3), если р = 2 или 3). А именно, для каждого из q возможных значений х имеется не более двух значений у, удовлетворяющих (1).
Но так как лишь у половины элементов F* имеются квадратные корни, естественно ожидать (если бы X + ах + b были случайными элементами поля), что количество Fg-точек примерно вдвое меньше этого числа. Точнее, пусть х — квадратичный характер F?. Это — отображение, переводящее х Є F* в 1 или —1 в зависимости от того, является или нет элемент X квадратом элемента из F9 (полагаем также
х(0) = 0). Например, если q — это простф число р, то X(2O — (f) есть символ Лежандра (см. §11.2). В любом случае число решений у є F9 уравнения у = и равно 1 -f х(и) и> значит, число решений (1) (с учетом точки в бесконечности) равно
1 + X^1 + Х(*3 + ах + Ь)) = q + 1 + Yl + ах + Ь)' (6)
Следует ожидать, что х(х + ах + Ь) одинаково часто принимает значения + 1 и —1. Вычисление суммы очень похоже на «случайное блуждание», когда мы подбрасываем монету q раз, продвигаясь на шаг вперед, если выпал герб, и назад — если решетка. В теории вероятностей подсчитывается, что после q бросаний случайное блуждание оказывается на расстоянии порядка y/q от исходного положения.
Сумма Y2 х(х3 + ах + Ь) ведет себя в чем-то аналогично случайному блужданию. Точнее, удалось доказать, что она ограничена величиной 2y/q. Этот результат — теорема Хассе; ее доказательство см. в § V. 1 указанной в списке литературы книги Силвермена (J.Silverman) об эллиптических кривых.
§ 1. ОСНОВНЫЕ ФАКТЫ
197
Теорема Хассе. Пусть N — число F9-точек на эллиптической кривой, определенной над F9. Тогда
\N -(q + 1)| *C2v^.
В дополнение к числу N элементов на эллиптической кривой над F9 нам бывает нужно знать строение этой абелевой группы. Она — не обязательно циклическая, но можно показать, что она — всегда произведение двух циклических групп. Это означает, что группа изоморфна произведению р-примарных групп вида Z/paZ X Z/p^Z, где произведение берется по всем простым делителям N (здесь a ^ l,? ^ 0). Под типом абелевой группы Fg-точек на E мы понимаем список (... ,р ,р ,.. .)p|yv порядков циклических р-примарных сомножителей
в упомянутом представлении в виде произведения (если ? = 0, р^ опускаем). Найти тип не всегда легко.
2 3
Пример 4. Найти тип для кривой у = х — х над F71.
Решение. Находим сначала число точек N. Заметим, что в сумме (6) члены для X и для —х сокращаются друг с другом: х((-х)3-(-х)) = х{-1)х{х3-х) = -х(х3-х), так как 71 = 3 (mod 4), и потому х( —1) = ~ 1- Следовательно, N = q4- 1 = 72. Далее, имеется в точности четыре точки порядка 2 (включая «бесконечную» точку О): они соответствуют корням многочлена х — х = х(х + 1)(х — 1) (см. упражнение 4 а ниже). Это означает, что 2-примарная часть группы имеет тип (4, 2) и, таким образом, тип группы — это (4, 2, 3, 3) или (4, 2, 9), в зависимости от того, равно 9 или 3 число точек порядка 3. Следовательно, остается выяснить, существует ли 9 точек порядка 3. Заметим, что условие ЗР = О при P ф О эквивалентно условию 2Р = ±Р, т.е. тому, что х-координаты точек 2Р и P одинаковы. Согласно (5) это означает, что ((Sx2 — I)2/(2у))2 - 2х = х, т.е. (Зх2 - I)2 = 12ху2 = 12х4 — 12х2. Упрощая, получаем Зх4 — 6х2 -1 = 0. Это уравнение имеет, самое большее, 4 корня в F71. Каждый корень
может давать не более двух точек (при у = ± Vx3 — х, если х3 — х есть квадрат по модулю 71), и если было бы 4 корня, то получилось бы 9 точек порядка 3 (включая точку О). В противном случае должно было бы быть меньше 9 точек порядка 3 (и, стало быть, в точности 3 таких точки). Но если корень X биквадратного уравнения таков, что х3 — х есть квадрат по модулю 71, то для другого его корня —х получаем, что (-х)3 — (—х) = —(—X3 — х) не есть квадрат. Значит, число точек порядка 3 не может быть равно 9 и потому тип группы — (4, 2, 9).
198
гл. vi. эллиптические кривые
Расширения конечных полей, гипотеза Вейля. Если эллиптическая кривая определена над F9, она определена также над Fqr, г = 1,2,..., и имеет смысл рассматривать Fqr-точки, т.е. решения (1) над расширениями поля. Отправляясь от поля F9 как поля, над которым задана Е, определяем число N1. как число F?r-точек на Е. (Таким образом, TV1 = N есть число точек с координатами в нашем «основном поле» F9.)
Для чисел N1. можно рассмотреть «производящий ряд» Z(T; E/Fq) -формальный степенной ряд в Qf[T]]:
Z(T;E/Fq) = e^N^/r, (7)
где T — неизвестная; обозначение E/Fq указывает эллиптическую кривую и поле, которое мы берем в качестве основного, а сумма в правой части берется по всем г = 1,2,... Можно показать, что ряд справа (рассматриваемый как бесконечное произведение экспоненци-альных степенных рядов е J имеет положительные целые коэф-
