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

Алгоритм 6.

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

Вихід:

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

2.

3.

3.1

3.2

4.

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

.

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

;

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

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

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

Алгоритм 7 .

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

Вихід:

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

,

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

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

3.

4.

4.1

4.2

5.