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