10.06.2016
ECM
Факторизация с помощью эллиптических кривых (англ. elliptic curve method, сокр. ECM ) —
алгоритм факторизации натурального числа с использованием эллиптических кривых.
Данный алгоритм имеет субэкспоненциальное время выполнения.
На практике часто используется для выявления (отбрасывания) небольших простых делителей числа.
Если полученное после работы алгоритма число все еще является составным, то остальные сомножители — большие числа.
При увеличении количества кривых шансы найти простой делитель возрастают.
Википедия следующим образом описывает базовый алгоритм:
Пусть дано составное число n. Нужно найти его нетривиальный делитель.
Случайным образом выбирается эллиптическая кривая:
y2 = x3 + ax + b
и некоторая точка P = ( x , y ) на ней.
Выбирается целое число k , делящееся на степени малых простых чисел.
Вычисляется произведение k * P
Вычисления проводятся до тех пор, пока при попытке найти число, обратное к 2yp
не появляется число, не взаимно простое с n.
Эллиптические кривые
Эллиптическая кривая - это кубическая кривая, задаваемая уравнением 3-й степени вида
y2 + a1xy + a3y = x3 + a2x2 + a4x + a6
Эллиптические кривые можно выразить в канонической форме:
y2 = x3 + ax + b - форма Вейерштрасса
y2 = x3 + a2x2 + a4x + a6
y2 + у = x3 + ax + b - суперсингулярные кривые
y2 + xу = x3 + ax2 + b - не-суперсингулярные кривые
Есть еще т.н. форма Монтгомери:
by2z = x(x2 + axz + z2)
Число 4a3 + 27b2 называется дискриминантом кубической кривой.
На следующем рисунке видно, что в случае Д и Е кривые существенно отличаются:
у первой имеется точка возврата, у второй - точка самопересечения.
Эти точки являются примерами особых точек кривой, соответственно, кривые, которые имеют хотя бы одну такую точку,
называются особыми. Кривые, не имеющие особых точек, называются неособыми или гладкими - это справедливо для рисунка
в слуваях А, Б, В, Г :
Теорема Ньютона Для любой неособой кубической кривой существует проективная замена координат,
приводящая ее в форму Вейерштрасса. Если коэффициенты упавнения исходной кривой рациональны
и на кривой имеется хотя бы одна рациональная точка, то можно найти проективную замену,
преобразующую исходную кривую в кривую в форме Вейерштрасса с рациональными a и b.
Неособая кривая 3-го порядка называется эллиптической кривой.
На следующем рисунке показана проективная замена переменных, приводящая кривую x3 + y3 = 1
к форме Вейерштрасса. Делаем две замены: x = s - t и y = t - получаем параллельную проекцию плоскости xy
на плоскость st:
Для произвольной эллиптической кривой задача нахождения рациональных точек аналогична задаче нахождения
целых точек. Метод секущих позволяет ввести на множестве рациональных точек эллиптичексой кривой некоторую структуру.
Рациональные точки можно дублировать
Пусть на эллиптической кривой y2 = x3 + ax + b , которая представлена на
следующем рисунке, есть рациональные точки - P и Q. Проведем прямую PQ и вычислим координату ее пересечения с кривой.
Эта точка пересечения удовлетворяет системе уравнений:
y2 = x3 + ax + b
(y - yP)(xQ - xP) = (x - xP)(yQ - yP)
Если xQ ≠ xP и yQ ≠ yP, во втором уравнении выражаем x через y
и подставляем в первое. В результате мы переходим к кубическому уравнению с рациональными коэффициентами.
Т.о. по двум рациональным точкам мы построили третью. Еще одна точка получается путем симметрии относительно оси ox,
которая еще называется суммой точек P+Q.
Что касается целых решений, то доказано, что любая эллиптическая кривая имеет конечное число целых решений.
Например, на следующем рисунке приведен график эллиптической кривой y2 + y = x3 - x ,
который распадается на два куска: овал и бесконечную дугу. Одно целое решение (0,0) тривиально.
Для этой кривой все целые точки отвечают условию aP1 + bP2, где a и b меньше 13.
Несколько целых решений для этого уравнения можно найти простым перебором: (1,1) , (10.5) , (13,6)
Алгоритм ECM
В википедии приводится следующий пример реализации алгоритма ECM:
Пусть нам нужно факторизовать число n = 455839.
Возьмем эллиптическую кривую и точку, лежащую на этой кривой:
y2 = x3 + 5x - 5 , P=(1,1)
Вычислим координаты точки P2 = 2!P = 2P
Тангенс угла наклона касательной в точке P равен:
Находим координаты точки P2:
x2 = s2 - 2x1 = 14 (mod n)
y2 = s(x1 - x2) - y = 4(1-14) -1 = -53 (mod n)
Проверяем, что точка 2P действительно лежит на кривой:
(-53)2 = 2809 = 143 + 5*14 - 5
Вычисляем P3 = 3!P = 6P
Тангенс угла наклона касательной в точке 2P составляет
s = (3*196 + 5) / (2(-53)) = -593/106 = 322522 (mod n)
Учитывая вычисленное s, мы можем вычислить координаты точки 2(2P), так же, как это было сделано выше:
4P = (259851, 116255). Проверяем, что точка действительно лежит на нашей эллиптической кривой.
Аналогичным образом можно вычислить P4 = 4!P, P5 = 5!P , и так далее.
Когда дойдем до 8!P заметим, что требуется вычисление обратного элемента к 599 (mod 455839).
Так как 455839 делится на 599, то мы нашли искомое разложение: 455839 = 599·761.
Критерий простоты, использующий эллиптические кривые, является аналогом следующего критерия простоты чисел,
который еще называется критерием простоты Поклингтона:
Пусть n - натуральное число. Предположим, что имеется простой делитель q числа n-1,
бОльший, чем sqrt(n)-1.
Если существует такое число a, такое, что:
1. an-1 ≡ 1 (mod n)
2. НОД(a(n-1)/q = 1
то n - простое число.
Тест Поклингтона является детерминированным, а не вероятностным. Обычно достаточно взять a=2
Критерий простоты, использующий эллиптические кривые, основан на аналогичном предположении,
в котором предполагается заданным уравнение y2 = x3 + ax + b , рассматриваемое по модулю n.
Целые числа a и b рассматриваются как вычеты по модулю n и E обозначает множество всех пар (x,y) целых чисел,
удовлетворяющих этому уравнению. При использовании эллиптических кривых прийдется складывать точки этих кривых
аналогично тому, как было показано выше. При поиске точек на эллиптической кривой возможны варианты, когда
мы получаем некоторое число m, которое при простом n равно числу точек эллиптической кривой E
Такое число m будет играть роль n-1. Теперь можно сформулировать аналог критерия Поклингтона для
эллиптических кривых:
Пусть n - натуральное число. Пусть E - множество, определяемое уравнением y2 = x3 + ax + b
по модулю n, НОД(4a3 + 27b2, n) = 1. Пусть m - целое число.
Предположим, что у m есть простой делитель q, больший чем (n1/4 + 1)2.
Если существует такая точка P на E, что:
1. mP = O
2. (m/q)P определена и не равна O
то n - простое число
Это предложение приводит к алгоритму для доказательства простоты данного натурального числа n.
Выбираем случайно три числа a, x, y по модулю n и полагаем:
b ≡ y2 - x3 - ax (mod n)
Если при этом НОД(4a3 + 27b2, n) > 1, выбираем другую тройку.
Тогда P = (x,y) есть элемент множества E, которое определяется нашим уравнением эллиптической кривой.
Используем метод Шуфа(или другой метод для подсчета числа точек на эллиптической кривой), чтобы найти число m,
которое при простом n равно числу точек эллиптической кривой. Если мы не можем представить m
в виде m = kq, где k>2, то выбираем другую случайную тройку и повторяем все с начала.
Предположим, что мы получили эллиптическую кривую, для которой m имеет искомый вид.
Тогда находим произведение mP и kP. Если мы в какой-то момент получаем неопределенное выражение,
то мы сразу находим нетривиальный делитель n.
Алгоритм ECM непрост по двум основным причинам. Первая - алгоритм Шуфа достаточно сложен для практического применения.
Приходится подсчитывать точки на большом количестве кривых, пока не будет найдена наконец кривая, для которой
число m будет иметь искомый вид - m = kq. Есть алгоритмы, подбирающие кривые с помощью комплексного
умножени (Atkin). Вторая - теоретическая. Чтобы найти кривую, у которой число точек "почти простое", нужно
кое-что знать о распределении простых чисел в интервале р + 1 - 2*sqrt(p) , p + 1 + 2*sqrt(р),
где в соответствии с теоремой Хассе находится число m. Дело в том, что до сих пор не доказано,
что за полиномиальное число попыток в данном интервале можно найти искомое число.
Одной из разновидностью алгоритма ECM является алгоритм, найденный Ленстрой.
Для того, чтобы понять, как он работает, нужно сначала вспомнить об алгоритме факторизации Полларда.
Пусть мы хотим разложить на множители составное число п и предполагаем, что р — его (еще неизвестный) простой делитель.
Если р таков, что р — 1 не имеет больших простых делителей, то р можно найти следующим способом:
1. Выбираем целое число к, кратное всем или большинству целых чисел, меньших некоторой границы В.
Например, в качестве к можно взять В! или общее наименьшее кратное всех целых чисел, не.превосходящих B
2. Выбираем целое число а между 2 и п — 2. Например, а может быть равно 2, 3 или случайно выбранному
целому числу.
3. Вычисляем аk по модулю п повторным возведением в квадрат.
4. Вычисляем d = НОД (аk - 1, п), используя алгоритм Евклида и вычет ak (mod n) из шага 3.
5. Если d не есть нетривиальный делитель п, то повторяем все шаги с новым а и/или новым к.
Чтобы понять, при каких условиях этот алгоритм будет работать, предположим, что к делится на все натуральные числа,
не превосходящие В. Далее, пусть р — простой делитель п, для которого р - 1 представляется в виде произведения
степеней небольших простых чисел, причем каждый из сомножителей меньше В. Отсюда следует, что к кратно р-1
(так как оно кратно каждому из сомножителей в разложении р—1). Поэтому, по малой теореме Ферма, имеем
аk ≡ 1 (mod p).Тогда НОД (аk - 1, п) делится на р.
Таким образом, единственное препятствие, которое может помешать нам получить на шаге 4 нетривиальный делитель п
— это случай, когда аk ≡ 1 (mod n)
Пример 1. Разложим указанным методом п = 540143. Выбираем В = 8 (и, следовательно, к равно 840 — общему наименьшему
кратному 1,2,..., 8) и а = 2. Находим, что 2840 (mod n) — это 53047 и НОД(53046, п) = 421.
Тем самым приходим к разложению 540143 = 421*1283.
Основная слабость метода Полларда, очевидно, проявляется при попытках его применения в тех случаях,
когда все простые делители р числа п таковы, что р—1 делится на относительно большое простое число (или на большую степень простого числа).
Принципиальное отличие метода Ленстры состоит в том, что при использовании эллиптических кривых мы получаем много последовательностей
небольшого ранга.
Пусть m — целое число и х1,х2 — два рациональных числа со знаменателями, взаимно простыми с m;
будем писать x1 ≡ х2 (mod m), если числитель разности х1 — х2, записанной в виде несократимой дроби,
делится на m. Для любого рационального числа x1 со знаменателем, взаимно простым с m,
существует такое однозначно определенное целое х2 между 0 и m — 1 («наименьший неотрицательный вычет»),
что x1 ≡ x2 (mod m). Иногда мы будем обозначать наименьший неотрицательный вычет как х1 (mod m).
Пусть даны уравнение вида y2 = x3 + ax + b , и удовлетворяющая ему точка Р = (х,у).
На практике эллиптическая кривая Е вместе с точкой Р будут порождаться некоторым «случайным» образом.
Например, можно выбрать три случайных целых числа а,х,у из некоторой области и положить затем
b = y2 - x3 - ax .
Будем предполагать, что кубический многочлен
x3 + ax + b .
имеет различные корни, т. е. что 4а3 + 27b2 ≠ 0;
это условие выполняется почти всегда,
если коэффициенты выбираются описанным выше случайным образом.
Для простоты мы предполагаем также в дальнейшем, что 4а3 + 27b2 не имеет с п общих множителей;
другими словами, что x3 + ax + b . не имеет кратных корней по модулю р для любого простого делителя р числа п.
Практически, выбрав а, b, мы можем проверить это, найдя
НОД(4а3 + 27b2, n).
Если это число больше 1, то либо п кратно (4а3 + 27b2)(и тогда нам следует выбрать другие а и 6),
либо мы уже обнаружили нетривиальный делитель п (и тогда задача решена).
Итак, мы будем предполагать, что НОД(4а3 + 27b2, n). = 1.
Пусть нам нужно найти кратную кР для точки Р методом повторного удвоения.
Есть много различных способов сделать это за O(log k) шагов, каждый из которых — либо удвоение точки, либо сложение двух различных точек.
Можно, например, записать к в двоичной системе счисления: к = a0 + a1*2 + ... + a*2m-1
и затем последовательно удваивать Р, прибавляя 2jР к уже накопленной сумме, если соответствующий бит aj равен 1.
Можно также разложить к в произведение простых чисел l1, l2 ,... (расположенных,скажем, в неубывающем порядке)
и затем последовательно вычислять l1P, l2(l1Р) и т.д.
Здесь каждая точка ljPj, где Pj = lj-1lj-2...l1P,
вычисляется повторным удвоением с использованием двоичной записи чисел lj.
Лемма:
Пусть Е — эллиптическая кривая с уравнением y2 = x3 + ax + b ,
и НОД(4а3 + 27b2, n). = 1..
Пусть Pi и Р2 — две точки на Е, у которых знаменатели координат взаимно просты с п,
и Р1 ≠ -P2. Тогда Р1 + Р2 имеет координаты, у которых знаменатели взаимно просты с п,
в том и только том случае, когда у п нет простого делителя р,
для которого сумма точек Pj (mod р) и Р2 (mod р) на эллиптической кривой Е (mod p)
была бы равна точке в бесконечности О (mod р).
Здесь Е (mod p) обозначает эллиптическую кривую, полученную приведением по модулю р коэффициентов уравнения
y2 = x3 + ax + b ,
Метод Ленстры. Пусть дано составное целое нечетное число п и нам нужно найти его нетривиальный делитель d, 1 < d < п.
Берем сначала какую-либо эллиптическую кривую Е
y2 = x3 + ax + b ,
с целыми a, b и точку Р = (x, у) на ней.
Пару (Е,Р) можно выбирать случайным образом или использовать любой детерминистический метод,
который порождает много таких пар.
Мы попытаемся с помощью Е и Р разложить п способом, описанным ниже; если попытка окажется неудачной,
то возьмем другую пару (Е,Р) и будем продолжать до тех пор, пока не найдем делитель d.
Если вероятность неудачи равна р < 1, то вероятность того, что все h последовательно выбранных пар (Е, Р) окажутся неудачными,
очень мала для больших h.
Таким образом, с высокой вероятностьюмы разложим п за приемлемое число шагов.
Имея пару (Е,Р), мы выбираем целое число к, которое делится на степени малых простых чисел (т.е. не больших некоторого В),
не превосходящие С. Таким образом, мы полагаем
k = ∏lαl
где αl = [(logC)/(logl)] есть такой наибольший возможный показатель,
что lα < C.
Далее мы пытаемся вычислить кР, выполняя все действия по модулю п.
Результаты этих вычислений не представляют для нас интереса до тех пор, пока при попытке найти число, обратноек х2 — x1 ,
мы не столкнемся с числом, которое не взаимно просто с п.
Согласно предложению. это произойдет, когда появится такая точка кР (частичная сумма в процессе вычисления кР),
что к(Р (mod р)) = О (mod p) для некоторого простого делителя р, иными словами, порядок Р (mod p) в группе Е (mod p)
является делителем к. Когда мы, применяя алгоритм Евклида, пытаемся обратить знаменатель, делящийся на р,
мы вместо этого находим НОД числа п и этого знаменателя.
Этот НОД и будет искомым собственным делителем п, если он отличен от п, т.е. если знаменатель не делится на само п.
Однако такая делимость означала бы, по предложению , что кР (mod р) = О (mod p) для всех простых делителей р числа п,
а это очень маловероятно, если п имеет не менее двух очень больших простых делителей.
Таким образом, почти с полной гарантией при попытке вычисления кР по модулю п для к, которое делится на порядок точки Р (mod p)
при некотором р, мы получим собственный делитель числа п.
Теперь пора перейти к конкретным реализациям ecm. Рассмотрим первый простой пример.
Ленстра использует эллиптические кривые, записанные в форме Вейерштрасса.
В ней точка трехмерна, имеет три координаты (x, y, z), при этом z=1.
Уравнение эллиптической кривой имеет каноническую форму
y2 = x3 + ax + b (mod n)
Нулевая точка имеет координату (0, 1, 0)
Сложение двух точек дает в результате третью точку, при этом используется модульная инверсия.
Умножение двух точек - это комбинация сложения и удвоения
Фактор, который находится с помощью метода
function lenstra(n, limit)
задается с параметром ограничения limit, определяющего количество вычислений.
В следующем примере дана простейшая реализация алгоритма Ленстры.
В данном примере вычисляется 6-значный простой делитель 6-го числа Ферма:
Код
from random import randint
from fractions import gcd
def primes(n):
b, p, ps = [True] * (n+1), 2, []
for p in xrange(2, n+1):
if b[p]:
ps.append(p)
for i in xrange(p, n+1, p):
b[i] = False
return ps
def bezout(a, b):
if b == 0: return 1, 0, a
q, r = divmod(a, b)
x, y, g = bezout(b, r)
return y, x-q*y, g
def add(p, q, a, b, m):
if p[2] == 0: return q
if q[2] == 0: return p
if p[0] == q[0]:
if (p[1] + q[1]) % m == 0:
return 0, 1, 0 # infinity
n = (3 * p[0] * p[0] + a) % m
d = (2 * p[1]) % m
else:
n = (q[1] - p[1]) % m
d = (q[0] - p[0]) % m
x, y, g = bezout(d, m)
if g > 1: return 0, 0, d # failure
z = (n*x*n*x - p[0] - q[0]) % m
return z, (n * x * (p[0] - z) - p[1]) % m, 1
def mul(k, p, a, b, m):
r = (0,1,0)
while k > 0:
if p[2] > 1:
return p
if k % 2 == 1:
r = add(p, r, a, b, m)
k = k // 2
p = add(p, p, a, b, m)
return r
def lenstra(n, limit):
g = n
while g == n:
q = randint(0, n-1), randint(0, n-1), 1
a = randint(0, n-1)
b = (q[1]*q[1] - q[0]*q[0]*q[0] - a*q[0]) % n
g = gcd(4*a*a*a + 27*b*b, n)
if g > 1: return g # lucky factor
for p in primes(limit):
pp = p
while pp < limit:
q = mul(p, q, a, b, n)
if q[2] > 1:
return gcd(q[2], n)
pp = p * pp
return False
ferma = 6
n = (2**(2**ferma)) + 1
print n
print lenstra(n, 20000)
В следующем примере мы рассмотрим модернизированную версию Монтгомери для алгоритма Ленстры.
Она работает быстрее, чем предыдущий вариант. В предыдущей версии можно обратить внимание на то, что много времени
тратится на модульную инверсию. Монтгомери внес изменение - вместо использования эллиптической кривой
y2 = x3 + ax + b он предложил использовать кривую вида
y2 = x3 + ax2 + x . Плюс к этому из вычислений исключается координата y.
Числитель и знаменатель параметра a хранятся отдельно.
Удвоение и умножение координат в случае с вариантом Монтгомери теперь выглядят так:
Эллиптическую кривую мы задаем в форме
y2 = x3 + (An/Ad -2)x2 + x (mod n)
Точка хранится как пара координат (x,z)
Для того, чтобы сложить две точки P1(x1,z1) и P2(x2,z2). нужно сначала вычислить точку P0(x0,z0)= P1 - P2
x = ((x1–z1) × (x2+z2) + (x1+z1) × (x2–z2))2 × z0 (mod n)
z = ((x1–z1) × (x2+z2) – (x1+z1) × (x2–z2))2 × x0 (mod n)
Чтобы удвоить точку P:
x = (x+z)2 × (x–z)2 × 4 × Ad (mod n)
z = (4 × Ad × (x–z)2 + t × An) × t (mod n) where t = (x+z)2 – (x–z)2
Умножение представлено как комбинация сложения и удвоения
Брент разработал метод для нахождения нужной эллиптической кривой с помощью начального параметра s :
u = s2 - 5
v = 4s
An = (v–u)3 (3u+v)
Ad = 4u3v
P = (u3, v3)
Этот алгоритм, как уже было сказано раньше, похож на алгоритм факторизации Полларда p-1:
В обоих алгоритмах фигурирует одинаковый список простых чисел. Вычисляется максимальная экспонента.
Вычисляется НОД. Различие в том, что алгоритм Полларда основан на модульной арифметике,
а у ecm эллиптическая арифметика. Также отличие этих алгоритмов в том, что в случае неудачи
алгоритм Полларда просто останавливается, а ecm продолжается по новой.
Исходный алгоритм Ленстры проверяет НОД на каждой итерации. В версии Монтгомери мы вычисляем НОД один раз в конце.
Версия Монтгомери быстрее, поскольку в ней отсутствует инверсия. Параметризация Брента также важна, поскольку
она гарантирует, что ранг кривой - или число точек на ней - будет кратно 12.
В этом примере вычисляется уже 17-значный простой делитель для 7-го числа Ферма:
Код
from random import randrange
from math import log
def ilog(x, b): # greatest integer l such that b**l <= x.
l = 0
while x >= b:
x /= b
l += 1
return l
def isqrt(n):
if n == 0: return 0
x, y = n, (n + 1) / 2
while y < x: x, y = y, (y + n/y) / 2
return x
def introot(n, r=2):
if n < 0: return None if r%2 == 0 else -introot(-n, r)
if n < 2: return n
if r == 2: return isqrt(n)
lower, upper = 0, n
while lower != upper - 1:
mid = (lower + upper) / 2
m = mid**r
if m == n: return mid
elif m < n: lower = mid
elif m > n: upper = mid
return lower
def gcd(a, b):
while b: a, b = b, a%b
return abs(a)
# Returns the largest integer that, when squared/cubed/etc, yields n, or 0 if no such integer exists.
# Note that the power to which this number is raised will be prime.
def ispower(n):
for p in primegen():
r = introot(n, p)
if r is None: continue
if r ** p == n: return r
if r == 1: return 0
# Recursive sieve of Eratosthenes
def primegen():
yield 2; yield 3; yield 5; yield 7; yield 11; yield 13;
ps = primegen() # yay recursion
p = ps.next() and ps.next()
q, sieve, n = p**2, {}, 13
while True:
if n not in sieve:
if n < q: yield n
else:
next, step = q + 2*p, 2*p
while next in sieve: next += step
sieve[next] = step
p = ps.next()
q = p**2
else:
step = sieve.pop(n)
next = n + step
while next in sieve: next += step
sieve[next] = step
n += 2
def ecadd(p1, p2, p0, n): # Add two points p1 and p2 given point P0 = P1-P2 modulo n
x1,z1 = p1; x2,z2 = p2; x0,z0 = p0
t1, t2 = (x1-z1)*(x2+z2), (x1+z1)*(x2-z2)
return (z0*pow(t1+t2,2,n) % n, x0*pow(t1-t2,2,n) % n)
def ecdub(p, A, n): # double point p on A modulo n
x, z = p; An, Ad = A
t1, t2 = pow(x+z,2,n), pow(x-z,2,n)
t = t1 - t2
return (t1*t2*4*Ad % n, (4*Ad*t2 + t*An)*t % n)
def ecmul(m, p, A, n): # multiply point p by m on curve A modulo n
if m == 0: return (0, 0)
elif m == 1: return p
else:
q = ecdub(p, A, n)
if m == 2: return q
b = 1
while b < m: b *= 2
b /= 4
r = p
while b:
if m&b: q, r = ecdub(q, A, n), ecadd(q, r, p, n)
else: q, r = ecadd(r, q, p, n), ecdub(r, A, n)
b /= 2
return r
def ecm(n, B1=10, B2=20):
m = ispower(n)
if m: return m
iters = 1
while True:
for _ in xrange(iters):
seed = randrange(6, n)
u, v = (seed**2 - 5) % n, 4*seed % n
p = pow(u, 3, n)
Q, C = (pow(v-u,3,n)*(3*u+v) % n, 4*p*v % n), (p, pow(v,3,n))
pg = primegen()
p = pg.next()
while p <= B1: Q, p = ecmul(p**ilog(B1, p), Q, C, n), pg.next()
g = gcd(Q[1], n)
if 1 < g < n: return g
while p <= B2:
Q = ecmul(p, Q, C, n)
g *= Q[1]
g %= n
p = pg.next()
g = gcd(g, n)
if 1 < g < n: return g
B1 *= 3
B2 *= 3
iters *= 2
ferma = 7
n = (2**(2**ferma)) + 1
print ecm(n)
Реализацию ecm можно найти например в питоновской библиотекв pyecm.
В ней используется эллиптические кривые Монтгомери с параметризацией Шиямы.
Более подробно об алгоритме можно почитать у самого Ленстры.
Коблиц. Курс теории чисел.
Ишмухаметов. Методы факторизации натуральных чисел.
|
| Юлия | Здравствуйте, спасибо за статью! Скажите, пожалуйста, а как происходит вычитание
точек эллиптической кривой в проективных координатах?
В методе Монтгомери сложения точек нужно найти P0 = P1 - P2. Мне не очень понятен этот момент...
2017-03-03 13:54:34 | | Яковлев Сергей | Точка P0 является стартовым параметром, она является функцией от самого числа Ферма.
В данном примере она вычисляется по алгоритму Брента, описанному здесь,
по правилам модульной арифметики:
P0 = (x0, z0)
x0 = (An % ferma ) = (v–u)^3*(3u+v) % ferma
z0 = (Ad % ferna ) = (4u^3v) % ferma
Здесь ferma - это само число ферма
u, v - это координаты самих точек P1 и P2
Т.е. мы все время генерим эти самые случайные числа u, v
и получаем точку отсчета P0 как функцию трех переменных - u, v и самого числа ферма
Когда мы складываем две точки P1 и P2, мы получаем точку с координатами (x, z),
которые еще домножаем на (x0,z0) для того, чтобы гарантировать,
что полученная точка будет принадлежать эллиптической кривой,
на которой лежат точки P1 и P2
Вообще, вычитание двух точек делается аналогично сложению -
нужно только поменять знак у второй координаты
2017-03-03 22:35:15 | | Юлия | Спасибо!
Скажите, а можно с вами как-то связаться и обсудить данную тему подробнее?
Мне по учёбе нужно реализовать алгоритм Ленстры в качестве курсовой работы, есть много непонятных моментов,
но не у кого поспрашивать.
Если у вас есть время, и, естественно, не бесплатно с моей стороны...
2017-03-16 22:09:15 | | |
|
|