сел, для DL - проблема дискретного логарифмування, а для EC - проблема дискретного логарифмування для еліптичних кривих. Складність цих завдань безпосередньо позначається на продуктивності, так як вона визначає необхідний розмір параметрів шифрування і ключа, що в свою чергу позначається на продуктивності всього алгоритму в цілому. p align="justify">
Алгоритми рішення задачі факторизації цілих чисел . Окремим випадком проблеми факторизації цілих чисел є завдання розкладання цілого числа n на два простих числа розміру l /2 біт. Розмір вхідних даних - O (l) біт. Найшвидший відомий алгоритм факторизації n - Number Field Sieve < span align = "justify"> (NFS) має субекспотенціальное очікуваний час роботи .
L n [1/3, 1.923] , де L n [a, c] = O ( )
Алгоритми рішення задачі дискретного логарифмування. У задачі дискретного логарифмування параметрами є числа p і q , де p - просте число розміром l біт і q - простий дільник числа p-1 розміру t . Розмір вхідних даних дорівнює O (l) біт. Найшвидшими алгоритмами вирішення такого завдання є Number Field Sieve (NFS) з очікуваним часом роботи L n [1/3, 1.923] і Pollard s rho algorithm з очікуваним часом роботи
В
Вибір найбільш ефективного алгоритму залежить від розміру вхідних даних.
Алгоритми для вирішення задачі дискретного логарифмування еліптичних кривих. Метою завдання є ціле число d ? [1, n? 1], таке, що Q = dP, де n - просте число розміром t біт , P - точка порядку n еліптичної кривої над полем GF (p), і Q належить циклічної підгрупі, пор...
