Факторизація за допомогою еліптичних кривих ( англ. elliptic curve method , Скор. ECM) - алгоритм факторизації натурального числа з використанням еліптичних кривих. Даний алгоритм має субекспоненціальное час виконання. Є третім за швидкістю роботи після загального методу решета числового поля та методу квадратичного решета.

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


1. Алгоритм

Дано складене ціле непарне число n . Потрібно знайти його нетривіальний дільник d , 1 <d <n .

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

E \ colon \ quad y ^ 2 = x ^ 3 + ax + b,

де a, b \ in \ mathbb {Z} _n , І деяка точка P = \ left ({x, y} \ right) на ній. Якщо спроба розкладання виявиться невдалою, слід взяти інші E і P і повторити алгоритм спочатку.

1. Вибирається ціле число k , Делящееся на ступені малих простих чисел (не більших деякого B ), Не переважаючих C , Тобто

k = \ prod_ {\ ell \ le B} \ ell ^ {\ alpha_i},

де \ Alpha_i = \ left \ lfloor \ log_ {\ ell} C \ right \ rfloor - Найбільший із можливих показників, при якому \ Ell ^ {\ alpha_i} \ le C .

2. Обчислення kP (Всі дії проводяться за модулем n)

kP = \ underbrace {P \ boxplus \ dots \ boxplus P} _k,

де \ Boxplus - Операція складання, визначена за груповому законом.

Обчислення проводяться до тих пір, поки при спробі знайти число, протилежне до 2y_p (Див. груповий закон) не з'являється число, не взаємно просте з n . Це відбудеться при такому k = k_1 , Що k_1 P = O , Тобто порядок P в групі E по модулю n є дільником k_1 .

3. При застосуванні алгоритму Евкліда замість звернення знаменника по модулю n, отримуємо нетривіальний найбільший спільний дільник цього знаменника і n, тобто, власний дільник числа n.


2. Обгрунтування

Якщо числа p і q - два простих дільника числа n, то еліптична крива y 2 = x 3 + ax + b (mod n) відповідає двом еліптичним кривим: по модулю p і по модулю q. Ці дві криві із заданою операцією додавання точок утворюють групи, що містять N p і N q елементів, відповідно. За теоремі Лагранжа для будь-якої точки Р на вихідній кривій по модулю p з рівності kP = \ infty для мінімального позитивного числа k випливає, що k ділить N p (зокрема, N_p P = \ infty ). Аналогічне твердження справедливе і для кривої по модулю q. Для випадково вибраної еліптичної кривої порядки N p і N q є випадковими числами, близькими до p +1 і q + 1, відповідно (див. нижче). Тому малоймовірно, що більшість простих дільників N p і N q збігаються, і цілком імовірно, що при обчисленні eP ми зіткнемося з деякими kP = \ infty по модулю р, але не по модулю q, або навпаки. Якщо це так, то kP не існує на вихідній кривій, а в обчисленнях ми знайшли таке v, що або НОД (v, p) = p, або НОД (v, q) = q, але не одночасно. Тоді НСД (v, n) ​​є нетривіальним дільником числа n.


3. Приклад

Припустимо, нам потрібно факторізовать число n = 455839.

Візьмемо еліптичну криву і точку, що лежить на цій кривій

~ Y ^ 2 = x ^ 3 +5 x-5, ~ P ​​= (1, ~ 1).

Спробуємо обчислити 10! P:

1. Для початку обчислимо координати точки P_2 = 2! P = 2P .

  • Тангенс кута нахилу дотичної в точці P дорівнює:
~ S = \ frac {dy} {dx} = \ frac {3x ^ 2 +5} {2y} = 4.
  • Знаходимо координати точки P_2 :
~ X_2 = s ^ 2-2x_1 = 14 \ pmod {n},
~ Y_2 = s (x_1-x_2)-y = 4 (1-14) -1 = -53 \ pmod {n}. .
  • Перевіряємо, що точка 2P дійсно лежить на кривій:
(-53) ^ 2 = 2809 = 14 ^ 3 + 5 \ cdot14 - 5.

2. Тепер обчислимо P_3 = 3! P = 6P .

  • Тангенс кута нахилу дотичної в точці 2 P становить
~ S = (3 \ cdot142 +5) / (2 (-53)) = -593/106 = 322522 \ pmod {n} .
Для обчислення 593/106 по модулю n можна скористатися розширеним алгоритмом Евкліда : 455839 = 4300.106 + 39, далі 106 = 2.39 + 28, далі 39 = 28 + 11, далі 28 = 2.11 + 6, далі 11 = 6 + 5, далі 6 = 5 + 1 . Звідки отримуємо, що НОД (455839, 106) = 1, і у зворотний бік: 1 = 6 - 5 = 2.6 - 11 = 2.28 - 5.11 = 7.28 - 5.39 = 7.106 - 19.39 = 81707.106 - 19.455839. Звідки 1/106 = 81 707 (mod 455 839), таким чином, -593 / 106 = 322 522 (mod 455 839).
  • Враховуючи обчислене s, ми можемо обчислити координати точки 2 (2 P), так само, як це було зроблено вище: 4 P = (259851, 116255). Перевіряємо, що точка дійсно лежить на нашій еліптичної кривої.
  • Підсумовуючи 4 P і 2 P знаходимо P_3 = (195045, 123227) .

3. Аналогічним чином можна обчислити P_4 = 4! P , P_5 = 5! P , І так далі. Коли дійдемо до 8! P зауважимо, що вимагається обчислення зворотного елемента до 599 (mod 455 839). Так як 455839 ділиться на 599, то ми знайшли шукане розкладання: 455839 = 599.761.


4. Обчислювальна складність

Нехай найменший дільник числа n дорівнює p. Тоді час роботи алгоритму можна оцінити величиною

\ Exp (\ sqrt {2} + o (1) \ sqrt {p \ ln p \ ln (\ ln p)})

яка виконується у випадку, якщо межа B 1 вибрана близько до величини

\ Exp (\ sqrt {2} / 2 + o (1) \ sqrt {p \ ln p \ ln (\ ln p)})

Оскільки значення дільника p невідомо, то вибір значення B 1 виконується емпірично, що кілька погіршує практичну оцінку збіжності. Відзначимо, що додавання в алгоритм другій стадії обчислень зберігає загальну асимптотичну оцінку, хоча забезпечує великий практичний приріст швидкості збіжності алгоритму.

Якщо порівнювати метод еліптичних кривих з іншими методами факторизації, то цей метод відноситься до класу субекспоненціальних методів факторизації, а, значить, працює швидше за будь експоненціального методу. Якщо порівнювати його з методом квадратичного решета (QS) і методом решета числового поля (NFS), то все залежить від розміру найменшого дільника числа n. Якщо число n вибрано як в RSA у вигляді добутку двох простих чисел приблизно однакової довжини, то метод еліптичних кривих має ту ж оцінку, що і метод квадратичного решета, але поступається методу решета числового поля.

Однак якщо n має розмірність, що перевищує рекордні показники для методів QS і NFS, (нагадаємо, що останнім [ коли? ] рекордне розкладання чисел RSA з використанням NFS відноситься до числа довжини 768 бітів), то єдина надія знайти дільник n може виконана тільки за допомогою методу еліптичних кривих.


Література

  • Koblitz NA Course in number theory and cryptography. - Springer-Verlag, 1987.
  • Lenstra AK, Lenstra HW, Lovsz L. (1982). "Factoring polynomials with rational coefficients". Math. Ann. 261.
  • Lenstra Jr., HW (1987). "Factoring integers with elliptic curves". Annals of Mathematics 126 (2): 649-673. MR 89g: 11125.
  • Trappe, W., Washington, LC Introduction to Cryptography with Coding Theory. - Second. - Pearson Prentice Hall, 2006. - ISBN 0-13-186239-1
  • Ішмухаметов Ш. Т. Методи факторизації натуральних чисел. - Казань: Казан. ун .. - 2011. - 190 с.