gistfile1.txt

import base64

from Crypto.Util.number import *
from Crypto.PublicKey import RSA

def gcd(a,b):
	while b != 0:
		t = b
		b = a % b
		a = t
	return a

# Pollard's p-1 algorithm
# https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm
# this is really slow on stock python2, use either python3 or some JITer

def factor(n):
    a = 2
    b = 2
    while True:
        if b % 10000 == 0:
            print(b)
            
        a = pow(a, b, n)
            
        p = gcd(a - 1, n)
        if 1 < p < n:
            print("FOUND " + str(p))
            return p
            
        b += 1

n = 149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897
q = factor(n);

p = n/q