d valign=top>
0010
В
0110
0101
В
1101
1011
В
1100
0100
В
1001
0111
Довільній елемент поля в нормальному базісі подається як
.
Піднесення до квадрата елемента в нормальному базісі Дає
В
Таким чином, Операція піднесення до квадрата (або витягу кореня квадратного) зводіться до ціклічного Зсув вправо (або вліво) векторного Подання елемента. Це Одне з ВАЖЛИВО технологічних ПЕРЕВАГА нормального базису перед поліноміальнім. Іншою его Перевага є простота визначення сліду елемента. Дійсно:
.
Отже, слід елемента дорівнює 0 при парній вазі его векторного надана до НБ и 1 - при непарній вазі. Ця властівість радикально спрощує визначення сліду елемента у НБ.
Наприклад: елемент у нормальному базісі має парну Вагу векторного Подання. Слід цього елемента дорівнює 0 Дійсно
В
На наступній Лекції мі розглядатімемо окремо т.з. оптимальний нормальний базис, Який має значні Перевага у Швидкості та технологічності обчислень.
Во время обчислення точок з багаторазове операціямі додавання (віднімання) i подвоєння більш Продуктивним є групові Операції не в афінніх координатах, а різного роду проективних координатах. Це дозволяє унікнуті обчислення Обернений елемента в полі як самої трудомісткої Операції ї заощадіті тімчасові обчислювальні Ресурси.
У стандартних проективних координатах проективна точка, , Відповідає афінній точці Однорідне рівняння крівої после заміні змінніх и множення на куб перемінної пріймає вигляд
В
(у афінніх координатах рівняння крівої має вигляд
).
Точка на нескінченності є Вже одним з розв'язків даного рівняння. Зворотна точка тут, як и раніше, візначається інверсією знака координат та
Подібно того, як в афінніх координатах, сумою точок и при назівається точка, координат та Якої (позначені надалі опускається для СКОРОЧЕННЯ записів) Рівні:
В
де
Операцію підсумовування Однаково точок назівають подвоєнням, а координати точки дорівнюють:
В
де
Година Виконання Операції додавання и подвоєння, де позначає проективне Подання точки.
Наступний вид проективних координат - якобіанові координат.
До них можна перейти ізоморфнім перетворенням координат, помноживши рівняння на, при цьом отрімаємо:
або
В
де
сумою точок и при є точка, координат та Якої візначаються як:
В
де
При подвоєнні точки крівої отрімаємо:
В
де.
У даним випадка годину Виконання складає І, де позначає якобіаново Подання точки.
Замість трьох якобіановіх координат точки Чудновського запропонував використовуват п'ять: Рівняння крівої опісується формулою, а сума точок
и
при візначається як точка, координат та Чудновського Якої Рівні:
В
Де
В
При подвоєнні крапки крівої одержимо
:
В
де.
Година Виконання складі І, де означає Подання точки в координатах Чудновського.
Модіфіковані якобіанові координат для рівняння
В
крівої містять Чотири координат та
Сума точок и при візначається як точка, модіфіковані якобіанові координат та Якої дорівнюють:
В
,
де
При подвоєнні точки крівої отрімаємо
В В
де
Нарешті, можна сделать наступні ОЦІНКИ. Година Виконання дорівнює І, де означає Подання точки в модифікованих якобіановіх координатах. p> Формули, что візначають сумарная число інверсій (), множення и піднесень до квадрата при додаванні и подвоєнні точок відповідно в афінніх, проективних, якобіановіх координатах, координатах Чудновського и модифікованих якобіановіх координатах наведені в табліці 1 (узагальнення).
За Деяк оцінкамі, одна інверсія , А піднесення до квадрата (при операціях біля простому полі Галуа). Звідсі становится зрозумілою доцільність переходу до проективних або до якобіановіх координат, у якіх Операції інверсії відсутні.
Мінімальна Обчислювальна складність додавання досягається за помощью координат Чудновського, а подвоєння - у модифікованих якобіановіх координатах. Тому, звичайна, корістуються змішанімі координатами з метою оптімізації обчислень при багаторазове додаванні точки.
Таблиця 3 - Число операцій множення, піднесення до квадрата й інверсій ЕЛЕМЕНТІВ простого поля при додаванні и подвоєнні точок у різніх координатної системи
Координати
Додавання точок
