Эллиптические кривые над конечными полями.

В предыдущем пункте мы рассматривали сложение точек на эллиптической кривой с геометрической точки зрения. Однако для того, чтобы иметь возможность использовать эллиптические кривые и криптографии, нам необходимо рассмотреть кривые, координаты точек которых принадлежат конечному полю (по причинам, которые будут ясны позднее, будем полагать, что ). Формально определение эллиптической кривой остается прежним.

Определение 2.Эллиптической кривой над конечным полем называется множество точек следующего уравнения:

Е: , (5)

где числа являются константами в поле и удовлетворяют условию:

. (6)

Введем обозначение:

В дальнейшем под эллиптической кривой будем понимать множество .

Замечание 1.Если – поле характеристики 2, то эллиптическая кривая над – это множество точек, которые удовлетворяют уравнению вида

Е: , (5а)

или уравнению вида

Е: . (5б)

Если – поле характеристики 3, то эллиптическая кривая над – это множество точек, которые удовлетворяют уравнению вида

Е: . (5в)

Замечание 2.Имеется общая форма уравнения эллиптической кривой, которая применима при любом поле: В случае, когда ее можно привести к виду (5в) (или к виду (5), если В случае, когда , это уравнение приводится к виду (5а) или (5б).

Пример.Рассмотрим эллиптическую кривую Е: над полем . Подставляя вместо х значения 0,1, 2, …, 12, несложно выяснить, что лишь при х равном 1,2,9,12 выражение представляет собой квадратичный вычет по модулю 13. Поэтому состоит всего лишь из 9 точек:

Рассмотрим операцию сложения на .

Теорема 2.Пусть Е – эллиптическая кривая над полем и пусть – точки множества . Тогда:

1) точка , полученная в результате применения алгоритма сложения точек на эллиптической кривой (теорема 1) к точкам принадлежит множеству ;

2) множество образует абелеву группу.

Доказательство. Докажем утверждение 1. Несложно видеть, что если рассматриваемые точки удовлетворяют условиям 1, 2 теоремы 1, то точка , определенная в теореме 1, принадлежит эллиптической кривой. Так как координаты , выраженные в теореме 1, пункт 3, получены как решение системы уравнений, в которой одно из уравнений есть уравнение эллиптической кривой, то точка , построенная в пункте 3 теоремы 1, также принадлежит кривой Е.

Справедливость второго утверждения данной теоремы устанавливается непосредственной проверкой соответствующих аксиом.

Пример.Вернемся к эллиптической кривой Е: над полем из предыдущего примера. Для вычислим . Используя формулы теоремы 1, пункт 3, проводим вычисления в :

Следовательно, .

Для этой же кривой вычислим Имеем:

Значит, . Аналогичным образом можно найти суммы всех возможных пар точек рассматриваемой кривой. В результате получим следующую таблицу:

Координаты x,y точек кривой принадлежат множеству Поэтому множество является конечным. Если быть более точным, то переменная x может принимать одно из значений. Для каждого x уравнение может иметь не более двух значений переменной y. Если добавить бесконечно удаленную точку О, то мы получим, что количество точек на кривой не превосходит : . В действительности данная оценка является грубой и величина намного превосходит количество точек на кривой .

Если рассмотреть величину для фиксированного значения , то существует три возможности. Во-первых, величина может быть квадратичным вычетом по модулю (это происходит примерно в 50% случаев). Тогда значению соответствует две точки кривой . Во-вторых, величина может быть квадратичным невычетом по модулю (это также происходит примерно в 50% случаев). В-третьих, величина может равняться нулю. Такие случаи очень редки (сравнение имеет не более трех решений). Из всего сказанного следует, что количество точек на примерно равно

Теорема Хассе утверждает, что полученная нами оценка верна с точностью до случайных флуктуаций:

Теорема 3 (Хассе).Пусть – эллиптическая кривая над полем . Тогда:

где удовлетворяет условию:

Определение 3.Величина из теоремы Хассе называется следом Фробениуса числа .

Пример.Пусть Следующая таблица содержит величины для различных :

			3.46
		-2	4.47
		-3	5.29
		-4	6.63
			7.21
			8.25