Сліді и базисом розширеного поля. Подання точок крівої у різніх координатної системи. Складність Арифметичний операцій у групах точок ЕК
Від ідеї создания криптосистем на еліптічніх кривих () до сьогоднішнього дня поряд Із кріптоаналізом ціх систем фахівці безупинності и плідно Працюють над підвіщенням ефектівності.
самперед це відносіться до швідкодії криптосистеме або Швидкості обчислень. Одним з напрямків робіт у Цій сфере Було Вивчення и порівняльній аналіз арифметики в поліноміальному и нормальному базисах поля.
1. Сліді и базисом розширеного поля
Операції в розширеного полях вімагають введення таких зрозуміти, як слід елемента поля та базису поля.
Нехай - просте поле і - его Розширення.
Слідом елементу над полем назівається сума сполучення ЕЛЕМЕНТІВ поля
.
Зокрема, слід елемента над полем візначається сумою
.
Розширення поля Галуа є-вімірнім векторна простором над полем. Базисом цього поля назівається будь-яка множини з лінійно незалежних ЕЛЕМЕНТІВ поля (дів. Лекції з дисципліни РПЕК). Коженая елемент поля подається-вімірнім вектором з координатами з поля (або поліномом степеня з коефіцієнтамі з). Его такоже можна віразіті як лінійну комбінацію векторів базису.
В
Теорема 1. Елементи поля утворюють базис над полем тоді и Тільки тоді, коли Визначник матріці Вандермонда
В
або Визначник
В
Із множини всілякіх базісів найбільш Розповсюдження є поліноміальній и нормальний базиси поля.
Поліноміальній базис, звичайна, будується за помощью послідовніх степенів прімітівного елемента поля. Йо назва пов'язана з тим, что при ВСІ Операції в полі здійснюються за модулем мінімального полінома елемента.
Прімітівній елемент тут є утворюючім елементом мультіплікатівної групи поля. слід базис Розширення полі
Наприклад. Розглянемо полі. Елементами цього поля є 16 векторів. p> Таблиця 1.
(0000)
(0001)
(0010)
(0011)
(0100)
(0101)
(0110)
(0111)
(1000)
(1001)
(1010)
(1011)
(1100)
(1101)
(1110)
(1111)
Вікорістовуємо при обчисления поліном (незвідній)
Додавання:
(0101) + (1101) = (1000).
множення:
(0101) Г— (1101) =
В
Піднесення до степеня:
В
Таблиця 2 - Мультіплікатівна інверсія
В
Мультіплікатівною інверсією для є
В
Дійсно.
Нормальний базис (НБ) над полем візначається як множини сполучення ЕЛЕМЕНТІВ поля з підходящім Вибори елемента. Розглянемо далі Властивості НБ над полем. На елемент тут накладається Необхідна Умова:. Водночас НЕ обов'язково має буті прімітівнім. У будь-якому полі існує елемент Зі Слідом 1, того в будь-якому полі існує и НБ. Елементи НБ можна податі -Вімірнімі векторами. br/>В
Зазначімо, что молодший розряд НБ Звичайний запісується ліворуч (на відміну від поліноміального, у якому молодший розряд Прийнято запісуваті праворуч).
Коженая Наступний елемент базису є ціклічнім Зсув вправо попередня. Оскількі, елемент 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
