Конечные поля – поля Галуа2

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

Утверждение (о существовании и единственности конечных полей). Если F – конечное поле, то оно содержит q = pⁿ элементов, где p – простое число, n  1.

Поля вычетов Z_p являются простейшими примерами конечных полей.

Обозначение конечных полей – GF ( q ).

Поле GF( p ), где p – простое число, называется простым, поле GF( pⁿ ) называется расширенным.

Утверждение. Поле GF ( pⁿ ) имеет характеристику p .

Утверждение. Если GF ( pⁿ ) – поле, то GF ( p^d ) – подполе поля GF ( pⁿ ) для любого d – делителя n.

Ненулевые элементы поля Галуа GF(q) образуют мультипликативную группу, которая обозначается через GF^*( q ).

Утверждение. Мультипликативная группа GF^*( q ) является циклической группой порядка q – 1.

Образующий элемент мультипликативной группы поля Галуа называют примитивным элементом поля.

В поле примитивным элементом является класс вычетов . Его степени

, , , , ,

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

Контрольные вопросы

1. Дайте определение кольца.

2. Какое кольцо называется коммутативным?

3. Дайте определение поля.

4. Что такое мультипликативная группа поля?

5. Сформулируйте основное свойство мультипликативной группы поля.

6. Что такое поле Галуа?

7. Что такое примитивный элемент поля?

§ 12 Эллиптические кривые в криптографии

Эллиптическая кривая – это математический объект, который может быть определен над любым полем, в частности над полем вещественных чисел или над конечным полем Галуа.

В общем случае эллиптическая кривая над полем К имеет вид

E: y² + axy + by = x³ +cx² + dx + e ,

где a, b, c, d, e  K .

На рисунке 1 представлен пример эллиптической кривой, определенной уравнением

y² = x³ + x + 1 ,

над полем вещественных чисел R.

Рисунок 1. Пример эллиптической кривой y² = x³ + x + 1 над R.

В криптографии применяются эллиптические кривые, определенные над конечными полями Галуа GF ( q ). В этом случае они представляют собой множество точек E(GF(q)), координаты которых удовлетворяют уравнению кривой. Такая форма называется редуцированной.

Пример. Дана эллиптическая кривая y² = x³ + x + 1 mod 5 над полем GF(5). Этому уравнению удовлетворяют 8 конечных точек с координатами из GF(5). На рисунке 2 представлен пример этой кривой.

Рассмотрим эллиптические кривые над простым полем GF (p) следующего вида:

y² = x³ + ax + b mod p, (1)

где р – простое число-модуль преобразований; параметры кривой a, b  GF (p) - неотрицательны и удовлетворяют условию гладкости кривой , переменные x, y  GF (p) .

Кроме точек ( x, y ), удовлетворяющих уравнению (1), в множество точек эллиптической кривой также включается бесконечно удаленная точка O .

Рисунок 2. Пример эллиптической кривой кривая y² = x³ + x + 1 mod 5 над полем GF(5).

Таким образом, при p = 2 точками эллиптической кривой y² = x³ + x + 1 mod 2 являются четыре точки – (0,1), (1,0), (1,1) и O .

Обозначим через E_p(a,b) множество точек эллиптической кривой вида y² = x³ + ax + b mod p .

На множестве E_p(a,b) введем операцию сложения + по правилу:

пусть и – точки эллиптической кривой, тогда координаты суммы точек определяются формулами

Если P₁  P₂ ,

Если P₁ = P₂ ,

Считаем, что P + O = O + P .

Утверждение. Множество точек эллиптической кривой E_p(a,b) с операцией сложения + образует аддитивную абелеву группу с нейтральным (нулевым) элементом O, т.е. выполняются следующие условия группы:

1) если P и Q  E_p(a,b) , то P + Q  E_p(a,b)

2) для любых трех точек кривой P, Q, S  E_p(a,b) P + (Q + S) = (P + Q) + S

3) для любой точки P = (x, y)  E_p(a,b) существует обратная точка – P , т.ч. P + (– P) = O ; точка – P имеет координаты (x, – y) .

Пример. Найдем точки эллиптической кривой y² = x³ + x + 1 mod 5 . Возможные значения переменной x – 0, 1, 2, 3, 4 . Задавая значения x , найдем y :

x = 0 y² = 1  y = 1, y = – 1 или y = 4

x = 1 y² = 3  решений нет

x = 2 y² = 11 = 1  y = 1, y = 4

x = 3 y² = 31 = 1  y = 1, y = 4

x = 4 y² = 69 = 4  y = 1, y = 4

Таким образом, получим точки (0,1), (0,4), (2,1), (2,4), (3, 1), (3,4), (4,1), (4,4) и добавляем точку O. Эллиптическая кривая E₅(1,1) содержит 9 точек.

Определение. Порядком группы точек эллиптической кривой E_p(a,b) называется число элементов этой группы. Обозначение – # E_p(a,b) .

Группа точек эллиптической кривой E₅(1,1) имеет порядок, равный 9.