Огляд проблеми дискретного логарифмування в групі точок еліптичної кривої. Сутність та сфера використання методу Поліга-Хелмана. Особливості використання методу ділення точок на два. Можливі підходи і приклади розв’язання задач дискретного логарифмування.
Аннотация к работе
Він заснований на відомій для групи факторизації порядку групи за ступенями простих чисел Стосовно до адитивної групи точок з генератором порядку маємо Відповідно до відомої китайської теореми про залишки існує єдине натуральне число , таке що Після визначення значення дискретний логарифм здобувають за допомогою розширеного алгоритму Евкліда. Приклад 1 Нехай порядок циклічної групи дорівнює , а точка , тобто . Метод ділення точок на два Метод ділення точок на два. Якщо частка парна, ділення триває, у протилежному випадку виконується віднімання 1 і ділення на 2 (отримуємо наступний розряд числа рівний відповідно 0 або 1). Під час виконання (4) отримуємо дві точки: і ділення точки на два з координатами (5) З (1) і (5) неважко отримати співвідношення між координатами точок ділення які можуть бути корисні при криптоаналізі.