title: Python Pollard P-1 factorization
body: <p>I'm trying to implement Pollard's P-1 factorization in Python.  Note that the Rho method has some answers but this p-1 is different and the best I can give you here about p-1 is the wiki and the Wolfram:</p>
  
  <p><a href="http://en.wikipedia.org/wiki/Pollard" rel="nofollow">http://en.wikipedia.org/wiki/Pollard</a>'s_p_%E2%88%92_1_algorithm</p>
  
  <p><a href="http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html" rel="nofollow">http://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html</a></p>
  
  <p>This is factoring something from n but consistently does not find p. The np and sp are from numpy and scipy respectively.  So the built-in functions for sp.uint64 is an unsigned long 64 int (because of the size of the expected integers) and np.prod(p) is the cumulative product pi of the list p:</p>
  
  <pre><code>def pm1_attack(n,b):
    p = [2,3,5,7,11,13,17]; i=19; a=2
    while i&lt;b:
      if is_prime(i,10): p.append(i)
      i+=2;
    k = sp.uint64(np.prod(p)); q = power2(a,k,n)
    g = euc_al_i((q-1),n)
    print "product pi: ",k
    print "q: ",q
    print "g: ",g
    #return a
  
  print "pollard_pm1_attack(n,b): ",pollard_pm1_attack(n,2000)
  </code></pre>
  
  <p>Output does not find p:</p>
  
  <pre><code>Python 2.7 (r27:82525, Jul  4 2010, 09:01:59) [MSC v.1500 32 bit (Intel)] on win32
  Type "copyright", "credits" or "license()" for more information.
  &gt;&gt;&gt; ================================ RESTART ================================
  &gt;&gt;&gt; 
  p = 1300199 
  q = 2063507 
  
  euler_totient = 2682966374188 
  
  common n = 2682969737893 
  
  
  public key e = 1588051820871 
  
  secret key d = 2410616084843 
  
  cleartext message = test 
  
  encoded message = 1489995542681 
  
  decoded message = test 
  
  check_rsa = Successful encryption and decrytion. Message is authenticated. 
  
  pollard_pm1_attack(n,b):  product pi:  18446744073460481730
  q:  2391570546599
  g:  1
  None
  &gt;&gt;&gt; 
  </code></pre>
  
  <p>I'm learning Python so it may be some simple mistake.  The power2() function uses exponentiation by squaring and is basically a super-charged pow() for very large integers.  The euc_al_i() is just the gcd.  You can use whatever gcd() you like, but since I'm learning I wanted to make these myself.</p>
  
  <p>I'm trying to find out what went so horribly wrong here that it doesn't find p from even relatively small n (as small as 20 bit-length).</p>