Сліди і базиси розширеного поля
Методика проведення операції в розширених полях. Сліди і базиси розширеного поля. Двійкове подання елементів у поліноміальному і нормальному базисах. Подання точок кривої у різних координатних системах. Складність арифметичних операцій у групах точок ЕК.
Рубрика | Математика |
Вид | реферат |
Язык | украинский |
Дата добавления | 05.02.2011 |
Размер файла | 133,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Сліди і базиси розширеного поля. Подання точок кривої у різних координатних системах. Складність арифметичних операцій у групах точок ЕК
Від ідеї створення криптосистем на еліптичних кривих () до сьогоднішнього дня поряд із криптоаналізом цих систем фахівці безупинно і плідно працюють над підвищенням ефективності .
Насамперед це відноситься до швидкодії криптосистеми або швидкості обчислень. Одним з напрямків робіт у цій сфері було вивчення і порівняльний аналіз арифметики в поліноміальному і нормальному базисах поля .
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 Число операцій множення , піднесення до квадрата й інверсій елементів простого поля при додаванні і подвоєнні точок у різних координатних системах
Координати |
Додавання точок |
Подвоєння точок |
|
Афінні |
|||
Проективні |
|||
Якобіанові |
|||
Чудновського |
|||
Модифіковані Якобіанові |
Після обчислення точки у змішаних координатах необхідно повернутися в афінні координати, для чого наприкінці обчислень потрібна одна інверсія.
Размещено на Allbest.ru
Подобные документы
Використання методу Полларда для вирішення проблеми дискретного логарифмування, його складність і час обчислення рішення ECDLP. Аномальні криві й криві над розширеннями малого поля. MOV-атака та суперсингулярні криві над полем F. Метод спуску Вейля.
реферат [269,5 K], добавлен 21.02.2011Дослідження особливостей скалярного та векторного полів. Похідна за напрямом. Градієнт скалярного поля, потенціальне поле. Сутність дивергенції, яка характеризує густину джерел даного векторного поля в розглянутій точці. Ротор або вихор векторного поля.
реферат [244,3 K], добавлен 06.03.2011Огляд проблеми дискретного логарифмування в групі точок еліптичної кривої. Сутність та сфера використання методу Поліга-Хелмана. Особливості використання методу ділення точок на два. Можливі підходи і приклади розв’язання задач дискретного логарифмування.
реферат [112,8 K], добавлен 09.02.2011Диференціальні операції другого порядку. Потік векторного поля. Формула Остроградського-Гаусса в векторній формі. Властивості соленоїдального поля. Інваріантне означення дивергенції. Формула Стокса у векторній формі. Властивості потенціального поля.
реферат [237,9 K], добавлен 15.03.2011Вимоги до ставлення цілей викладання геометрії в загальноосвітній школі. Суть методу координат на площині та його основні задачі стосовно геометричних місць точок. Афінна система координат. Елементи використання на практиці важливих точок трикутника.
дипломная работа [1,4 M], добавлен 04.08.2013Изложение теории поля с помощью векторного анализа и составление пособия. Циркуляция векторного поля. Оператор Гамильтона и векторные дифференциальные операции второго порядка. Простейшие векторные поля. Применение теории поля в инженерных задачах.
дипломная работа [190,2 K], добавлен 09.10.2011Операции в скалярных и векторных полях. Наиболее распространенные типы векторных полей и задачи, которые возникают при изучении этих полей. Потенциальное, гармоническое и соленоидальное векторное поле. Векторный потенциал поля. Задачи Дирихле и Неймана.
курсовая работа [294,8 K], добавлен 07.11.2013Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
задача [112,0 K], добавлен 23.06.2010Беселеві функції з будь-яким індексом, з напівцілим індексом. Формули приведення для Беселевих функцій. Інтегральне подання функцій із цілим індексом. Ряди Фур'є-Беселя. Асимптотичне подання функцій із цілим індексом для більших значень аргументу.
курсовая работа [211,7 K], добавлен 28.12.2010Конструкции и свойства конечных полей. Понятие степени расширения, определенность поля разложения, примитивного элемента, строение конечной мультипликативной подгруппы поля. Составление программы, которая позволяет проверить функцию на примитивность.
курсовая работа [19,2 K], добавлен 18.12.2011