Название: Сліди і базиси розширеного поля
Вид работы: реферат
Рубрика: Математика
Размер файла: 114.14 Kb
Скачать файл: referat.me-217769.docx
Краткое описание работы: Методика проведення операції в розширених полях. Сліди і базиси розширеного поля. Двійкове подання елементів у поліноміальному і нормальному базисах. Подання точок кривої у різних координатних системах. Складність арифметичних операцій у групах точок ЕК.
Сліди і базиси розширеного поля
Сліди і базиси розширеного поля. Подання точок кривоїу різних координатних системах. Складність арифметичних операцій у групах точок ЕК
Від ідеї створення криптосистем на еліптичних кривих () до сьогоднішнього дня поряд із криптоаналізом цих систем фахівці безупинно і плідно працюють над підвищенням ефективності
.
Насамперед це відноситься до швидкодії криптосистеми або швидкості обчислень. Одним з напрямків робіт у цій сфері було вивчення і порівняльний аналіз арифметики в поліноміальному і нормальному базисах поля .
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 Дійсно
На наступній лекції ми розглядатимемо окремо т.з. оптимальний нормальний базис, який має значні переваги у швидкості та технологічності обчислень.
Під час обчислення точок з багаторазовими операціями додавання (віднімання) і подвоєння більш продуктивними є групові операції не в афінних координатах, а різного роду проективних координатах. Це дозволяє уникнути обчислення оберненого елемента в полі як самої трудомісткої операції й заощадити тимчасові обчислювальні ресурси.
У стандартних проективних координатах проективна точка ,
, відповідає афінній точці
Однорідне рівняння кривої після заміни змінних і множення на куб перемінної
приймає вигляд
(в афінних координатах рівняння кривої має вигляд
).
Точка на нескінченності є вже одним з розв’язків даного рівняння. Зворотна точка тут, як і раніше, визначається інверсією знака
координати
Подібно тому, як в афінних координатах, сумою точок і
при
називається точка
, координати якої (позначення
надалі опускається для скорочення запису) рівні:
де
Операцію підсумовування однакових точок називають подвоєнням, а координати точки
дорівнюють:
де
Час виконання операції додавання і подвоєння
, де
позначає проективне подання точки.
Наступний вид проективних координат - якобіанові координати.
До них можна перейти ізоморфним перетворенням координат, помноживши рівняння на
, при цьому отримаємо:
або
де
Сумою точок і
при
є точка
, координати якої визначаються як:
де
При подвоєнні точки кривої отримаємо :
де .
У даному випадку час виконання складає і
, де
позначає якобіаново подання точки.
Замість трьох якобіанових координат точки Чудновський запропонував використовувати п'ять: Рівняння кривої описується формулою
, а сума точок
і
при визначається як точка
, координати Чудновського якої рівні:
Де
При подвоєнні точки кривої одержимо
:
де .
Час виконання складе і
, де
означає подання точки в координатах Чудновського.
Модифіковані якобіанові координати для рівняння
кривої містять чотири координати
Сума точок і
при
визначається як точка
, модифіковані якобіанові координати якої дорівнюють:
,
де
При подвоєнні точки кривої отримаємо
де
Нарешті, можна зробити наступні оцінки. Час виконання дорівнює і
, де
означає подання точки в модифікованих якобіанових координатах.
Формули, що визначають сумарне число інверсій (
), множень
і піднесень до квадрата
при додаванні і подвоєнні точок відповідно в афінних
, проективних
, якобіанових
координатах, координатах Чудновського
і модифікованих якобіанових координатах
наведені в таблиці 1 (узагальнення).
За деякими оцінками, одна інверсія , а піднесення до квадрата
(при операціях у простому полі Галуа). Звідси стає зрозумілою доцільність переходу до проективних або до якобіанових координат, у яких операції інверсії відсутні.
Мінімальна обчислювальна складність додавання досягається за допомогою координат чудновського, а подвоєння – у модифікованих якобіанових координатах. Тому, звичайно, користуються змішаними координатами з метою оптимізації обчислень при багаторазовому додаванні точки.
Таблиця 3 - Число операцій множення , піднесення до квадрата
й інверсій
елементів простого поля при додаванні і подвоєнні точок у різних координатних системах
Координати | Додавання точок | Подвоєння точок |
Афінні | ![]() |
![]() |
Проективні | ![]() |
![]() |
Якобіанові | ![]() |
![]() |
Чудновського | ![]() |
![]() |
Модифіковані Якобіанові |
![]() |
![]() |
Після обчислення точки у змішаних координатах необхідно повернутися в афінні координати, для чого наприкінці обчислень потрібна одна інверсія.
Похожие работы
-
Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчисл
Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчислень Ефективний шлях багаторазового зведення за модулем – використання методу Монтгомері, який було запропоновано в 1985 році. Цей метод особливо ефективний при апаратній реалізації алгоритмів. Дуже зручно відмовитися від операцій множення і ділення та замінити їх операціями додавання.
-
Інтегральні характеристики векторних полів
інтегральні характеристики векторних полів 1. Диференціальні операції другого порядку Нехай в області задані скалярне поле і векторне поле , причому функції
-
Проблема дискретного логарифмування
Проблема дискретного логарифмування В пошуках криптографічних алгоритмів з відкритим розповсюдженням ключів з експоненціальною складністю криптоаналізу спеціалісти зупинилися на криптографічних перетвореннях, що виконуються в групі точок ЕК.
-
Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої
Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої 1. Методи Полларда Розглядаючи метод Полларда для вирішення проблеми дискретного логарифмування розв'яжемо наступну задачу.
-
Методи вирішення проблем дискретного логарифмування
Методи вирішення проблем дискретного логарифмування 1. Метод Поліга-Хелмана Метод Поліга-Хелмана запропонований в 1978 році для визначення дискретного логарифма в мультиплікативній групі поля
-
Дослідження кривої й форми поверхні другого порядку
Курсова робота Дослідження кривої й форми поверхні другого порядку Зміст ВВЕДЕННЯ ДОСЛІДЖЕННЯ КРИВОЇ ДРУГОГО ПОРЯДКУ Теоретична частина Практична частина
-
Побудова зображень предметів на площині
Сутність методу проекціювання. Центральні та паралельні проекції. Переваги ортогонального проекціювання перед центральним та косокутним. Положення геометричної фігури в просторі і виявлення її форми по ортогональних проекціях. Закони побудови зображень.
-
Складність деяких методів експоненціювання точки кривої
Найпоширенішою операцією у всіх криптографічних алгоритмах є - кратне додавання точки , позначуване як Цю операцію звичайно називають скалярним множенням, або, звертаючись до термінології мультиплікативної групи, експоненціюванням точки кривої.
-
Побудова скінченних множин
Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
-
Представлення і перетворення фігур
ПРЕДСТАВЛЕННЯ І ПЕРЕТВОРЕННЯ ТОЧОК Представлення точок здійснюється наступним чином: На площині У просторі Перетворення точок. Розглянемо результати матричного множення