Факторизація за допомогою еліптичних кривих
Факторизація за допомогою еліптичних кривих(англ. elliptic curve factorization method , скор.ECM) абоМетод Ленстри факторизації за допомогою еліптичних кривих(англ. Lenstra elliptic curve factorization ) - алгоритм факторизації натурального числа з використанням еліптичних кривих. Цей алгоритм має субекспоненційну складність [1] . ECM є третім за швидкістю роботи [2] після загального методу решета числового поля та методу квадратичного решета.
Насправді найкраще підходить для знаходження невеликих простих дільників числа, і тому вважається вузькоспеціалізованим [3] алгоритмом.
Є кращим алгоритмом [4] для пошуку простих дільників довжини 20-25 знаків (розміром 64 ... 83 біт), тому що його складність в основному залежить від найменшого простого дільника p, а не від числа, що факторизується.
Часто використовується виявлення (відкидання) невеликих простих дільників числа. Якщо отримане після роботи алгоритму число все ще є складовим, то інші співмножники — великі числа, і для подальшого розкладання є сенс використовувати загальніші алгоритми факторизації.
Зміст
Алгоритм факторизації (знаходження нетривіального дільника) натурального числа n [6] :
Аналогічне твердження справедливе й у кривої по модулюq.
ECM є доопрацюванням старішого P-1 методу Полларда [7] . Алгоритмp− 1 знаходить такі прості дільникиp, що (p− 1) — B-гладке для деякого невеликогоB. Для будь-якогоe, кратного (p− 1) , і для будь-якогоa, взаємно простого зpза малою теорема Ферма вірно, щоae≡1(modp) . Тоді НОД(ae− 1,n) з великою ймовірністю буде дільникомn.Однак, Алгоритмp− 1 не спрацює [7] , коли уpє великі прості дільники. ECM у цьому випадку спрацює коректно, тому що замість розгляду мультиплікативної групи надZp, порядок якої завжди дорівнюєp− 1 , розглядається група випадкової еліптичної кривої над кінцевим полемZp.
Порядок групи точок, що лежать на еліптичній кривій E надZp, згідно з теоремою Хассі обмежений:p+ 1 − 2 √p≤ E ≤p+ 1 + 2 √p. Видається важливим дослідити [8] ймовірність того, що в цьому інтервалі може лежати деяке гладке число (у цьому випадку існують криві, порядок яких — гладке число). Не існує доказів того, що в інтервалі Хассе є завжди деяке гладке число, проте використанням евристичних імовірнісних методів, теореми Канфілда-Ердоса-Померанса (англ. Canfield-Erdős-Pomerance theorem) [9] та L-нотації виходить оцінка, що достатньо взятиL[ √ 2 /2, √ 2 ] кривих до отримання гладкого порядку групи. Це евристична оцінка добре застосовується практично.
Факторизація [10] числаn= 455839.
Вибирається еліптична крива та точка, що лежить на цій кривій
Послідовно обчислюється 10!P:
1. Обчислюються координати точки P 2 = 2! P = 2 P = 2! P = 2P & gt; .
- Тангенс кута нахилу дотичної в точці 2Pстановить
Якщо порівнювати метод еліптичних кривих коїться з іншими методами факторизації, цей метод належить до класу субэкспоненциальных [1] методів факторизації, отже, працює швидше будь-якого експоненціального методу. Якщо порівнювати його з методом квадратичного решета (QS) та методом решета числового поля (NFS), то все залежить від розміру найменшого дільника числаn[12] . Якщо числоnвибрано як у RSA у вигляді добутку двох простих чисел приблизно однакової довжини, то метод еліптичних кривих має ту ж оцінку, що і метод квадратичного решета, але поступається методу решета числового поля [13] .
Використання кривих Едвардса дозволяє [15] знизити кількість модульних операцій та зменшити час виконання алгоритму порівняно з еліптичними кривими у формі Вейєрштраса ( y 2 = x 3 + a x + b ( mod p ) =x^+ax+b> у формі Монтгомері (B y 2 = x 3 + A x 2 + x = x^+Ax^+x>).
Операція додавання: Закон додавання задається формулою ( e , f ) , ( g , h ) ↦ ( e h + f g 1 + d e g f h , f h − e g 1 − d e g f h ) >,>\right)> .
Точка (0,1) - це нейтральний елемент, а зворотна до точки (e, f) це (-e, f).
Інші форми виходять аналогічно тому, як проективна крива Вейєрштраса виходить зафінною кривою.
a ( 1 / u ) = − a ( u ) , b ( 1 / u ) = b ( u ) , d ( 1 / u ) = d ( u )