Реферат Сліди і базиси розширеного поля
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Сліди і базиси розширеного поля. Подання точок кривої у різних координатних системах. Складність арифметичних операцій у групах точок ЕК
Від ідеї створення криптосистем на еліптичних кривих (
Насамперед це відноситься до швидкодії криптосистеми або швидкості обчислень. Одним з напрямків робіт у цій сфері було вивчення і порівняльний аналіз арифметики в поліноміальному і нормальному базисах поля
1. Сліди і базиси розширеного поля
Операції в розширених полях вимагають введення таких понять, як слід елемента поля та базису поля.
Нехай
Слідом елемента
Зокрема, слід елемента над полем
Розширення поля Галуа
Теорема 1. Елементи
або визначник
Із множини всіляких базисів найбільш розповсюдженими є поліноміальний і нормальний базиси поля
Поліноміальний базис, звичайно, будується за допомогою послідовних степенів примітивного елемента поля
Примітивний елемент
Наприклад. Розглянемо поле
Таблиця 1.
| (0000) | (0001) | (0010) | (0011) | (0100) | (0101) | (0110) | (0111) |
| (1000) | (1001) | (1010) | (1011) | (1100) | (1101) | (1110) | (1111) |
Використовуємо при обчисленнях поліном
Додавання:
(0101)+(1101) = (1000).
Множення:
(0101)×(1101) =
Піднесення до степеня:
Таблиця 2 - Мультиплікативна інверсія
| | | | |
| | | | |
| | | | |
| | | | |
Мультиплікативною інверсією для
Дійсно
Нормальний базис (НБ) над полем
Зазначимо, що молодший розряд НБ звичайно записується ліворуч (на відміну від поліноміального, у якому молодший розряд прийнято записувати праворуч).
Кожен наступний елемент базису є циклічним зсувом вправо попереднього. Оскільки
Для порівняння двійкове подання елементів у поліноміальному і нормальному базисах подано в таблиці 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 – при непарній вазі. Ця властивість радикально спрощує визначення сліду елемента у НБ.
Наприклад: елемент
На наступній лекції ми розглядатимемо окремо т.з. оптимальний нормальний базис, який має значні переваги у швидкості та технологічності обчислень.
Під час обчислення точок з багаторазовими операціями додавання (віднімання) і подвоєння більш продуктивними є групові операції не в афінних координатах, а різного роду проективних координатах. Це дозволяє уникнути обчислення оберненого елемента в полі як самої трудомісткої операції й заощадити тимчасові обчислювальні ресурси.
У стандартних проективних координатах проективна точка
(в афінних координатах рівняння кривої має вигляд
Точка на нескінченності
Подібно тому, як в афінних координатах, сумою точок
де
Операцію підсумовування однакових точок
де
Час виконання операції додавання
Наступний вид проективних координат - якобіанові координати.
До них можна перейти ізоморфним перетворенням координат, помноживши рівняння
де
Сумою точок
де
При подвоєнні точки кривої отримаємо
де
У даному випадку час виконання складає
Замість трьох якобіанових координат точки Чудновський запропонував використовувати п'ять:
при
Де
При подвоєнні точки кривої одержимо
де
Час виконання складе
Модифіковані якобіанові координати для рівняння
кривої містять чотири координати
Сума точок
де
При подвоєнні точки кривої отримаємо
де
Нарешті, можна зробити наступні оцінки. Час виконання дорівнює
Формули, що визначають сумарне число
За деякими оцінками, одна інверсія
Мінімальна обчислювальна складність додавання досягається за допомогою координат чудновського, а подвоєння – у модифікованих якобіанових координатах. Тому, звичайно, користуються змішаними координатами з метою оптимізації обчислень при багаторазовому додаванні точки.
Таблиця 3 - Число операцій множення
| Координати | Додавання точок | Подвоєння точок |
| Афінні | | |
| Проективні | | |
| Якобіанові | | |
| Чудновського | | |
| Модифіковані Якобіанові | | |
Після обчислення точки
Размещено на Allbest.ru
