Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Сліди і базиси розширеного поля

Название: Сліди і базиси розширеного поля
Раздел: Рефераты по математике
Тип: реферат Добавлен 02:53:47 05 февраля 2011 Похожие работы
Просмотров: 13 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Сліди і базиси розширеного поля. Подання точок кривоїу різних координатних системах. Складність арифметичних операцій у групах точок ЕК


Від ідеї створення криптосистем на еліптичних кривих () до сьогоднішнього дня поряд із криптоаналізом цих систем фахівці безупинно і плідно працюють над підвищенням ефективності .

Насамперед це відноситься до швидкодії криптосистеми або швидкості обчислень. Одним з напрямків робіт у цій сфері було вивчення і порівняльний аналіз арифметики в поліноміальному і нормальному базисах поля .

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 - Число операцій множення , піднесення до квадрата й інверсій елементів простого поля при додаванні і подвоєнні точок у різних координатних системах

Координати Додавання точок Подвоєння точок
Афінні
Проективні
Якобіанові
Чудновського

Модифіковані

Якобіанові

Після обчислення точки у змішаних координатах необхідно повернутися в афінні координати, для чого наприкінці обчислень потрібна одна інверсія.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:09:15 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
09:31:48 29 ноября 2015

Работы, похожие на Реферат: Сліди і базиси розширеного поля

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150942)
Комментарии (1842)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru