import math, fractions, operator

class Toolbox(object):

  def egcd(self,a, b):
      if a == 0:
          return (b, 0, 1)
      else:
          g, y, x = self.egcd(b % a, a)
          return (g, x - (b // a) * y, y)

  def square_and_multiply(self, g, e, m):
    # g is the base, e is the exponent, m is the modulus.

    # We want to handle all integers e
    if e < 0:
      g = self.modinv(g)
      e = -e
    elif e == 0:
      return 1

    # Now assume that e > 0.

    # Get binary representation of e, and note that the first two
    # symbols are 0b when e is positive, so we cut them away.
    be = bin(e)[2:]

    a = 1
    for b in be:
      a = (a * a) % m
      if b == '1':
        a = (a * g) % m
    return a

class Factoring(object):

  def __init__(self):
    self.tb = Toolbox()

  def pollard_p(self,n, B):
    print 'Running pollard_p on n = ' + str(n)
    a = 2
    print 'Step 1: setting a = ' + str(a)

    print 'Step 2: for j from 2 to ' + str(B) + ':'
    for j in range(2,B):
      a = self.tb.square_and_multiply(a,j,n)
      print 'a <- a^'+str(j)+' = ' + str(a) + ' mod ' + str(n)
    d = fractions.gcd((a-1),n)
    print 'Gcd of a-1 and n is:'
    print 'gcd('+str(a)+'-1, '+str(n)+') = gcd('+str(a-1)+', '+str(n)+') = ' + str(d)
    if d > 1 and d < n:
      print 'Result of pollard_p is: ' +str(d)
      print 'n = ' + str(d) + '*' + str(n/d)
    else:
      print "Factoring failed"

  def pollard_rho_f(self,x,n):
    return (x**2 + 1)%n

  def pollard_rho(self,n = 3006611):
    print "Running pollard_rho on n = " + str(n)
    points = []
    cycle = False
    x1 = 2
    points.append(x1)
    print "x1 = " + str(x1)
    x2 = self.pollard_rho_f(x1,n)
    print "x2 = " + str(x2)
    p = fractions.gcd((x1-x2),n)
    print "Gcd(x1-x2,n) = " + str(p)
    it = 0
    while p == 1:
      it += 1
      x1 = self.pollard_rho_f(x1,n)
      if x1 in points and cycle == False:
        print "Cycle reached"
        cycle == True
      else:
        points.append(x1)
      x2 = self.pollard_rho_f(x2,n)
      x2 = self.pollard_rho_f(x2,n)
      p = fractions.gcd((x1-x2),n)
      print "Iteration number " + str(it)
      print "x1 = " + str(x1)
      print "x2 = " + str(x2)
      print "Gcd(x1-x2,n) = " + str(p)
    if p == n:
      print "Factoring failed"
    else:
      print "Factoring successful"
      print "n = " + str(p) + "*" + str((n/p))


print """
Usage: python -i factoring.py
   or: ./factoring.py (if you have set the executable flag)

The file provides the class Factoring, which you can use by typing

  obj = Factoring()

It contains
the following methods:

  pollard_p(n,B): Runs the pollard p-1 algorithm on the number n using the
      bound B.
  pollard_rho(n): Runs the pollard rho algorithm on the number n.

Example
  obj = Factoring()
  obj.pollard_p(3006611,12)
  obj.pollard_rho(3006611)
"""