Складність деяких методів експоненціювання точки кривої (стр. 3 из 3)

Другим досить витонченим підходом є підхід на основі вікон з фіксованою базою. Замість двійкового подання числа використовується

-е із передобчислюванням точок . Дійсно, нехай -е подання числа має вигляд

Тоді

де

Ці обчислення здійснюються за допомогою наступного алгоритму.

Алгоритм 6.

Вхід: ширина вікна

, ,

Вихід:

1. Передрозрахунки:

2.

3.

3.1

3.2

4.

Середня обчислювальна складність алгоритму оцінюється кількістю додавань :

.

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

шириною кожне можна подати у вигляді:

;

Всі можливі точки

й обчислюються на етапі передрозрахунків і записуються на згадку. Загальна кількість цих точок зростає експоненційно зі збільшенням ширини вікна . Двійкове подання точки розбивається далі на фрагментів шириною . У кожному такому фрагменті відбираються старші розряди й розряди зі зрушенням вправо на (тобто на половину фрагмента).

Їхні двійкові подання дають першу пару точок

й , які складаються, після чого їхня сума подвоюється.

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

Алгоритм 7.

Вхід: ширина вікна

, , ,

Вихід:

1. Передрозрахунки: обчислити всі точки

й

,

2. Подати число

у вигляді конкатенації фрагментів шириною

Нехай означає й біт фрагмента

3.

4.

4.1

4.2

5.

Обчислювальна складність цього алгоритму оцінюється числом групових операцій

Обмінюючи час обчислень на пам'ять, можна й далі підвищувати продуктивність експоненціювання точки кривої. Наприклад, для кожного вікна шириною

можна заздалегідь розрахувати точок, при цьому на згадку рийдеться записати точок. Операція подвоєння в цьому випадку не використовується, а складність оцінюється числом додавань. Цей алгоритм назвемо алгоритмом максимальної пам'яті. У табл.13.1 дані для порівняння величини пам'яті й тимчасової складності (числа групових операцій) алгоритму 6 й алгоритму максимальної пам'яті при . В обох випадках зі збільшенням ширини вікна збільшується пам'ять і знижується число групових операцій. Очевидно, що останній алгоритм за наявності більших резервів пам'яті дозволяє істотно прискорити операцію експоненціювання фіксованої точки

Таблиця 1 - Об'єм пам'яті

й тимчасова складність (число групових операцій) алгоритму 6 й алгоритму максимальної пам'яті при

Метод	W = 3		W = 4		W = 5		W = 6
M	S	M	S	M	S	M	S
Алгоритм 6	14	900	30	725	62	632	126	529
Алгоритммаксимальної пам'яті.	469	58	750	46	1280	38	2079	33