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

Цих вікон достатньо для формування числа

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

У загальному випадку в пам'яті зберігається

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

Алгоритм 4.

Вхід:

Вихід:

1.

2.

3.

3.1

3.2

4.

.

Нехай, наприклад,

при цьому й Використання трійкового вимагає, мабуть, двох додавань точок, тоді як у другому випадку за рахунок попереднього розрахунку точки достатньо одного додавання. Число подвоєнь однаково в обох випадках. Зрозуміло також, що виграш за рахунок вікна з'являється лише при порівняно більших довжинах числа

Перший крок алгоритму 4 у загальному випадку вимагає

групових операцій із точками кривої. На третьому кроці складність обчислень оцінюється середнім числом групових операцій додавання й подвоєння. Збільшення ширини вікна веде до збільшення складності обчислень на першому кроці (і об'єму пам'яті) і зниження тимчасової складності на третьому кроці. Для значень розширення поля порядку 180-260 оптимальним виявляється вікно шириною , а при - вікно шириною

Метод Монтгомері

Розглянемо метод Монтгомері. Нехай

з Позначимо Можна перевірити, що

(1)

Отже, знаючи

- координати точок й , можна обчислити координати точок й , перейти до пари , або до пари .

Кожна така ітерація вимагає одного подвоєння й одного додавання з використанням формули (1).

Після останньої ітерації,

- координата точки може бути відновлена з - координати точки й - координат точок і за формулою

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

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

Алгоритм 5. Метод експоненціювання Монтгомері.

Вхід:

Вихід:

1.

2.

2.1

3.1

3.2

4.

Алгоритм 5 вимагає однієї інверсії, а не двох, тому що можна обчислити

, а потім отримати множенням на . Можна домогтися істотного збільшення продуктивності, якщо операцію подвоєння замінити операцією ділення точки на два. Виграш до 40% при цьому досягається у зв'язку з відсутністю операції інверсії елемента в полі. Крім того, групові операції послідовних ділень у НБ зводяться практично до однієї операції множення в полі.

Методи експоненціювання при фіксованій точці

Фіксованою точкою в криптосистемі завжди є генератор або базова точка криптосистеми порядку

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