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

Контрольная работа - Математика и статистика

Другие контрольные работы по предмету Математика и статистика

? й одного додавання з використанням формули (1).

Після останньої ітерації, - координата точки може бути відновлена з - координати точки й - координат точок і за формулою

 

 

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

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

Вхід

Вихід

 

1.

2.

2.1

3.1

3.2

4.

 

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

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

 

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

 

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

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

 

 

Тоді

 

де

 

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

Алгоритм 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 = 3W = 4W = 5W = 6MSMSMSMSАлгоритм 6149003072562632126529Алгоритм

максимальної памяті. 4695875046128038207933 A