Сліди і базиси розширеного поля. Подання точок кривої у різних координатних системах. Складність арифметичних операцій у групах точок ЕК
Від ідеї створення криптосистем на еліптичних кривих ( 
) до сьогоднішнього дня поряд із криптоаналізом цих систем фахівці безупинно і плідно працюють над підвищенням ефективності .
Насамперед це відноситься до швидкодії криптосистеми або швидкості обчислень. Одним з напрямків робіт у цій сфері було вивчення і порівняльний аналіз арифметики в поліноміальному і нормальному базисах поля 
.
1. Сліди і базиси розширеного поля
Операції в розширених полях вимагають введення таких понять, як слід елемента поля та базису поля.
Нехай 
- просте поле і 
- його розширення.
Слідом елемента $IMAGE6$ над полем $IMAGE7$ називається сума сполучених елементів поля $IMAGE8$
$IMAGE9$.
Зокрема, слід елемента над полем $IMAGE10$ визначається сумою
$IMAGE11$.
Розширення поля Галуа $IMAGE12$ є $IMAGE13$-вимірним векторним простором над полем $IMAGE14$. Базисом цього поля називається будь-яка множина з $IMAGE13$ лінійно незалежних елементів поля $IMAGE16$ (див. лекції з дисципліни РПЕК). Кожен елемент поля подається $IMAGE13$-вимірним вектором з координатами з поля $IMAGE14$ (або поліномом степеня $IMAGE19$ з коефіцієнтами з $IMAGE14$). Його також можна виразити як лінійну комбінацію векторів базису.
$IMAGE21$
Теорема 1. Елементи $IMAGE16$ поля $IMAGE12$ утворюють базис над полем $IMAGE14$ тоді і тільки тоді, коли визначник матриці Вандермонда
$IMAGE25$
або визначник
$IMAGE26$ $IMAGE27$
Із множини всіляких базисів найбільш розповсюдженими є поліноміальний і нормальний базиси поля $IMAGE12$.
Поліноміальний базис, звичайно, будується за допомогою послідовних степенів примітивного елемента поля $IMAGE29$. Його назва пов'язана з тим, що при $IMAGE30$ всі операції в полі здійснюються за модулем мінімального полінома елемента $IMAGE31$.
Примітивний елемент $IMAGE31$ тут є утворюючим елементом мультиплікативної групи поля. слід базис розширений поле
Наприклад. Розглянемо поле $IMAGE33$. Елементами цього поля є 16 векторів.
Таблиця 1.
| (0000) | (0001) | (0010) | (0011) | (0100) | (0101) | (0110) | (0111) |
| (1000) | (1001) | (1010) | (1011) | (1100) | (1101) | (1110) | (1111) |
Використовуємо при обчисленнях поліном $IMAGE34$(незвідний)
Додавання:
(0101)+(1101) = (1000).
Множення:
(0101)×(1101) =
$IMAGE35$
Піднесення до степеня: $IMAGE36$
$IMAGE37$ $IMAGE38$ $IMAGE39$
Таблиця 2 - Мультиплікативна інверсія
| $IMAGE40$ | $IMAGE41$ | $IMAGE42$ | $IMAGE43$ |
| $IMAGE44$ | $IMAGE45$ | $IMAGE46$ | $IMAGE47$ |
| $IMAGE48$ | $IMAGE49$ | $IMAGE50$ | $IMAGE51$ |
| $IMAGE52$ | $IMAGE53$ | $IMAGE54$ | $IMAGE55$ |
Мультиплікативною інверсією для $IMAGE47$ є
$IMAGE57$
Дійсно $IMAGE58$.
Нормальний базис (НБ) над полем $IMAGE14$ визначається як множина сполучених елементів поля $IMAGE60$ з підходящим вибором елемента $IMAGE61$. Розглянемо далі властивості НБ $IMAGE62$ над полем $IMAGE10$. На елемент $IMAGE61$ тут накладається необхідна умова: $IMAGE65$. Водночас $IMAGE61$ не обов'язково має бути примітивним. У будь-якому полі $IMAGE67$ існує елемент зі слідом 1, тому в будь-якому полі $IMAGE67$ існує і НБ. Елементи НБ можна подати $IMAGE13$-вимірними векторами.
$IMAGE70$
Зазначимо, що молодший розряд НБ звичайно записується ліворуч (на відміну від поліноміального, у якому молодший розряд прийнято записувати праворуч).
Кожен наступний елемент базису є циклічним зсувом вправо попереднього. Оскільки $IMAGE71$, елемент 1 поля $IMAGE67$ визначається координатами $IMAGE73$. Як бачимо, векторне подання елемента 1 поля $IMAGE67$ в поліноміальному і нормальному базисах різні.
Для порівняння двійкове подання елементів у поліноміальному і нормальному базисах подано в таблиці 3.
Таблиця 2 - Двійкове подання елементів у поліноміальному і нормальному базисах
| $IMAGE75$ | $IMAGE76$ | $IMAGE77$ | $IMAGE75$ | $IMAGE76$ | $IMAGE77$ |
| 0 | 0000 | 0000 | $IMAGE81$ | 1011 | 1110 |
| 1 | 0001 | 1111 | $IMAGE82$ | 0101 | 0011 |
| $IMAGE31$ | 0010 | 1001 | |