АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Еліптичні криві над простим полем Галуа GF (p)

Читайте также:
  1. Алгоритм скалярного множення на еліптичній кривій
  2. Глава пятнадцатая. Портрет человека, связанного с полем намерения
  3. Класні години є найбільш поширеними та найбільш організаційно простими формами виховної діяльності.
  4. Криві титрування
  5. Криві «доход-споживання». Криві і закони Енгеля
  6. Криві «ціна-споживання» та виведення кривих попиту
  7. Нарощена сума боргу за простими відсотками
  8. Неповні та еліптичні речення.
  9. ПОЛЕМИКА - ЭТО ПРИЗНАК РАВЕНСТВА
  10. Полемика Августина Аврелия и Пелагия о свободе воли
  11. Полемика вокруг биопсихиатрии

 

У криптографії застосовуються еліптичні криві, визначені над скінченнимим полями Галуа GF (q). У цьому випадку вони являють собою множину точок E (GF (q)), координати яких задовольняють рівнянню кривої.

Приклад. Дано еліптичну криву y2 = x3 + x + 1(mod 5) над полем GF (5). Цьому рівнянню задовольняють 8 скінченних точок із координатами з GF (5). На рис.4.2 подано приклад цієї кривої.


Рисунок 4.2 - Приклад еліптичної кривої y 2 = x 3 + x + 1 mod 5 над полем GF (5)

 

Розглянемо еліптичні криві над простим полем GF (p):

y 2 = x 3 + ax + b (mod p), (4.1)

де р - просте число - модуль перетворень; параметри кривої
a, b Î GF (p) - невід¢ємні і задовольняють умові гладкості кривої , змінні x, y Î GF (p).

Крім точок (x, y), що задовольняють рівнянню (4.1), у множину точок еліптичної кривої також включається нескінченно віддалена точка O.

Наприклад, при p = 2 точками еліптичної кривої
y2 = x3 + x +1 (mod 2) є три точки - (0,1), (1,1) і O.

Позначимо через Ep (a, b) множину точок еліптичної кривої виду (4.1).

На множині E p(a, b) введемо операцію додавання + за правилом: нехай P 1=(x 1, y 1) і P 2=(x 2, y 2) – точки еліптичної кривої, тоді координати суми точок P 3 = P 1+ P 2 = (x 3, y 3) визначаються за формулами

 

x 3 = (l 2 – x 1 – x 2) mod p

y 3 = (l (x 1 – x 3) – y 1) mod p

Якщо P 1¹ P 2, то .

Якщо P 1= P 2, то .

Вважаємо, що P + O = O + P.

 

Твердження. Множина точок еліптичної кривої Ep (a, b) з операцією додавання + утворює адитивну абелеву групу з нейтральним (нульовим) елементом O, тобто виконуються умови групи:

а) якщо P і Q Î E p(a, b), то P + Q Î E p(a, b);

б) для будь-яких трьох точок кривої P, Q, S Î E p(a, b)

P + (Q + S) = (P + Q) + S;

в) для будь-якої точки P = (x, y) Î E p(a, b) існує обернена точка – P, така, що P + (– P) = O; точка (– P) має координати (x, – y).

 

Приклад. Знайдемо точки еліптичної кривої y 2 = x 3 + x + 1(mod 5). Можливі значення змінної x Î {0, 1, 2, 3, 4}. Задаючи значення x, знайдемо y:

x = 0 y 2 = 1 Þ y = 1, y = – 1 або y = 4

x = 1 y 2 = 3 Þ розв'язків немає

x = 2 y 2 = 11 = 1 Þ y = 1, y = 4

x = 3 y 2 = 31 = 1 Þ y = 1, y = 4

x = 4 y 2 = 69 = 4 Þ y = 2, y = – 2 або y = 3

Таким чином, одержимо точки (0,1), (0,4), (2,1), (2,4), (3, 1), (3,4), (4,2), (4,3) і добавляємо точку O. Еліптична крива E5 (1,1) містить 9 точок.

 

Визначення. Порядком групи точок еліптичної кривої Ep (a, b) називається число елементів цієї групи. Позначення - # Ep (a, b).

Група точок еліптичної кривої E5 (1,1) має порядок рівний 9.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)