Материалы что дал Мухачев / Материалы что дал Мухачев / проективні_координати

3.1.1 Представлення точок еліптичній кривій над полем в проективних координатах

Для невиродженої кривої над полем , , яка задається рівнянням , , комутативний груповий закон з нейтральним елементом О в афінних координатах має наступні властивості [1]:

а) для всіх ;

б) якщо , то ; для всіх ;

в) якщо - скінченні точки, такі, що , і , а , то

, ;

г) якщо - скінченні точки, а , то

, ;

д) якщо знаменник дорівнює нулю, то результатом операції є .

Для невиродженої кривої над полем , яка задається рівнянням , , властивості груповий закону з нейтральним елементом О в афінних координатах наступні [1]:

а) для всіх ;

б) якщо , то ; для всіх ;

в) якщо - скінченні точки, такі, що , і , а , то

, ;

г) якщо - скінченні точки, а , то

, ;

д) якщо знаменник дорівнює нулю, то результатом операції є .

Операцію додавання двох однакових точок називають подвоєнням точки .

При дослідженні властивостей еліптичної кривої природнім є запис координат її точок у проективних координатах, оскільки при цьому аналітичний вираз групового закону приймає загальний вид і всі точки кривої стають рівноправними при виконанні групової операції.

Зокрема, виявляєтся, що довільну точку кривої можна вибрати у якості нейтрального елемента групи .

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

Нагадаємо, що за деякими оцінками [1], одна інверсія за затратами часу еквівалентна I=80М, де М - час виконання операції множення у простому полі.

Якщо згадати, що серед розв’язків рівняння еліптичної кривої відсутня точка , то стає очевидним, що для рівнопровності всіх точек групи необхідно розглядати деяке узагальнення рівняння, розв’язки якого утворювали б групу ізоморфну групі точок еліптичної кривої яку ми побудували, виходячи з так званого афінного рівняння і приєднання нескінченно віддаленої точки .

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

Виявляється, що розв’язки проективного рівняння можна розбити на класи еквівалентності. Ці класи утворюють групу, ізоморфну групі точок еліптичної кривої з приєднаною точкою . З іншого боку, ці класи становлять елементи відомої структури – проективного простору розмірності над полем . Проективний простір можно побудувати з афінного простору розмірності приєднанням додаткової координати, що відображено у позначенні .

Афінний та проективний простори розглядаються як множини загального виду, тобто як сукупність відповідних елементів без додаткової структури.

У нашому випадку простір будується на основі множини , що складається з усих трійок чисел, що належать виду , крім . Єлементи і множини вважаються еквівалентними, якщо існує , такий, що .

Таким чином, клас еквівалентності, що містить елемент , нагадує пряму з направляючим вектором , який виходить з початку координат і породжує цю пряму. Очевидно, довільний вектор класу можна взяти як породжуючий.

Клас еквівалентності, що містить позначається як .

Класи еквівалентності складають проективний простір і називаються його точками.

Зауважимо, що у випадку, коли задовільняє рівняння , то всі елементи виду , , також є розв’язками цього рівняння.

Таким чином, розв’язки проективного рівняння можна розглядати у проективному просторі.

Нехай - розв’язок проективного рівняння і .

Тоді і розв’язки афінного рівняння , відповідають розв’язкам проективного рівняня.

Якщо , то у афінного рівняння розв’язків немає, а проективне рівняння зводиться до , що дає один розв’язок виду , з довільним , тобто . Таким чином, .

3.1.2 Груповий закон в стандартних проективних координатах

В стандартних проективних координатах рівняння кривої над має вигляд

.

Точка , , відповідає афінній точці , точка .

Якщо , то .

У випадку коли , , , координати суми обчислюються за такими правилами [1]:

, , , де

, , .

Обчислення подвоєнної точки виконується наступним чином [1]:

, , , де

, , , .

3.1.3 Груповий закон в якобієвих координатах

Перехід рівняння кривої над у якобієвих проективних координатах можна здійснити за допомогою множення обох частин афінного рівняння на . Таким чином, отримаємо , або

, де , .

При додаванні точок , , , координати суми можна знайти за наступними формулами [1]:

, , , де

, , , , , .

Формули подвоєння точки наступні :

, , , де

, , .

3.1.4 Груповий закон в координатах Чудновських

Операції у якобієвих проективних координатах можна дещо прискорити за рахунок попереднього обчислення деяких величин, пов’язаних з координатами, якщо врахувати, що при пересилці координат точок іншим абонентам передавати додаткову інформацію, то це дозволяє ім не обраховувати деяки проміжні обчислення, що підвищує у цілому ефективність системи.

Брати Чудновські запропонували додавати до трьох якобієвих координат точки додаткову інформацію і працювати з точками виду [1].

При додаванні точок , , , координати суми задаються наступним чином.

, , , , , де

, , , , , .

Запис координат точки аналогічний:

, , , , , де

, , .

Нехай . Підрахуємо, скільки операцій множення та піднесення до квадрату потрібно для знаходження .

Для обчислення потрібно обчислити , тобто ,що потребує два множення. Для обчислення треба виконати одне піднесення до квадрату та одне множення. Очевидно, , як і інші потрібні проміжні результати можна зберігати в пам’яті машини.

Добуток множимо на 2 – ще два множення. Ще одне піднесення до квадрату додає обчислення . Таким чином, для обчислення потрібно 5 множень і 2 піднесення до степеня.

Аналогічно, можна підрахувати затрати часу щодо обчислення і отримати сумарну оцінку для кількості операцій множення (M) та піднесення до квадрату (S) необхідних для обчислення коодинат Чудновських: .

З таблиці таблиці 3.1, яка запозичена з [1] видно, що за рахунок інверсії перетворення в афінних координатах суттєво програють у часі перетворенням у проективних координатах.

Крім того, мінімальні затрати часу на додавання у випадку різних точок дають координати Чудновських, а подвоєння точки найскоріше виконується в якобієвих координатах.

Тому слід користуватися змішаними координатами з метою оптимізації обчислень скалярного добутку .

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

Таблиця 3.1- Складність операцій на еліптичній кривій

Координати	Додавання точок	Подвоєння точок
Афінні	I+2M+S	I+2M+S
Проективні	12M+2S	7M+5S
Якобієві	12M+4S	4M+6S
Чудновських	11M+3S	5M+6S