Сліди і базиси розширеного поля
Сліди і базиси розширеного поля. Подання точок кривої у різних координатних системах. Складність арифметичних операцій у групах точок ЕК
Від ідеї створення криптосистем
на еліптичних кривих (
)
до сьогоднішнього дня поряд із
криптоаналізом цих систем фахівці
безупинно і плідно працюють над
підвищенням ефективності
.
Насамперед це відноситься
до швидкодії криптосистеми або швидкості
обчислень. Одним з напрямків робіт у
цій сфері було вивчення і порівняльний
аналіз арифметики в поліноміальному і
нормальному базисах поля
.
Сліди і базиси розширеного поля
Операції в розширених полях вимагають введення таких понять, як слід елемента поля та базису поля.
Нехай
просте поле і
його розширення.
Слідом елемента
над полем
називається сума сполучених елементів
поля
.
Зокрема, слід елемента над
полем
визначається сумою
.
Розширення поля Галуа
є
-вимірним
векторним простором над полем
.
Базисом цього поля називається будь-яка
множина з
лінійно незалежних елементів поля
(див. лекції з дисципліни РПЕК). Кожен
елемент поля подається
-вимірним
вектором з координатами з поля
(або поліномом степеня
з коефіцієнтами з
).
Його також можна виразити як лінійну
комбінацію векторів базису.
Теорема 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.
Таблиця 2 Двійкове подання елементів у поліноміальному і нормальному базисах
|
|
|
|
|
|
|
|
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
Число операцій множення
,
піднесення до квадрата
й інверсій
елементів
простого поля при додаванні і подвоєнні
точок у різних координатних системах
|
Координати |
Додавання точок |
Подвоєння точок |
|
Афінні |
|
|
|
Проективні |
|
|
|
Якобіанові |
|
|
|
Чудновського |
|
|
|
Модифіковані Якобіанові |
|
|
Після обчислення точки
у змішаних координатах необхідно
повернутися в афінні координати, для
чого наприкінці обчислень потрібна
одна інверсія.