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

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

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

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

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

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

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

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

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

.

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

.

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

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

або визначник

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

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

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

Наприклад. Розглянемо поле . Елементами цього поля є 16 векторів.

Таблиця 1.

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

Додавання:

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

Множення:

(0101)×(1101) =

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

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

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

Дійсно .

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

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

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

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

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

.

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

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

.

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

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

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

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

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

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

).

Точка на нескінченності  є вже одним з розв’язків даного рівняння. Зворотна точка тут, як і раніше, визначається інверсією знака координати

де

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

де

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

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

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

 або

де

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

де

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

де .

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

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

 і

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

Де

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

:

де .

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

Модифіковані якобіанові координати для рівняння

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

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

,

де

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

де

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

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

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

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

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

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