title: How can I improve this code of elliptic curve factorization?
body: <p>First, I'm very noob :) I didn't studied deep on elliptic curves. I just google some elementary knowledge of prime factorization and elliptic curve.</p>
  
  <p>I'm trying to make the python3 code implementation of elliptic curve factoring  algorithm. I just Followed the discription in <a href="https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization" rel="nofollow noreferrer">Lenstra's Elliptic Curve Method</a>, and with some functinons, class and implemented error, I managed to build the code:</p>
  
  <pre><code>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 &amp; 1:
                  r = r + self
                  if other==1: return r
              other &gt;&gt;= 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())))
  </code></pre>
  
  <p>This code gets a composite number as input, and print two nontrivial divisors.</p>
  
  <p>The code runs well for most of the inputs. Problem is, it's too slow...
  I tested this code for some numbers between 60~120 bit integers(such as 2^101-1, 10^30-33, etc.), and what I encountered was it is even slower than roughly made Pollard's p-1 test like this:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>And for inputs of roughly 50 digits(according to Wikipedia, this range should be the real playground for ECM...), this program is halted even for a day.</p>
  
  <p>Can I improve the performance of this code? Is it worthy to optimize the boundary of the value k, or should I fix large part of this algorithm?</p>
  
  <p>Thanks for your help, and sorry for poor language(if something wrong);;</p>