Алгоритм факторизации методом эллиптических кривых Ленстры

Введение

Алгоритм целочисленной факторизации

Факторизация эллиптической кривой Ленстры или метод факторизации эллиптической кривой (ECM) — это быстрый алгоритм целочисленной факторизации со временем работы, растущим субэкспоненциально, использующий эллиптические кривые. Для факторизации общего назначения ECM является третьим по скорости известным методом. Вторым по скорости является метод многочленного квадратичного решета, а самым быстрым — общее решето числового поля. Факторизация эллиптической кривой Ленстры названа в честь Хендрика Ленстры. На практике ECM считается алгоритмом факторизации специального назначения, поскольку он наиболее подходит для поиска малых делителей. В настоящее время это по-прежнему лучший алгоритм для делителей, не превышающих 50–60 цифр, поскольку его время работы определяется размером наименьшего делителя p, а не размером числа n, которое необходимо разложить на множители. Часто ECM используется для удаления малых делителей из очень большого целого числа, имеющего множество делителей; если оставшееся целое число все еще составное, то оно имеет только большие делители и разлагается на множители с использованием методов общего назначения. Самый большой делитель, найденный с помощью ECM на сегодняшний день, содержит 83 десятичные цифры и был обнаружен 7 сентября 2013 года Р. Проппером. Увеличение количества проверяемых кривых повышает вероятность нахождения делителя, но эта вероятность не растет линейно с увеличением числа цифр.

Пояснение

Если p и q – два простых делителя n, то 1=y^(2) = x^(3) + 1=ax + b (mod n) влечет за собой то же уравнение также 1=modulo p и 1=modulo q. Эти две меньшие эллиптические кривые с операцией сложения теперь являются настоящими группами. Если эти группы имеют Np и Nq элементов соответственно, то для любой точки P на исходной кривой, по теореме Лагранжа, 1=k > 0 минимально, чтобы на кривой по модулю p, k делило Np; более того, аналогичное утверждение верно для кривой по модулю q. Когда эллиптическая кривая выбирается случайным образом, то Np и Nq являются случайными числами, близкими к 1=p + 1 и 1=q + 1 соответственно (см. ниже). Следовательно, маловероятно, что большинство простых факторов Np и Nq совпадают, и весьма вероятно, что при вычислении eP мы встретим некоторое kP, которое равно ∞ 1=modulo p, но не 1=modulo q, или наоборот. В этом случае kP не существует на исходной кривой, и в вычислениях мы находим некоторое v, для которого 1=gcd(v,p) = p или 1=gcd(v,q) = q, но не одновременно. То есть 1=gcd(v, n) дает нетривиальный фактор 1=of n. ECM по сути является усовершенствованием более старого алгоритма 1=p − 1. Алгоритм 1=p − 1 находит простые множители p, такие, что 1=p − 1 является гладким числом относительно степени b для небольших значений b. Для любого e, кратного 1=p − 1, и любого a, взаимно простого с p, по малой теореме Ферма имеем 1=a^(e) ≡ 1 (mod n). Тогда 1=[[наибольший общий делитель, вероятно, даст фактор n. Однако алгоритм не работает, когда 1=p − 1 имеет большие простые факторы, как в случае чисел, содержащих сильные простые числа, например. ECM обходит это препятствие, рассматривая группу случайной эллиптической кривой над конечным полем Zp, а не мультипликативную группу Zp, которая всегда имеет порядок 1=p − 1. Порядок группы эллиптической кривой над Zp изменяется (достаточно случайно) в пределах от до по теореме Хассе и, вероятно, будет гладким для некоторых эллиптических кривых. Хотя нет доказательства того, что в интервале Хассе будет найден гладкий порядок группы, используя эвристические вероятностные методы, теорему Канфилда — Эрдоша — Померанца с соответствующим оптимизированным выбором параметров и L-нотацию, мы можем ожидать, что попробуем кривых, прежде чем получить гладкий порядок группы. Эта эвристическая оценка очень надежна на практике.

If p and q are two prime divisors of n, then 1=y^(2) = x^(3) + 1=ax + b (mod n) implies the same equation also 1=modulo p and 1=modulo q. These two smaller elliptic curves with the addition are now genuine groups. If these groups have Np and Nq elements, respectively, then for any point P on the original curve, by Lagrange's theorem, 1=k > 0 is minimal such that on the curve modulo p implies that k divides Np; moreover, The analogous statement holds for the curve modulo q. When the elliptic curve is chosen randomly, then Np and Nq are random numbers close to 1=p + 1 and 1=q + 1, respectively (see below). Hence it is unlikely that most of the prime factors of Np and Nq are the same, and it is quite likely that while computing eP, we will encounter some kP that is ∞ 1=modulo p but not 1=modulo q, or vice versa. When this is the case, kP does not exist on the original curve, and in the computations we found some v with either 1=gcd(v,p) = p or 1=gcd(v, q) = q, but not both. That is, 1=gcd(v, n) gave a non trivial factor 1=of n.

ECM is at its core an improvement of the older 1=p − 1 algorithm. The 1=p − 1 algorithm finds prime factors p such that 1=p − 1 is b powersmooth for small values of b. For any e, a multiple of 1=p − 1, and any a relatively prime to p, by Fermat's little theorem we have 1=a^(e) ≡ 1 ([[modular arithmetic. Then 1=[[greatest common divisor is likely to produce a factor of n. However, the algorithm fails when 1=p 1 has large prime factors, as is the case for numbers containing strong primes, for example. ECM gets around this obstacle by considering the group of a random elliptic curve over the finite field Zp, rather than considering the multiplicative group of Zp which always has order 1=p − 1. The order of the group of an elliptic curve over Zp varies (quite randomly) between and by Hasse's theorem, and is likely to be smooth for some elliptic curves. Although there is no proof that a smooth group order will be found in the Hasse interval, by using heuristic probabilistic methods, the Canfield–Erdős–Pomerance theorem with suitably optimized parameter choices, and the L notation, we can expect to try curves before getting a smooth group order. This heuristic estimate is very reliable in practice.

Пример использования

Следующий пример из , с некоторыми добавленными деталями. Мы хотим разложить на множители 1=n = 455839. Выберем эллиптическую кривую 1=y^(2) = x^(3) + 5x – 5, с точкой 1=P = (1, 1) на ней, и попробуем вычислить 1=(10!)P. Наклон касательной прямой в некоторой точке A=(x, y) равен 1=s = (3x^(2) + 5)/(2y) (mod n). Используя s, мы можем вычислить 2A. Если значение s имеет вид a/b, где b > 1 и НОД(a, b) = 1, мы должны найти модульный обратный к b. Если он не существует, то НОД(n, b) является нетривиальным делителем n.

Сначала вычислим 2P. У нас есть 1=s(P) = s(1, 1) = 4, так что координаты 2P равны и 1== 4(1 – 14) – 1 = –53, все числа понимаются по модулю n. Просто чтобы проверить, что 2P действительно лежит на кривой: 1=(–53)^2 = 2809 = 143 + 5·14 – 5 (mod n). Затем вычислим 3(2P). У нас есть 1=s(2P) = s(14, 53) = –593/106 (mod n). Используя алгоритм Евклида: 1=455839 = 4300·106 + 39, затем 1=106 = 2·39 + 28, затем 1=39 = 28 + 11, затем 1=28 = 2·11 + 6, затем 1=11 = 6 + 5, затем 1=6 = 5 + 1. Следовательно, 1=НОД(455839, 106) = 1, и работая в обратном направлении (версия расширенного алгоритма Евклида): 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^(-1) = 81707 (mod 455839), и 1=–593/106 = –133317 (mod 455839). С учетом этого s, мы можем вычислить координаты 2(2P), как мы и делали выше: 1=4P = (259851, 116255). Просто чтобы проверить, что это действительно точка на кривой: 1=y^(2) = 54514 ≡ x^(3) + 5x – 5 (mod 455839). После этого мы можем вычислить.
Мы можем аналогично вычислить 4!P и так далее, но 8!P требует инвертирования 1=599 (mod 455839). Алгоритм Евклида показывает, что 455839 делится на 599, и мы нашли 1=факторизацию 455839 = 599·761. Причина, по которой это сработало, заключается в том, что кривая 1=(mod 599) имеет 1=640 = 27·5 точек, в то время как 1=(mod 761) она имеет 1=777 = 3·7·37 точек. Кроме того, 640 и 777 являются наименьшими положительными целыми числами k, такими, что 1=kP = ∞ на кривой 1=(mod 599) и 1=(mod 761), соответственно. Поскольку 8! кратно 640, но не кратно 777, мы имеем 1=8!P = ∞ на кривой 1=(mod 599), но не на кривой 1=(mod 761), следовательно, повторное сложение сломалось здесь, давая факторизацию.

Этап 2

Вышеприведенный текст посвящен первой стадии факторизации эллиптической кривой. На этой стадии надеются найти простой делитель p, такой что является нейтральным элементом в . На второй стадии надеются найти простой делитель q, такой что имеет небольшой простой порядок в . Мы надеемся, что этот порядок будет находиться между и , где определяется на стадии 1, а – новый параметр стадии 2. Проверка на малый порядок может быть выполнена путем вычисления по модулю n для каждого простого числа l.

GMP-ECM и EECM-MPFQ

Использование эллиптических кривых Twisted Edwards, а также других техник, было применено Бернштейном и соавторами. Алгоритм Гровера позволяет примерно удвоить длину простых чисел, полученных по сравнению со стандартным EECM, при условии наличия квантового компьютера с достаточным количеством кубитов и сравнимой скоростью работы с классическим компьютером, выполняющим EECM.