Современная прикладная криптография (стр. 37 )

Иногда теорему о разложении конечных абелевых групп формулируют в другом виде, когда разложение приводится в так называемой форме Смита [].

Теорема.

Любая конечная абелева группа изоморфна прямой сумме групп

Z + … + Z,

где n делит n для i=1, …, (s-1). Числа n однозначно определяются группой.

Эта форма записи и называется формой Смита. Форму Смита можно преобразовать в форму представления по степеням простых чисел и обратно. Для перехода к форме Смита надо выбрать наибольшие из степеней каждого простого числа и перемножить их, а затем повторить это пока ничего не останется. Для перехода от формы Смита надо просто разложить порядки циклических групп. Например, Z+Z+Z+Z изоморфна Z+Z. Это разные формы представления одной и той же группы.

Теорема.

Пусть E(F) –группа точек эллиптической кривой над конечным полем F.

Тогда она изоморфна или Z или прямой сумме Z+ Z, для некоторых целых n>=1, или n, n >=1 и n делит n.

Рассмотрим несколько примеров.

Пример.

Пусть Е(F_5) – группа точек эллиптической кривой, задаваемой уравнением

y = x + x + 1 над простым конечным полем F. При небольшом размере поля легко посчитать число элементов в этой группе.

x	X+x+1	y	Точки
0	1	+1, -1	(0,1), (0,4)
1	3	-	-
2	1	+1, -1	(2,1), (2,4)
3	1	+1, -1	(3,1), (3,4)
4	4	+2, -2	(4,2), (4,3)

Поэтому порядок группы равен 9 , группа является циклической с порождающим элементом (0, 1).

Доказательство

Из таблицы видно, что уравнению удовлетворяют 8 точек и, добавляя точку в бесконечности O, получаем, что порядок группы равен 9.

Для доказательства цикличности воспользуемся критерием [ГЕН03]:

G-циклическая gG: ord g=

Рассмотрим элемент (0,1) и по формулам сложения точек эллиптической кривой докажем критерий:

1.(0,1)+O=(0,1) 6.(3,1)+(0,1)=(2,4)

2.(0,1)+(0,1)=(4,2) 7.(2,4)+(0,1)=(4,3)

3.(4,2)+(0,1)=(2,1) 8.(4,3)+(0,1)=(0,4)

4.(2,1)+(0,1)=(3,4) 9.(0,4)+(0,1)=O

5.(3,4)+(0,1)=(3,1).

Порядок элемента (0,1) равен 9 по определению (ord gG=nN :gn=e).

Пример.

Пусть Е(F) – группа точек эллиптической кривой, задаваемой уравнением

y = x + 2 над простым конечным полем F.

Для этого примера группа Е(F) содержит следующие элементы

Е(F) = {O, (0,3), (0,4), (3,1), (3,6), (5,1), (5,6), (6,1), (6,6)}

Все эти точки Р удовлетворяют соотношению 3Р = О, а группа Е(F) изоморфна прямой сумме Z + Z.

Доказательство

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

Составим таблицу Кели для группы Е(F):

+	О	(0,3)	(0,4)	(3,1)	(3,6)	(5,1)	(5,6)	(6,1)	(6,6)
О	О	(0,3)	(0,4)	(3,1)	(3,6)	(5,1)	(5,6)	(6,1)	(6,6)
(0,3)	(0,3)	(0,4)	О	(6,1)	(5,6)	(3,1)	(6,6)	(5,1)	(3,6)
(0,4)	(0,4)	О	(0,3)	(5,1)	(6,6)	(6,1)	(3,6)	(3,1)	(5,6)
(3,1)	(3,1)	(6,1)	(5,1)	(3,6)	О	(6,6)	(0,3)	(5,6)	(0,4)
(3,6)	(3,6)	(5,6)	(6,6)	О	(3,1)	(0,4)	(6,1)	(0,3)	(5,1)
(5,1)	(5,1)	(3,1)	(6,1)	(6,6)	(0,4)	(5,6)	О	(3,6)	(0,3)
(5,6)	(5,6)	(6,6)	(3,6)	(0,3)	(6,1)	О	(5,1)	(0,4)	(3,1)
(6,1)	(6,1)	(5,1)	(3,1)	(5,6)	(0,3)	(3,6)	(0,4)	(6,6)	О
(6,6)	(6,6)	(3,6)	(5,6)	(0,4)	(5,1)	(0,3)	(3,1)	О	(6,1)

Представим группу Е(F) в виде прямой суммы двух подгрупп, воспользовавшись основной теоремой о строении конечной абелевой группы и теоремой о выделении прямого слагаемого в примарной абелевой группе получаем Е(F)=<g>+<f>(группа не циклическая т. к. ее порядок равен 9,а порядки всех элементов равны 3) , в частности из таблицы следует Е(F)=<(0,3)>+<(5,1)> ,т. к. порядки образующих элементов равны 3,то и порядки подгрупп <g> и <f> будут равны 3.А по критерию об изоморфизме циклических групп(Две циклические группы изоморфныих порядки равны([ГЕН03] Т.1,с249)) каждая из подгрупп изоморфна Z,из чего следует:

Е(F)= Z + Z. ч. т.д.

Пример.

Пусть Е(F) – группа точек эллиптической кривой, задаваемой уравнением