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