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

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

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

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

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 - Двійкове подання елементів у поліноміальному і нормальному базисах

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 Дійсно

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

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать