Реферат: Методи вирішення проблем дискретного логарифмування

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

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

Якщо частка парна, ділення триває, у протилежному випадку виконується віднімання 1 і ділення на 2 (отримуємо наступний розряд числа рівний відповідно 0 або 1). Процедура триває до одержання частки, рівної 1. Якщо точка – генератор простого порядку , то при знанні відповіді на питання про парність (непарність) множника точки легко вирішується ( у поліноміальному часі ) описаною вище послідовною процедурою віднімання-ділення на два.

У простому полі ділення на два тотожно множення на елемент

Виявляється замість багаторазового додавання ділення точки на два виконується набагато ефективніше й швидше.

Визначимо порядок кривої як

де - велике просте число (в існуючих криптографічних стандартах ), - непарне число.

Нехай - точка порядку , тоді генератор криптосистеми може бути визначений як точка порядку .

Введемо операцію ділення точки несуперсингулярної кривої

: (1)

на два як зворотну подвоєнню. Нехай маємо точку та точку з координатами

(2)

Інакше кажучи, визначення означає знаходження координат точки з відомої точки Відповідно до (2) для цього необхідно вирішувати квадратне рівняння

(3)

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

(4)

Якщо слід то точка - непарна точка - непарне). Під час виконання (4) отримуємо дві точки: і ділення точки на два з координатами

(5)

З (1) і (5) неважко отримати співвідношення між координатами точок ділення

які можуть бути корисні при криптоаналізі. Відзначимо дві властивості точок ділення.

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

,

тому що

Якщо - точка непарного порядку , тобто , то точка