Сліди і базиси розширеного поля

Сліди і базиси розширеного поля. Подання точок кривої у різних координатних системах. Складність арифметичних операцій у групах точок ЕК

Від ідеї створення криптосистем на еліптичних кривих () до сьогоднішнього дня поряд із криптоаналізом цих систем фахівці безупинно і плідно працюють над підвищенням ефективності .

Насамперед це відноситься до швидкодії криптосистеми або швидкості обчислень. Одним з напрямків робіт у цій сфері було вивчення і порівняльний аналіз арифметики в поліноміальному і нормальному базисах поля .

1. Сліди і базиси розширеного поля Операції в розширених полях вимагають введення таких понять, як слід елемента поля та базису поля.

Нехай просте поле і його розширення.

Слідом елемента над полем називається сума сполучених елементів поля

.

Зокрема, слід елемента над полем визначається сумою

.

Розширення поля Галуа євимірним векторним простором над полем. Базисом цього поля називається будь-яка множина з лінійно незалежних елементів поля (див. лекції з дисципліни РПЕК). Кожен елемент поля подаєтьсявимірним вектором з координатами з поля (або поліномом степеня з коефіцієнтами з). Його також можна виразити як лінійну комбінацію векторів базису.

Теорема 1. Елементи поля утворюють базис над полем тоді і тільки тоді, коли визначник матриці Вандермонда або визначник

Із множини всіляких базисів найбільш розповсюдженими є поліноміальний і нормальний базиси поля .

Поліноміальний базис, звичайно, будується за допомогою послідовних степенів примітивного елемента поля. Його назва пов’язана з тим, що при всі операції в полі здійснюються за модулем мінімального полінома елемента .

Примітивний елемент тут є утворюючим елементом мультиплікативної групи поля. слід базис розширений поле Наприклад. Розглянемо поле. Елементами цього поля є 16 векторів.

Таблиця 1.

Використовуємо при обчисленнях поліном (незвідний) Додавання:

(0101)+(1101) = (1000).

Множення:

(0101)(1101) =

Піднесення до степеня:

Таблиця 2 Мультиплікативна інверсія

Мультиплікативною інверсією для є

Дійсно .

Нормальний базис (НБ) над полем визначається як множина сполучених елементів поля з підходящим вибором елемента. Розглянемо далі властивості НБ над полем. На елемент тут накладається необхідна умова. Водночас не обов’язково має бути примітивним. У будь-якому полі існує елемент зі слідом 1, тому в будь-якому полі існує і НБ. Елементи НБ можна подативимірними векторами.

Зазначимо, що молодший розряд НБ звичайно записується ліворуч (на відміну від поліноміального, у якому молодший розряд прийнято записувати праворуч).

Кожен наступний елемент базису є циклічним зсувом вправо попереднього. Оскільки, елемент 1 поля визначається координатами. Як бачимо, векторне подання елемента 1 поля в поліноміальному і нормальному базисах різні.

Для порівняння двійкове подання елементів у поліноміальному і нормальному базисах подано в таблиці 3.

Таблиця 2 Двійкове подання елементів у поліноміальному і нормальному базисах

Довільний елемент поля в нормальному базисі подається як

.

Піднесення до квадрата елемента в нормальному базисі дає

Таким чином, операція піднесення до квадрата (або витягу кореня квадратного) зводиться до циклічного зсуву вправо (або вліво) векторного подання елемента. Це одне з важливих технологічних переваг нормального базису перед поліноміальним. Іншою його перевагою є простота визначення сліду елемента. Дійсно:

.

Отже, слід елемента дорівнює 0 при парній вазі його векторного подання в НБ і 1 — при непарній вазі. Ця властивість радикально спрощує визначення сліду елемента у НБ.

Наприклад: елемент у нормальному базисі має парну вагу векторного подання. Слід цього елемента дорівнює 0 Дійсно На наступній лекції ми розглядатимемо окремо т.з. оптимальний нормальний базис, який має значні переваги у швидкості та технологічності обчислень.

Під час обчислення точок з багаторазовими операціями додавання (віднімання) і подвоєння більш продуктивними є групові операції не в афінних координатах, а різного роду проективних координатах. Це дозволяє уникнути обчислення оберненого елемента в полі як самої трудомісткої операції й заощадити тимчасові обчислювальні ресурси.

У стандартних проективних координатах проективна точка, , відповідає афінній точці Однорідне рівняння кривої після заміни змінних і множення на куб перемінної приймає вигляд

(в афінних координатах рівняння кривої має вигляд

).

Точка на нескінченності є вже одним з розв’язків даного рівняння. Зворотна точка тут, як і раніше, визначається інверсією знака координати Подібно тому, як в афінних координатах, сумою точок і при називається точка, координати якої (позначення надалі опускається для скорочення запису) рівні:

де

Операцію підсумовування однакових точок називають подвоєнням, а координати точки дорівнюють:

де

Час виконання операції додавання і подвоєння, де позначає проективне подання точки.

Наступний вид проективних координат якобіанові координати.

До них можна перейти ізоморфним перетворенням координат, помноживши рівняння на, при цьому отримаємо:

або де

Сумою точок і при є точка, координати якої визначаються як:

де

При подвоєнні точки кривої отримаємо :

де .

У даному випадку час виконання складає і, де позначає якобіаново подання точки.

Замість трьох якобіанових координат точки Чудновський запропонував використовувати п’ять: Рівняння кривої описується формулою, а сума точок

і

при визначається як точка, координати Чудновського якої рівні:

Де При подвоєнні точки кривої одержимо де .

Час виконання складе і, де означає подання точки в координатах Чудновського.

Модифіковані якобіанові координати для рівняння кривої містять чотири координати

Сума точок і при визначається як точка, модифіковані якобіанові координати якої дорівнюють

де

При подвоєнні точки кривої отримаємо де

Нарешті, можна зробити наступні оцінки. Час виконання дорівнює і, де означає подання точки в модифікованих якобіанових координатах.

Формули, що визначають сумарне число інверсій (), множень і піднесень до квадрата при додаванні і подвоєнні точок відповідно в афінних, проективних, якобіанових координатах, координатах Чудновського і модифікованих якобіанових координатах наведені в таблиці 1 (узагальнення).

За деякими оцінками, одна інверсія, а піднесення до квадрата (при операціях у простому полі Галуа). Звідси стає зрозумілою доцільність переходу до проективних або до якобіанових координат, у яких операції інверсії відсутні.

Мінімальна обчислювальна складність додавання досягається за допомогою координат чудновського, а подвоєння — у модифікованих якобіанових координатах. Тому, звичайно, користуються змішаними координатами з метою оптимізації обчислень при багаторазовому додаванні точки.

Таблиця 3 Число операцій множення, піднесення до квадрата й інверсій елементів простого поля при додаванні і подвоєнні точок у різних координатних системах

Після обчислення точки у змішаних координатах необхідно повернутися в афінні координати, для чого наприкінці обчислень потрібна одна інверсія.