Сліди і базиси розширеного поля
Сліди і базиси розширеного
поля. Подання точок кривої у різних координатних системах. Складність
арифметичних операцій у групах точок ЕК
Від ідеї створення криптосистем на
еліптичних кривих () до
сьогоднішнього дня поряд із криптоаналізом цих систем фахівці безупинно і
плідно працюють над підвищенням ефективності .
Насамперед це відноситься до
швидкодії криптосистеми або швидкості обчислень. Одним з напрямків робіт у цій
сфері було вивчення і порівняльний аналіз арифметики в поліноміальному і
нормальному базисах поля .
1. Сліди і базиси розширеного поля
Операції в розширених полях вимагають введення таких понять, як слід елемента
поля та базису поля.
Нехай - просте поле
і - його розширення.
Слідом елемента над полем називається сума сполучених елементів поля
.
Зокрема, слід елемента над полем визначається сумою
.
Розширення поля Галуа є -вимірним векторним простором над полем . Базисом цього поля
називається будь-яка множина з лінійно незалежних елементів поля (див. лекції з дисципліни
РПЕК). Кожен елемент поля подається -вимірним вектором з координатами з поля (або поліномом степеня з коефіцієнтами з ). Його також можна виразити
як лінійну комбінацію векторів базису.
Теорема 1. Елементи поля утворюють базис над полем тоді і тільки тоді, коли визначник
матриці Вандермонда
або визначник
Із множини всіляких базисів
найбільш розповсюдженими є поліноміальний і нормальний базиси поля .
Поліноміальний базис, звичайно,
будується за допомогою послідовних степенів примітивного елемента поля . Його назва пов'язана з
тим, що при всі
операції в полі здійснюються за модулем мінімального полінома елемента .
Примітивний елемент тут є утворюючим елементом
мультиплікативної групи поля. слід базис розширений
поле
Наприклад. Розглянемо поле . Елементами цього поля є 16
векторів.
Таблиця 1.
(0000)
|
(0001)
|
(0010)
|
(0011)
|
(0100)
|
(0101)
|
(0110)
|
(0111)
|
(1000)
|
(1001)
|
(1010)
|
(1011)
|
(1100)
|
(1101)
|
(1110)
|
(1111)
|
Використовуємо при обчисленнях
поліном (незвідний)
Додавання:
(0101)+(1101) = (1000).
Множення:
(0101)×(1101) =
Піднесення до степеня:
Таблиця 2 - Мультиплікативна інверсія
Мультиплікативною інверсією для є
Дійсно .
Нормальний базис (НБ) над полем визначається як множина
сполучених елементів поля з підходящим вибором елемента . Розглянемо далі властивості НБ над полем . На елемент тут накладається необхідна умова: . Водночас не обов'язково має бути примітивним. У
будь-якому полі існує елемент
зі слідом 1, тому в будь-якому полі існує і НБ. Елементи НБ можна подати -вимірними векторами.
Зазначимо, що молодший розряд НБ
звичайно записується ліворуч (на відміну від поліноміального, у якому молодший
розряд прийнято записувати праворуч).
Кожен наступний елемент базису є
циклічним зсувом вправо попереднього. Оскільки , елемент 1 поля визначається координатами . Як бачимо, векторне подання
елемента 1 поля в
поліноміальному і нормальному базисах різні.
Для порівняння двійкове подання
елементів у поліноміальному і нормальному базисах подано в таблиці 3.
|
|
|
|
|
|
0
|
0000
|
0000
|
|
1011
|
1110
|
1
|
0001
|
1111
|
|
0101
|
0011
|
|
0010
|
1001
|
|
1010
|
0001
|
|
0100
|
1100
|
|
0111
|
1010
|
|
1000
|
1000
|
|
1110
|
1101
|
|
0011
|
0110
|
|
1111
|
0010
|
|
0110
|
0101
|
|
1101
|
1011
|
|
1100
|
0100
|
|
1001
|
0111
|
Довільний елемент поля в
нормальному базисі подається як
.
Піднесення до квадрата елемента в нормальному базисі дає
Таким чином, операція піднесення
до квадрата (або витягу кореня квадратного) зводиться до циклічного зсуву
вправо (або вліво) векторного подання елемента. Це одне з важливих
технологічних переваг нормального базису перед поліноміальним. Іншою його
перевагою є простота визначення сліду елемента. Дійсно:
.
Отже, слід елемента дорівнює 0 при
парній вазі його векторного подання в НБ і 1 – при непарній вазі. Ця
властивість радикально спрощує визначення сліду елемента у НБ.
Наприклад: елемент у нормальному базисі має парну вагу
векторного подання. Слід цього елемента дорівнює 0 Дійсно
На наступній лекції ми
розглядатимемо окремо т.з. оптимальний нормальний базис, який має значні
переваги у швидкості та технологічності обчислень.
Під час обчислення точок з
багаторазовими операціями додавання (віднімання) і подвоєння більш
продуктивними є групові операції не в афінних координатах, а різного роду
проективних координатах. Це дозволяє уникнути обчислення оберненого елемента в
полі як самої трудомісткої операції й заощадити тимчасові обчислювальні
ресурси.
У стандартних проективних
координатах проективна точка , , відповідає афінній точці Однорідне рівняння кривої після
заміни змінних і множення на куб перемінної приймає вигляд
(в афінних координатах рівняння
кривої має вигляд
).
Точка на нескінченності є вже одним з розв’язків
даного рівняння. Зворотна точка тут, як і раніше, визначається інверсією знака координати
де
Операцію підсумовування однакових
точок називають подвоєнням,
а координати точки дорівнюють:
де
Час виконання операції додавання і подвоєння , де позначає проективне подання точки.
Наступний вид проективних
координат - якобіанові координати.
До них можна перейти ізоморфним
перетворенням координат, помноживши рівняння на , при цьому отримаємо:
або
де
Сумою точок і при є точка , координати якої визначаються як:
де
При подвоєнні точки кривої
отримаємо :
де .
У даному випадку час виконання
складає і , де позначає якобіаново подання точки.
Замість трьох якобіанових
координат точки Чудновський запропонував використовувати п'ять: Рівняння кривої описується формулою , а сума точок
і
при визначається як точка , координати Чудновського якої рівні:
Де
При подвоєнні точки кривої одержимо
:
де .
Час виконання складе і , де означає подання точки в координатах
Чудновського.
Модифіковані якобіанові координати для рівняння
кривої містять чотири координати
Сума точок і при визначається як точка , модифіковані якобіанові координати
якої дорівнюють:
,
де
При подвоєнні точки кривої
отримаємо
де
Нарешті, можна зробити наступні
оцінки. Час виконання дорівнює і , де означає подання точки в модифікованих
якобіанових координатах.
Формули, що визначають сумарне
число інверсій ( ), множень і піднесень до квадрата при додаванні і подвоєнні
точок відповідно в афінних , проективних , якобіанових координатах, координатах Чудновського і модифікованих якобіанових
координатах наведені в
таблиці 1 (узагальнення).
За деякими оцінками, одна інверсія
, а піднесення до
квадрата (при
операціях у простому полі Галуа). Звідси стає зрозумілою доцільність переходу
до проективних або до якобіанових координат, у яких операції інверсії відсутні.
Мінімальна обчислювальна
складність додавання досягається за допомогою координат чудновського, а
подвоєння – у модифікованих якобіанових координатах. Тому, звичайно,
користуються змішаними координатами з метою оптимізації обчислень при багаторазовому
додаванні точки.
Таблиця 3 - Число операцій множення , піднесення до квадрата й інверсій елементів простого поля при додаванні і
подвоєнні точок у різних координатних системах
Координати
|
Додавання точок
|
Подвоєння точок
|
Афінні
|
|
|
Проективні
|
|
|
Якобіанові
|
|
|
Чудновського
|
|
|
Модифіковані
Якобіанові
|
|
|
Після обчислення точки у змішаних координатах
необхідно повернутися в афінні координати, для чого наприкінці обчислень
потрібна одна інверсія.