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

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

width="260" height="65" align="BOTTOM" border="0" /> (1)


Отже, знаючи Складність деяких методів експоненціювання точки кривої - координати точок Складність деяких методів експоненціювання точки кривої й Складність деяких методів експоненціювання точки кривої, можна обчислити Складність деяких методів експоненціювання точки кривої координати точок Складність деяких методів експоненціювання точки кривої й Складність деяких методів експоненціювання точки кривої, перейти до пари Складність деяких методів експоненціювання точки кривої, або до пари Складність деяких методів експоненціювання точки кривої.

Кожна така ітерація вимагає одного подвоєння й одного додавання з використанням формули (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 = 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

Размещено на

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: