Реферат: Складність деяких методів експоненціювання точки кривої

--PAGE_BREAK--Метод вікон з алгоритмом подвоєння — додавання — віднімання


Якщо в криптосистемі є резерви пам'яті, їх можна задіяти для подальшого збільшення швидкості обчислень. Ідея в тому, що замість точки <img width=«17» height=«19» src=«ref-1_1631212017-95.coolpic» v:shapes="_x0000_i1095"> можна експоненціювати і надалі складати суміжні блоки або вікна шириною <img width=«17» height=«16» src=«ref-1_1631229679-92.coolpic» v:shapes="_x0000_i1096"> в <img width=«43» height=«20» src=«ref-1_1631227660-138.coolpic» v:shapes="_x0000_i1097">  — поданні точки <img width=«28» height=«20» src=«ref-1_1631212112-122.coolpic» v:shapes="_x0000_i1098">

Для цього розраховується за допомогою алгоритму 2 трійкове число <img width=«67» height=«24» src=«ref-1_1631219724-303.coolpic» v:shapes="_x0000_i1099">, що потім може розбиватися на блоки довжиною, не менше <img width=«20» height=«16» src=«ref-1_1631230334-103.coolpic» v:shapes="_x0000_i1100">

Назвемо <img width=«17» height=«16» src=«ref-1_1631229679-92.coolpic» v:shapes="_x0000_i1101">  — вікном числа <img width=«148» height=«55» src=«ref-1_1631230529-622.coolpic» v:shapes="_x0000_i1102">непарний коефіцієнт <img width=«120» height=«31» src=«ref-1_1631231151-402.coolpic» v:shapes="_x0000_i1103"> утримуючий хоча б один ненульовий елемент. Зазначимо, що <img width=«88» height=«25» src=«ref-1_1631231553-329.coolpic» v:shapes="_x0000_i1104"><img width=«67» height=«24» src=«ref-1_1631219724-303.coolpic» v:shapes="_x0000_i1105">. Наприклад, при <img width=«45» height=«20» src=«ref-1_1631232185-187.coolpic» v:shapes="_x0000_i1106"> маємо вісім різних значень <img width=«28» height=«25» src=«ref-1_1631232372-126.coolpic» v:shapes="_x0000_i1107">
<img width=«305» height=«111» src=«ref-1_1631232498-2665.coolpic» v:shapes="_x0000_i1108">
Цих вікон достатньо для формування числа <img width=«67» height=«24» src=«ref-1_1631219724-303.coolpic» v:shapes="_x0000_i1109"> довільної довжини <img width=«16» height=«19» src=«ref-1_1631228662-92.coolpic» v:shapes="_x0000_i1110">. Зазначимо, що парні коефіцієнти в <img width=«43» height=«20» src=«ref-1_1631227660-138.coolpic» v:shapes="_x0000_i1111">  — поданні числа <img width=«15» height=«20» src=«ref-1_1631211923-94.coolpic» v:shapes="_x0000_i1112"> надлишкові, тому що вони утворяться подвоєнням непарних. На першому етапі передрозрахунків розраховуються й записуються на згадку вісім точок:<img width=«105» height=«23» src=«ref-1_1631235790-344.coolpic» v:shapes="_x0000_i1113"> і <img width=«45» height=«20» src=«ref-1_1631236134-195.coolpic» v:shapes="_x0000_i1114">

У загальному випадку в пам'яті зберігається <img width=«37» height=«24» src=«ref-1_1631236329-202.coolpic» v:shapes="_x0000_i1115"> точок. Число <img width=«76» height=«25» src=«ref-1_1631236531-317.coolpic» v:shapes="_x0000_i1116"> може бути визначене за допомогою модифікованого алгоритму 2. Модифікація полягає в тому, що:на кроці 2.1 замість <img width=«163» height=«25» src=«ref-1_1631236848-530.coolpic» v:shapes="_x0000_i1117"> необхідно записати <img width=«144» height=«29» src=«ref-1_1631237378-452.coolpic» v:shapes="_x0000_i1118">, де <img width=«83» height=«25» src=«ref-1_1631237830-338.coolpic» v:shapes="_x0000_i1119"> означає ціле число <img width=«103» height=«25» src=«ref-1_1631238168-360.coolpic» v:shapes="_x0000_i1120">, певне в інтервалі <img width=«135» height=«25» src=«ref-1_1631238528-335.coolpic» v:shapes="_x0000_i1121">. Далі обчислюється точка <img width=«25» height=«20» src=«ref-1_1631212234-112.coolpic» v:shapes="_x0000_i1122"> згідно з алгоритмом 4.

Алгоритм 4.

Вхід:<img width=«21» height=«19» src=«ref-1_1631238975-157.coolpic» v:shapes="_x0000_i1123"><img width=«196» height=«55» src=«ref-1_1631239132-738.coolpic» v:shapes="_x0000_i1124">

Вихід:<img width=«28» height=«20» src=«ref-1_1631212112-122.coolpic» v:shapes="_x0000_i1125">

1. <img width=«209» height=«29» src=«ref-1_1631239992-538.coolpic» v:shapes="_x0000_i1126">

2. <img width=«60» height=«20» src=«ref-1_1631215588-207.coolpic» v:shapes="_x0000_i1127">

3. <img width=«196» height=«24» src=«ref-1_1631240737-407.coolpic» v:shapes="_x0000_i1128">

3.1 <img width=«69» height=«20» src=«ref-1_1631216201-248.coolpic» v:shapes="_x0000_i1129">

3.2 <img width=«137» height=«25» src=«ref-1_1631241392-357.coolpic» v:shapes="_x0000_i1130">

<img width=«245» height=«25» src=«ref-1_1631241749-499.coolpic» v:shapes="_x0000_i1131">

<img width=«148» height=«25» src=«ref-1_1631242248-269.coolpic» v:shapes="_x0000_i1132">

4. <img width=«85» height=«24» src=«ref-1_1631216838-194.coolpic» v:shapes="_x0000_i1133">.

Нехай, наприклад,<img width=«113» height=«23» src=«ref-1_1631242711-390.coolpic» v:shapes="_x0000_i1134"> при цьому <img width=«219» height=«24» src=«ref-1_1631243101-814.coolpic» v:shapes="_x0000_i1135"> й <img width=«265» height=«25» src=«ref-1_1631243915-949.coolpic» v:shapes="_x0000_i1136"> Використання трійкового <img width=«67» height=«24» src=«ref-1_1631219724-303.coolpic» v:shapes="_x0000_i1137"> вимагає, мабуть, двох додавань точок, тоді як у другому випадку за рахунок попереднього розрахунку точки <img width=«41» height=«20» src=«ref-1_1631245167-182.coolpic» v:shapes="_x0000_i1138"> достатньо одного додавання. Число подвоєнь однаково в обох випадках. Зрозуміло також, що виграш за рахунок вікна з'являється лише при порівняно більших довжинах <img width=«16» height=«19» src=«ref-1_1631228662-92.coolpic» v:shapes="_x0000_i1139"> числа <img width=«17» height=«20» src=«ref-1_1631221776-106.coolpic» v:shapes="_x0000_i1140">

Перший крок алгоритму 4 у загальному випадку вимагає <img width=«133» height=«29» src=«ref-1_1631245547-440.coolpic» v:shapes="_x0000_i1141"> групових операцій із точками кривої. На третьому кроці складність обчислень оцінюється середнім числом <img width=«156» height=«25» src=«ref-1_1631245987-602.coolpic» v:shapes="_x0000_i1142"> групових операцій додавання й подвоєння. Збільшення ширини <img width=«17» height=«16» src=«ref-1_1631229679-92.coolpic» v:shapes="_x0000_i1143"> вікна веде до збільшення складності обчислень на першому кроці (і об'єму пам'яті) і зниження тимчасової складності на третьому кроці. Для значень <img width=«19» height=«16» src=«ref-1_1631246681-94.coolpic» v:shapes="_x0000_i1144"> розширення поля порядку 180-260 оптимальним виявляється вікно шириною <img width=«44» height=«20» src=«ref-1_1631246775-200.coolpic» v:shapes="_x0000_i1145">, а при <img width=«112» height=«20» src=«ref-1_1631246975-445.coolpic» v:shapes="_x0000_i1146">  — вікно шириною <img width=«49» height=«20» src=«ref-1_1631247420-220.coolpic» v:shapes="_x0000_i1147">
    продолжение
--PAGE_BREAK--