Как я могу улучшить этот код факторизации эллиптической кривой? - PullRequest
Новая
       10

Как я могу улучшить этот код факторизации эллиптической кривой?

0 голосов
/ 14 января 2019

Во-первых, я очень новичок :) Я не изучал глубоко на эллиптических кривых. Я просто Google немного элементарных знаний о факторизации и эллиптической кривой.

Я пытаюсь реализовать в коде python3 реализацию алгоритма факторинга эллиптических кривых. Я просто следовал описанию в Методе эллиптических кривых Ленстры , и с некоторыми функциями, классом и реализованной ошибкой мне удалось построить код: 

from random import randint
from math import e as exp
from math import sqrt, log

class InvError(Exception):
    def __init__(self, v):
        self.value = v


def inv(a,n):
    r1, s1, t1 = 1, 0, a
    r2, s2, t2 = 0, 1, n
    while t2:
        q = t1//t2
        r1, r2 = r2, r1-q*r2
        s1, s2 = s2, s1-q*s2
        t1, t2 = t2, t1-q*t2

    if t1!=1: raise InvError(t1)
    else: return r1


class ECpoint(object):
    def __init__(self, A,B,N, x,y):
        if (y*y - x*x*x - A*x - B)%N != 0: raise ValueError
        self.A, self.B = A, B
        self.N = N
        self.x, self.y = x, y

    def __add__(self, other):
        A,B,N = self.A, self.B, self.N
        Px, Py, Qx, Qy = self.x, self.y, other.x, other.y
        if Px == Qx and Py == Qy:
            s = (3*Px*Px + A)%N * inv((2*Py)%N, N) %N
        else:
            s = (Py-Qy)%N * inv((Px-Qx)%N, N) %N
        x = (s*s - Px - Qx) %N
        y = (s*(Px - x) - Py) %N
        return ECpoint(A,B,N, x,y)

    def __rmul__(self, other):
        r = self; other -= 1
        while True:
            if other & 1:
                r = r + self
                if other==1: return r
            other >>= 1
            self = self+self


def ECM(n):
    x0 = 2
    y0 = 3
    bound = max(int(exp**(1/2*sqrt(log(n)*log(log(n))))),100)
    while True:
        try:
            a = randint(1,n-1)
            inv(a,n)
            b = (y0*y0 - x0*x0*x0 - a*x0) %n
            inv(b,n)
            inv((4*a*a*a + 27*b*b)%n, n)

            P = ECpoint(a,b,n, x0,y0)
            for k in range(2, bound):
                inv(P.x, n)
                inv(P.y, n)
                P = k*P
                #print(k,P)

        except InvError as e:
            d = e.value
            if d==n: continue
            else: return d, n//d


print(ECM(int(input())))

Этот код получает составное число в качестве входных данных и печатает два нетривиальных делителя.

Код работает хорошо для большинства входных данных. Проблема в том, что это слишком медленно ... Я тестировал этот код для некоторых чисел в диапазоне от 60 до 120 бит (например, 2 ^ 101-1, 10 ^ 30-33 и т. Д.), И я столкнулся с тем, что он даже медленнее, чем грубо сделанный тест Полларда p-1, такой как это: 

def Pollard_pminus1(n):
    if '0' not in bin(n)[3:]: base = 3
    else: base = 2
    if n % base == 0: return base, n//base

    b = base; exp = 1
    while True:
        b = pow(b,exp,n)
        d = gcd(b-1,n)
        if d!=1: break
        exp += 1
    if d!=n: return d, n//d

А для входных данных примерно из 50 цифр (согласно Википедии этот диапазон должен быть реальной площадкой для ECM ...), эта программа остановлена ​​даже на день.

Могу ли я улучшить производительность этого кода? Стоит ли оптимизировать границу значения k или мне следует исправить большую часть этого алгоритма?

Спасибо за вашу помощь, и извините за плохой язык (если что-то не так) ;;

...