Multiple Polynomial Quadratic Sieve implementation

With self-initialization

Here is an implementations of the Quadratic Sieve (QS) factoring algorithm It is implemented in Sage, with a few critical components implemented in Cython for improved speed. It heavily utilizes general subroutines from Sage's libraries.

The implementation is split in three parts:

Basic Initialization
Generation of polynomials
Sieving
Linear Algebra

The sieving step is implemented in cython (that is converted to C-code and compiled)

%cython

from sage.rings.arith import is_prime, gcd
from math import log, ceil
from sage.misc.prandom import randint
from sage.structure.factorization import Factorization

class Enough(Exception):
    pass

# From the factorization functions
# we return (is_smooth, prime_part, factorization, original_val)

# If the number was not B-smooth
# we can still try to use it for 
# single-large-prime matching
cdef one_prime(val, factors, original_val, ones):
    if is_prime(val):
        #Single large prime
        if val in ones:
            (other_factors, other_val) = ones[val]
            f = Factorization(other_factors)*Factorization(factors)
            print "1" , # Single prime match
            return (True, val, f, original_val*other_val)
        else:
            ones[val] = (factors, original_val)
    return (False, None, None, None)

# Use trial division to see if val really is B-smooth
# Trial cheap is faster because we assume the value to fit in 64 bits.
# But we cannot start with that assumption
cdef trial_cheap(int *primes, int starting_point, int nr_primes, long long val, factors, original_val, ones):
    cdef int i, e
    cdef int p
    B = primes[nr_primes-1]
    for i in range(starting_point, nr_primes):
        p = primes[i]
        e = 0
        while(val % p == 0):
            val = val // p
            e += 1
        if e!= 0:
            factors.append((p, e))
            if val == 1:
                print "B", # B-Smooth nr.
                return (True, 1, Factorization(factors), original_val)
    return one_prime(val, factors, original_val, ones)
    
cdef trial_expensive(int *primes, int nr_primes, val, original_val, ones):
    cdef int i
    cdef int e
    B = primes[nr_primes-1]
    factors = []
    if val < 0:
        factors.append((-1,1))
        val=-val
    cdef long long long_long_limit = (1<<63)-1
    if val < long_long_limit:
        return trial_cheap(primes, i+1, nr_primes, val, factors, original_val, ones)
    for i in range(nr_primes):
        p = primes[i]
        e = 0
        while(val % p == 0):
            val = val // int(p)
            e += 1
        if e!= 0:
            factors.append((p, e))
            if val == 1:
                print "B", # B-Smooth nr.
                return (True, 1, Factorization(factors), original_val)
            if val < long_long_limit:
                return trial_cheap(primes, i, nr_primes, val, factors, original_val, ones)
    return one_prime(val, factors, original_val, ones)

# This is defined inline so it will not slow us down.
cdef inline eval_pol(a, b, n, int x, M):
    return (a * (x-M) + b) ** 2 - n

def sieve(int B, n, sq, int M, int K, a, b, solutions, factor_base, ones, B_smooths):
    # Floating point operations should be just as fast as 
    # integer operations on a modern CPU
    cdef float *sieve = <float *>malloc(M * 2 * sizeof(float))
    cdef int i, x, root, p, r
    cdef float logp
    cdef float sm
    cdef bint good
    cdef int M2 = 2 * M
    cdef int tenths = M2 / 10 # for measuring progress
    
    print("Starting sieve: $(%s*x + %s)^2 - N$" % (a, b))
    
    # Here we initialize the array with values negative
    # log of the polynomial value in that point, plus
    # some error term
    for x in range(M2):
        sieve[x] = -log(abs(eval_pol(a, b, n, x, M))) + 30

    # We could skip the first(smallest) primes,
    # as they do not contribute much to the smoothness,
    # and they are by far the most expensive to sieve with.
    for (sol1, sol2, p, logp) in solutions:
        # Do sieving for the positive and negative root
        for solution in [sol1, sol2]:
            #Find the starting point
            x = p - (-M % p) + (solution % p)
            assert((eval_pol(a, b, n, x, M) % p) == 0)
            i=0
            # Do actual sieving
            while(x < M2):
                sieve[x]+=logp
                x+=p
    #For trial division we want the primes to be in a raw array
    cdef int *primes = <int *>malloc(sizeof(int)*len(factor_base))
    cdef int nr_primes = len(factor_base)
    for i in range(nr_primes):
        primes[i] = factor_base[i][0]

    print "Done sieving, controlling results..."
    tries = 0
    for x in range(M2):
        if x % (tenths) == 0:
            print "*" ,
        if (sieve[x] > 0):
            tries +=1
            val = eval_pol(a, b, n, x, M)
            (is_smooth, large_prime, f, original_val) =\
                trial_expensive(primes, nr_primes, val, a*(x-M) + b, ones)
            if is_smooth:
                B_smooths.append((f, large_prime, original_val))

                if(len(B_smooths) == K+10):
                    free(sieve)
                    free(primes)
                    print "Got enough!"
                    raise Enough()
    print "\n2*M: %s, K: %s, supposedly smooth: %s. Relations found: %s" % (M2, K, tries, len(B_smooths)) 
    free(sieve)
    free(primes)
print "sieve defined"

sieve defined

A small wrapper procedure for taking square-roots modulo primes

from sage.rings.integer_mod import square_root_mod_prime

def sqrtmodp(n, p):
    return int(square_root_mod_prime(GF(p)(n)))

This function generates polynomials to sieve

def make_polynomials(factor_base, n, B, M):
    print "***** Initializing polynomials *****"
    qs = []
    i = 0
    a = 1
    factor_base = factor_base[:] # make a copy
    
    # Find an a by fist skipping primes that are
    # too small
    while(factor_base[i][1] < (sqrt(2*n)/M)^(1/10)):
        i+=1
        
    # Then take enough primes out that a gets approx.
    # the right size
    while a/2<(sqrt(2*n)/M):
        (q, t) = factor_base.pop(i)
        a *= q
        qs.append((q, t))
    print "Nr of primes used for a: ",len(qs)
    Bs = []
    
    for (q, t) in qs:
        gamma = t * inverse_mod(a//q, q) % q
        if gamma > q//2: gamma = q - gamma
        Bs.append(a//q * gamma)
    Bainv2={}
    solutions = []
    b = sum(Bs)
    
    for (p, t) in factor_base:
        if p in qs:
            continue
        ainv = inverse_mod(a, p)
        for j in range(len(qs)):
            Bainv2[(j,p)] = (2*Bs[j]*ainv) % p
        solutions.append([ainv * (-b + t) % p, ainv * (-b - t) % p, p, math.log(p)])
        
    yield (a, b, solutions)

    from operator import xor
    code = 0
    
    for i in range(1, 2^(len(qs)-1)):
        # Find out where the gray-code differs
        # from last time
        newcode = (xor(i, i >> 1))
        diff = xor(code, newcode)
        v =  diff.nbits() - 1
        
        # Did it change from a zero or to a zero
        if newcode & diff == 0:
            sign = 1
        else:
            sign = -1
        code = newcode
        
        # Find the new b
        b = b + 2 * sign * Bs[v]
        for j in range(len(solutions)):
            p = solutions[j][2]
            solutions[j][0] = (solutions[j][0] - sign * Bainv2[(v, p)]) % p
            solutions[j][1] = (solutions[j][1] - sign * Bainv2[(v, p)]) % p
        yield(a,b, solutions)

The main program

def quadratic_sieve(n, B=None):
    print "***** Initialization *****"
    if not B:
        B = int(ceil(exp(sqrt(log(n) * log(log(n))/2))))
    print "B: %s" % B
    smaller_primes = prime_range(3, B+1)
    smaller_useful_primes = [2] + [p for p in smaller_primes if legendre_symbol(n, p) == 1 ]
    reverse_table = {}
    for i,p in enumerate([-1]+smaller_useful_primes):
        reverse_table[p] = i

    K = len(smaller_useful_primes)
    print "K: %s" % K

    factor_base = [(p, sqrtmodp(n, p)) for p in smaller_useful_primes]
    
    sq = int(ceil(sqrt(n)))
    u = float(math.log(n)/(1.2*math.log(B)))
    print "u: %s" % u

    T = max(100, int(u^u * (K+1)* log(log(B))) // 20)
    M = max(100, T // 2^4, B)
    print "T: %s" % T

    print "***** Starting the sieving step *****"
    polynomials = make_polynomials(factor_base, n, B, T)
    global ones
    ones = {}
    B_smooths = []
            
    try:
        for (a, b, solutions) in polynomials:
            time sieve(B, n, sq, M, K, a, b, solutions, factor_base, ones, B_smooths)
            
    except Enough:
        pass
    ones.clear()
    print "Found %s B-smooth numbers" % len(B_smooths)
    
    print "***** Linear algebra *****"
    print "***** Building exponent matrix *****"
    values = {}
    for i,(f, _, _) in enumerate(B_smooths):
        for (p,e) in f:
            values[(i,reverse_table[p])] = e
    A = matrix(GF(2), values)
    print "***** Computing kernel *****"
    time K = matrix(A.kernel().basis())
    print "     Done computing kernel"
    if K.nrows() == 0:
        print "No dependencies found, go find more relations"
    for b in K:
        x = prod([B_smooths[i][2] for (i,k) in enumerate(b) if k])
        ys = prod([B_smooths[i][0] for (i,k) in enumerate(b) if k])
        large_primes = prod([B_smooths[i][1] for (i,k) in enumerate(b) if k])
        y = Factorization([(p,e/2) for (p,e) in ys if p!=1]).value() * large_primes
        print (x,y,n)
        factor1 = gcd(x - y, n)
        factor2 = gcd(x + y, n)
        if not factor1 in (1,n):
            assert(n == factor1 * factor2)
            print "%s = %s * %s" % (n, factor1, factor2)
            break
        else:
            print "Did not give a factorization"

print "QS defined"

QS defined

time quadratic_sieve(10807, 200)

***** Initialization *****
B: 200
K: 21
u: 1.46083317727
T: 100
***** Starting the sieving step *****
***** Initializing polynomials *****
Nr of primes used for a:  1
Starting sieve: $(11*x + 4)^2 - N$
Done sieving, controlling results...
* B 1 B B * B B B * 1 B B B B B B * B B B B 1 B * B B B B 1 B B 1 1 B 1 Got enough!
Found 31 B-smooth numbers
***** Linear algebra *****
***** Building exponent matrix *****
***** Computing kernel *****
Time: CPU 0.02 s, Wall: 0.07 s
     Done computing kernel
(-42884578231170357397822565760000, 29772692463541936747804491451068, 10807)
10807 = 107 * 101
Time: CPU 0.22 s, Wall: 1.27 s

time quadratic_sieve(7001 * 70001, 200)

***** Initialization *****
B: 200
K: 21
u: 3.14723708448
T: 100
***** Starting the sieving step *****
***** Initializing polynomials *****
Nr of primes used for a:  3
Starting sieve: $(7429*x + 2557)^2 - N$
Done sieving, controlling results...
* B * B * * B * B B B B B B * B B B B 1 1 B * B B 1 * 1 B * B * B 1 
2*M: 400, K: 21, supposedly smooth: 400. Relations found: 24
Time: CPU 0.05 s, Wall: 0.05 s
Starting sieve: $(7429*x + 809)^2 - N$
Done sieving, controlling results...
* 1 1 * 1 1 1 * 1 1 Got enough!
Found 31 B-smooth numbers
***** Linear algebra *****
***** Building exponent matrix *****
***** Computing kernel *****
Time: CPU 0.01 s, Wall: 0.01 s
     Done computing kernel
(1257948739896674687069649211258835208263978406, 1159983594834130763429110927363158413045760000, 490077001)
490077001 = 70001 * 7001
Time: CPU 0.12 s, Wall: 0.33 s

time quadratic_sieve(2^67 - 1)

***** Initialization *****
B: 12589
K: 732
u: 4.09940098255
T: 26735
***** Starting the sieving step *****
***** Initializing polynomials *****
Nr of primes used for a:  5
Starting sieve: $(24039899*x + 29080396)^2 - N$
Done sieving, controlling results...
* B B B * B B B B B B B B * B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B * B B B B B B B B 1 B B B B B B B B B B B 1 B B B B B B B B B B B B B B B B B B B B B B B B B 1 B 1 B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B 1 B B B B * B B B B B 1 B B B B B B B B B B B * B B B 1 B B B B B 1 B B B B * B B B 1 B 1 B B B B B 1 B B * B B B B B B 1 B B 1 B 1 B B B B B * 
2*M: 25178, K: 732, supposedly smooth: 697. Relations found: 207
Time: CPU 0.94 s, Wall: 0.94 s
Starting sieve: $(24039899*x + 6889720)^2 - N$
Done sieving, controlling results...
* B B B B B * B B 1 B B * B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B 1 B * B B B B B B B B 1 1 B 1 B 1 B B B B B B B B B B B B B B B B B B B B B B B B B B * B B 1 B B B 1 B B B B B B B B B B 1 B 1 B B B 1 B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B 1 B B B B B B B 1 B B 1 B B B B B B B B * B B 1 B 1 B B B B 1 1 1 B B B B B B B B * B B B B B B B B B B B 1 B B B * B B B B B B 1 1 B B B B B B B B B 1 B B * 
2*M: 25178, K: 732, supposedly smooth: 670. Relations found: 423
Time: CPU 0.90 s, Wall: 0.94 s
Starting sieve: $(24039899*x + 4799294)^2 - N$
Done sieving, controlling results...
* B B * B 1 1 B 1 * B B B B B 1 B B 1 B B * B B B B B B B B B B 1 B 1 B 1 1 1 1 * B B 1 B B B B B B B B B B B B B B B B 1 B 1 B B B B B 1 B B B B B B B 1 B B B B 1 B B B B B B B B B B B B B B * B B B 1 B B B B 1 B B 1 1 B B B B 1 B B B B B 1 B B B B B B B 1 1 B B B 1 1 1 B B B B 1 B B B B B 1 B B B B B B B B B B B B B B B 1 1 B * B B B B B B 1 B B 1 B B B 1 1 B B B B B B B B B B 1 1 B B B 1 1 B B 1 B B B * 1 B B B B B B B 1 B B B B B B B 1 B 1 B * B B 1 1 B B B B B 1 B B B B B 1 B B B 1 B B 1 * 1 B B 1 B B B 1 B 1 1 B 1 B B 1 B * 
2*M: 25178, K: 732, supposedly smooth: 649. Relations found: 680
Time: CPU 0.84 s, Wall: 0.93 s
Starting sieve: $(24039899*x + 26989970)^2 - N$
Done sieving, controlling results...
* B * B B B * B B B B B B B B 1 B B * B B B 1 B B B B B B 1 B B 1 B B 1 B 1 B B B B B B B B 1 B B B B B B * B B 1 B 1 B B B 1 B B B B Got enough!
Found 742 B-smooth numbers
***** Linear algebra *****
***** Building exponent matrix *****
***** Computing kernel *****
Time: CPU 3.48 s, Wall: 3.48 s
     Done computing kernel
(1456501666845954072228672554123120446729515753246001064369418669222386092469362040591003200190157336781309918994222953859689122071462999747528556644523538032880555322378332456931278705489865967836425705565589824696478030273340756529600925320400206145274056843296527006044365871684748293485454884070083306642427219941953193664184527914858609307761324734521450569223415709494968944459625051678496802003900363155735234897713005168041052583706703082664135187535613136307354002588635312561215461513009487857439003128806500126352428723596706575586216994711501074064649373540434630397246940478667587489838475209642243415042988508179666459897347882760898811061707461698456650850623319020888134865711288174740875138420323973736525503554061706288762876422402062950515963774883405802773045417283697467590852929692049908221540362299047376258969057265895281535719377119176287095378424925997539014205321314446338965269321385656455219613647759585887181390679291427557439042367907431079324447680486135535606763640268954396012392857616045581477746378727783119907248548527855293720875779110890146302625660347054831949658709843699213270303657931130366479286611750255275831102719751965866099838109399931146973671988938169998290864010732783362256840051347513297856367953849912463903717067773705639596803771418168932364632314613270907760348212483176785388081656934328903336613166184080080896000000000000000000000000000000000, 2947765142125589673175855642584392045176567931445193439531532670986385216328755416460036445411027959517948985564660751201909239818774874279830109397902989850232447874750029975827230506666734141306476611111067509843917394740398006768871397490884024173644932613368467855149234585291629204071661120337287967588881947382786907702668438604809486905334050229737705413263067027624134885045380238721817555791546683967033480433021776702186468314725576043336101275115426625717390406404451130470335611075977025445830983460930547119198207244231486466207037129363704523711040278438868837222712797680829528960324706999915893302477696915198246522242878048635645540142003306556433777600970551175788532186610957422227734504616187873823649801736633245189481578771148181725397213319387590632508591410332750753403724731703080932160319175634972757693069183049083903663636963079106049455155568539546781565566192098107209266224127316751898701585453280301163644510638476974461920760231338519763141454270957229421595007915378846864651910469697242824038223288703261093052550843574038514859377086085993270652230376999333545815936419849101623970380883154402512713970464232584419638957636220259705141755250728300776323483680676289279588734570176254206129327501850926165730953396534617013129348202653727385438324663029111815409272469024204629417639193913833298113734734324881752850119682886654105257088592053053472734564552015872, 147573952589676412927)
147573952589676412927 = 761838257287 * 193707721
Time: CPU 7.27 s, Wall: 9.32 s

bitlength = 120
a = random_prime(1 << (bitlength // 2))
b = random_prime(1 << (bitlength // 2))
n = a*b
print "Will factor %s * %s = %s." % (a, b, n)
time quadratic_sieve(n, 16019)
#time factor(n)
#qsieve(n, time=True)

WARNING: Output truncated!

full_output.txt

Will factor 24045464845378387 * 672842206272442417 = 16178803617410847374165141033841379.
***** Initialization *****
B: 16019
K: 949
u: 6.78000649636
T: 46613005
***** Starting the sieving step *****
***** Initializing polynomials *****
Nr of primes used for a:  7
Starting sieve: $(548528136599*x + 1298035305146)^2 - N$
Done sieving, controlling results...
* B B B B B B B B * B B B B * B B B B B B B B B B * B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B * B B B B B B B B B B * B B B B B B B B B B * B B B B B B B B B * 
2*M: 5826624, K: 949, supposedly smooth: 149. Relations found: 149
Time: CPU 24.06 s, Wall: 24.06 s
Starting sieve: $(548528136599*x + 995399091850)^2 - N$
Done sieving, controlling results...
* B B B B B B B B B * B B B B B B B * B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B * B B B B B B B B B B B B * B B B B B B B B * B B B B B B * 
2*M: 5826624, K: 949, supposedly smooth: 155. Relations found: 304
Time: CPU 24.03 s, Wall: 24.39 s
Starting sieve: $(548528136599*x + 674309450914)^2 - N$
Done sieving, controlling results...
* B B B B B * B B B B B B * B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B * B B B B B B B B B * B B B B B B B B B B * 
2*M: 5826624, K: 949, supposedly smooth: 177. Relations found: 481
Time: CPU 24.15 s, Wall: 24.47 s
Starting sieve: $(548528136599*x + 976945664210)^2 - N$
Done sieving, controlling results...
* B B B B B * B B B B B * B B B B B * B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B * B B B B B B B B B B B B * B B B B B B B B * B B B B B B B B B B * 
2*M: 5826624, K: 949, supposedly smooth: 153. Relations found: 634
Time: CPU 23.92 s, Wall: 24.21 s
Starting sieve: $(548528136599*x + 543225742248)^2 - N$
Done sieving, controlling results...
* B B B * B B B B B B B B B B * B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B * B B B B B B B B B B B B B B * B B B B B B B B B * B B B B B B B B B B B * 
2*M: 5826624, K: 949, supposedly smooth: 155. Relations found: 789
Time: CPU 24.34 s, Wall: 24.83 s
Starting sieve: $(548528136599*x + 240589528952)^2 - N$
Done sieving, controlling results...
* B B B B B B B B * B * B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B B B B B B B B B * B B B B B B B B B B B B B B B B B B * B B B B B B B B * B B B B B B B B B B B B * B B B B B B B B * 
2*M: 5826624, K: 949, supposedly smooth: 153. Relations found: 942
Time: CPU 23.86 s, Wall: 24.05 s
Starting sieve: $(548528136599*x + 561679169888)^2 - N$
Done sieving, controlling results...
* B B B B B B * B B B B B B B B B * B B Got enough!
Found 959 B-smooth numbers
***** Linear algebra *****
***** Building exponent matrix *****
***** Computing kernel *****
Time: CPU 1.74 s, Wall: 1.76 s
     Done computing kernel
(-64269407609995384852341310359106291991143499058597760810319799656737893092677136205253964183048124287669947546172908142174149760753965822207785322440779987734022186031540755893038738723103284014051361353652264291843718328462623131523351260944450763990825709406322979402247371068543247529316461492360447514421838140662097713379284272689086308368620520363519572521327646960240730003334617003909433346244171306523440839315720274623236111470420603745703776891909238507912091140492001990141519988445410467370869121710712093352114767851936611246245896360223956491217493588127765447419849238750873413379429952398058426704702531385664999507761563647731022559131626635082074926812417006453714430702098798777878554136589828991408773942242911695256658016137068201083035478501564581916472362335536434087660844288058560431494341636784332243229905411290095206358953833465782783204159328000824104624210406326097395765316275030928942289079249307998415826228761277547943035508169022969907337792016122765680829253970646273600350227688596716167942959990976437386344167054767477161235742310333685292412935625643118160986090623442053204662852765349847410239488895401477997150140593450531508056569894452903459485297017821492481289994871937597797098819654430901791774725254425031555747559051875598999791689321845939436172871044882302130574415517044492737444138859955383255591606670845870747430293311457798500222888817416907150402946158396748739811370833673729979656433140404505046709798058473890629221877993954423625396926722045689582699834099523019116757637239505101275622064368824289375736622969554785572854454944651376703297947478405312114410648586716576603474315694615819582642634463807564094244868713220794786384878975020054497009036508724630741661900902859343248188043215383628264079210765422218932483132751216707224244994982796961365365491552958904334328752465015245097798708702516514245401927191594909141129184929444809493733676050235553763510768678849448637169204581452102028344109707267598920399341240306868427134244158025172428217170684172947050202321426327630009157263056838936514205102003618707095165881295679140045752265697105174032078079374652416435163759103077005586225795982724996538182090909349148439193399916451493772588335616326042428399216283803041753062463304339705794313846596065313409676379740116768152930786456328237662808601120944750272201704593221421768580419201861654132188539740535259569263102433935688638560960184347677383162057731344272793376582426649020832862610823128945484305495854532057441024515773721882518231077399197613183663312004892329067780227253228655943573752573126992286629423854739090853231275127471391572202276776859477554868167673399530011878060978270052934710820050863934901827739058549866628443338928429870868851209056889591260761029164603342995281775819170535227081040072562152512698663735912616424473564362117166284562602000437073898263930059428280443626342907013912162765091581837028851855403584248736914873841063889953278874564455635704886236433334990022805662203141367791950463890614067757079714817597019100397216936132627912837430511667254538737277877081893045374637519561973559711383616755907908878418559938713377485388352875583237200021212598218415256310046512731520028702784095857684186336773294887639789938672809203283144931753402957113858930677582536016048794948569499408976442474867109079569088824585447080848661651439077264827591045254050255851246550426974011000179359573277554283789403707570134293860196760159373361015708727612383721712645633922586808466451366576083036154608198029958521420220569834007174802199003288748059387657675293769188462567596789064637070008846776878855301526595096127752391901174815241442047774613805602378411692108500112874509996463276491618449258948419178152941454904377412784702584891610715691313604039969441662574524520145888482594513112326848132764922320448029198277508830100089306248447715459659357510564594685444778343322734481631714403552031593193428828896457590816526504486658700394666019903711401257176629961807523759764788430048431590475995893485537045115610845855425433286662479604207206742673975826298827986825333649569195127426209088425699735580450727091762939491163237445442993567356378874707791716524175845353286026499908483302101402618801484233597412250847995900983894225257814726887777509305262022043544554136906785643015141110172062543559081670728018480506553079016745286150741294773134517676307566575567804239744848610489584903630741435153128838899714874547920377531750026964557427076566375955187017042161655387924504622653736471952651867070996706085203166322918883142115159204636950443272295873967301323567959380569982877507627741454965395888055282804555841152427803215110897115458324735701445914171325343774534946116741095411710034443662107408283805253138038970729890398216610525793064641922747237842949494964107545183352374443858849073098277679114198484501873008644817659272554073328168011210624817634064292556961436467412385609237871366821466395832051980981907230435503616730610807048734320793387901798882613620407804436484340203867675819618961927468345918071748260862187273484992619882955485050069944941660857851776206672468457876935553997949172497576374915799625731959740426191421430416058077954468612914942447540577951878924102736066847491853391823541584688258174175695951915899232583204383264564925971513073631870814379990404930757837430763516214948166035760020920640483428486586883131350902768419621899718436844602309296955118465327694214528455861499740395958050056358739041136097680529769668063419705576819354782676146842028456963827497213864324167031748518391163081438190783408717419520366339113195914603388474552910756994194417167246695601461029637180489868773782841015412127787998110067446646003305567136671626730047994911432414328709226891220431592637281858272607011388552818595462896056941305843017874792185686027413800474201543442350938010781214249773496988209070119257241661872425067504989687968973962847216780069056514531666724692483449497365106931166876552726443539589341301948121069788587155393009390501627221201609186490124140972986495062894243239960989738762677688549459645786924108108285091623394046112154652180943555562623924676015053308007882375314480456438085532985513117377691273395054237074198870556584434160660446559973653084019008880115463907403979471030831513651946090225658304564698700027071128238358450619213688887006517951691901697401226524728877398745473063785139361083608268800000000000000000000000000000000000000000000000000000000000000000000000000000000000, 35738199493672290215581504836534418972775889780949924038230031762591836453266006325836424220867252368979677415030952583209650143167409999556475101376573972983683015096288365784754237035370142634456630065122118798381423925413857377170615412345076945280771706441522692342878091159165929625513740619805885914424817619606858718454195829115426274258330219406075610968130217639190593768778140232013301466982475773191957493828122189346152890560111143983136587148886934976579527766766469654644734610651269762200919763463413423790107484870700112546631403963827289549647444613922109512285482437245452835189504848850431661577563036946553434659708468976091568407846770905398004868166622356348105720485711756081990094118442191474168517426842086874991459129998822822604648782125477107255395648508998458181575046988683260845440583902204980310149465881536655338278089328668391837519385008412174512509270696390496717690878916340053284587787409885207908729951284665705598890652551959876556992577351713455878323049116909767798733626608158222437119983601723771751180853866044221408147161229215786226016402545283801027958930839078179281368273098627126460209211655779461416780661932497433729355027970451160213694615054540308861761849988581615177782402154582879987788952272065045362878409571614367854702425960010995982369906304402008265019836031466012794775600339491146118863638508959023353602850885369599317946717100245003693932975028240844510042385212304382953051823186849392985799129687558260455719808507182141597141438992655720261608117460190418131544393576506356336245275651835837252026944487383054783814413983363350631195514023482066690990778696059577785527968372294347863107629318888827761090061866842344956943769067628737908351642995342346543644430654324805089696556500529191883642048324349978801841598744923741020902834716372058706651185645782959643757059015575454932608401669542628189262300700033783436492802031908094909512265685744290269128519142225626725920211779909791108041584840866622437669431491768010953232881329745118388386797634009641336827104429766089070588110859076734978404263934857702161493019504719141748111634988000731564993429449520462061541459586210127262524928679258488394373673085555441188246777009706886175085017849827288203912310773897831615028143195879984558893000899548856251537692479753747344423241264813535405975085608110642446472256992321836835227222878116128775804090865673605848938127669705664532980689126320998504390583996795386426126963327300350724829370584663183811700816290824738826627070185689972025532021977168007848065562188567316999972559650437021229895908935974158810223554239789339981384922750819618756508619575717338381067829761834149349330953309097838841105966163153470967295298177390318012553591690775533644907964060157084193139306581893065579344923502125408375570195418225136478714229129486313161076217728874092183731646019521631358947176544664500407544322985762863441766451786685171853833391296888498240031776876185241861101636336830650538196221490561717326113190440476089681333490606723377573923547734409636619014089939485853289465685884196087449494638478337928227720932262500402693884838556917641351697525310587290117122481052635111588378270327718849728426821658068356835660435057852287712420306187457327253677916878361140426832512299051823068148546345514302607203504964384712698730248691495852088766694359452615516133806489098465818053855839430718800316368182634469124120449894202709022706134457076225688814823622099335736846246400894769948412180524781476382500457629852566951488819732760460432868529031566196746055341356104847253536805456398038948699420710559130092943042135073046904443815857860568841780867732756767800971255788642317068786641548511407375409898343872396248988086288834278894066567854130020573825059075315341995560457103476053380181378827930095181640593245156652918280126835453852395216477611734891725814173085892942993206863560335598592678097674998552024722076492095295264302512839621996042170175822475375964396015403125382754665643363295198372623826363744526436970924124302382744276663658870766180454369646467563558024368226339932787836418213894997005911226907313983224199317591938274998675706656503405433683378929825250620063907501426188148167132599286435908777307569810091261173261294200353375920357257379594482654385727619641409571805558276579854777191569515779178137806717548841304218766423282169912665114209705337789621115258568033269192187745286279542553328438902671762455833042776190179718189409803772434327399441108900040231155952416493392312772781571998966305381503464110532488556551913314220673684331260524702893793684889262004161934972824461244651690262206978262372106312665788150959664501513398186436163175576608870570676336877608104086857935485163582073627048358064693881955550764928094031817126430896775102010328590470208950997281947097374264249974622045268756911068422989231084922424985576799672922154976323840105857452058176475666486027390137860079171745436847241599833804898164975922537628009581463479350050337822235045815374780442844623148778474728478564348837262193453252306884197341447631643516167714727896345940892008888259965696530797065807031147364862357140925101174801735935343462024874212405881998377833926808553507645556071753623304299620566290909606225196089958408850074348165413972218845412097259534298094096461669200223210751757689490769721898944655179665572783356566086356342784788435443560392309648725697228054529520680522291923856385598971971340931020459886922019319861860451991596979207787088965359919166296062959769114940195967134374811595622259513289974114534800466252914832423166878295793078882190046141086826457606098916272162032167637042230149008504575175467765592026016904796353439468118092505889497104760066824604095222624811305225196249822774539614176991

...

730702562416079460027523879578917747288628672210149189842571312110094164236716782279920258106372190146953149659763775167059126817440151734390278138331389359339555058135423700498338923984451899647280533907646738921562264702873843642875581997412457967841571794546957920661500562368455090259464688432487010522965847440490095060491361605931026788264685868778443138861504504709025071939920497089086684095615338563571843501593173142132383992942410647415973317785217327636924014135066079223432571799174641042077969166337100962420068020023184631727716845435549061510441534851734117661246963305430076833723151615288292434903854551562292479622645966251443117702111057246765902867852080797198978617712023398896338982735790786069576255282990032216732131549139677602884878457194682524218162828200908893725037935938500940087194249000039749057427466119619200054050240565224398218311607950885040986131624016861015096999911051042794779258828646295871745497656771578467316446564446634136123469888366996515764270624159296339136031058078744614330694726514774016648638746657732181975579200325666487830541940678487789677278226377799318847143408527299819375781176351151799460050222942923468811425054609160515704436385225410517820828010852647890019517814675377018767162972652762655430189418637889221867607181257286498600633034648442245395282164726121851841159669848475018498147906079290179584542125833024942245214723686213291398501746171512451834286621936201386818858918928262967532538661633545237111644405928476089868502006298180749777655512174501903011419806491204211109084367079165052840183272937731738829581236432718228083774650083168115097076714854778221951501887077439648053287694214200095569122886246174700836496091658379774778722817446659755727634429931640625000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L, 16178803617410847374165141033841379)
Did not give a factorization
(-550829992395603721225260554259715835918419438385683160541127489474879881612489214856013786381395641718979956716444523300270480226033033476940561631366657044797980110280504288782948585943864162536767322178070950320830937542212801747689161289466600558127418088089873682643595904619799867423987937672868065191694653696274939781465852253855681992028398844416762003297075186169879494640945510247110593983782857595480908776238326898533020793968029501537921581028753681387235596326575633036999712347861466158897134667010997018572551845432039286067895771943975209532052643774752289843222593915193671351843804449622970363123805249800386028734175081948658458434492464959423095911764299232832307742589320726070324981930770888888375421668725439613810124799344434173868855426479977742280600669054839795631252811242979752244355920378283210776902497138324055366747543632122125770020255021360520170553162231077682702858859521346584956650361650845005291564621507392238228428256772557073575444868739127314455384188432548766978819649598453656402025126752430838844439520709894903845329217995086921012154983533376894263967299630948018448208291741211642550036561378457453822599330765876773806627775539477996093913058301061973383775153805861845245003607757464269362598658040732812690617833480538888988309546504101543613795374988911613715707359343284812975175988888890364451562733816064508301113834666068416025693712363196090184165375374626952862745763311593169654441720604868551540545493259570723585369206806495164668152408695938923297995662668949521739226403679694044420488826479256369429867459964376396496734807604082567737549139410089989542865213519077700912140941653813502453747088300392537454159576580488942607183453003805232899531512522465424115456844423606616920757681114389690139432816288444631951593545213012676279536456864113037787320696552518834945976763809448113999158571391809393936137770058991789465559564383273345876807734796211104948240944990296071765538714996596769595057364755155164252925833406702147983184490201258046707657538206283612094053042099489920923379626652773251887010701599792403527968788872577816820880335984471066613729340504218855056593311633571582739221869926996426712907867135636793766378975399571116174192084891136408018537789068043403870450064990263353625337675973267062487139655971593363940041268721429229332164822536455175647142748059941236016745143443141131029693159558899564171016251386141190119459832154368784091884579766187611955804780000390981936893794307776936708930441965911855582105930617226116964774751540513204932017037061954506503500670801028033311591393893182261822793534717103433787719993768383159734153791634943101605729171012532286761141887180632598972481724028061442342886273720778533992786464304558172081505229087673350300018321638477107966709381363532276326655986968246264207850902772983751339152047111694317192105524221721889891862137269464073064383198990227031950325894741165988373437024761323538806226427351539909473068255391195524288649466308872712247592344081455242892993802176426481401293022914888836989025749814045673143348567698856281764132181868273782947344040834377550511447840284000403782924617503207279115216677494881157038737262320750551850618601253862112921250799701672642046819106120449650207189582112976183615857695513732803323768460355775195027273759697597189426901215590288625232610671829654430320383720859950107385327244840546659578826850262593681243267715951221157890230748567401010033292191375475300006277537817867962876671905757268443953140648804935160673930299576260066574860972153907615778290201932138275356580216022281769571499488487148228821016089409755846022304846986775831387631553417976757858570337416600213196902939123419358606331025012180399394491602789805106599063653722551567077075801224523743011390650782009520774175974295642805265554188505944882756521611608532376213925647688427831774830938650508278919738927532488321767052513917230737538724777534951293210047269876736668080273710003723079547484342039564663670213678947596131104821948833582976469976499024800133978094154518339302392947309365101341817340380849618316225520776551349877173923301456044051568744478575890278204823781025650039557291493645805077395539956518465243669846399535024468659446380500886315876342133932839819397123616067377409436698805453159882213132014944409628541392987167249622459540435542099605580181996297980026365178176836958576078084629345688066879194009573481401137917249849981128952829413446897010660145331055799283999336078192029250370486967946513227527546640389435796613325082885797407088335767257829917322566410612570548243786794657832174696417112820113355530627591612554041491304298482423242769415098168148572778398232330810345687058819161441572382680121762732176296959984597254547714167779893524890595535057438618884265680072731611575161567673801610812313644744907767805491620051623207487719081150883826919805341861110580270542868789101362754646069549579489379446269116712460326056110837594395903000940679926423946180697745692655388883904047293775717131589598720832652540448577944671602584809321160632410855921709255914232561963491642849253037525905871199900459910751773980826009779285093935106879394696777203627712986026847363298585830099762871037624450501103324518737978368894682195622815016585842590271727616181704058768560887757289018215725039297948927228569201688087890965691629677033255104398776172475731560315875282003242669956423891977999790678380831030176899650056170588991297715509777119771156504486050445350339460531693959547428899446132164502932386513688163982959691790363751002980851467630774209524145524603729873735034174343736556104617716867953946163856954820229068403502666614643105253833321422794607698818903737189328628808189622745640277497345418207128204441011597384018727586361972813979755035667427891887947666197836963454047433952693383795266718097635127093727781671054460403000232922180777950824010455762999767339587507987558372369675438686273160304347582884068601706744091743778082749126419600384612064265402662903410618408863324333867946996513546614793958367749701652986444941970022266578223636326977572296897221001015970195214449950171379827018298815768947577632974322004411595366875731641793992999258657754347565393094717806758303222160148960423367343586681600782467885135455280188073750160045485278416087404321864771557909639855133138136416115836343810930802634564671300194414535079247219068191291432903958557145223311351236398599507412853281814544276619183726953114814780839403485868278786758928396942115009501203264369128309370360365607596323538384308002104248704451528867150100435312651328034581611315919994543739154173953924159048411380478478125456230484742031321818237656507483923811354816559991047238063121461403977971969924544301532651427588906837417774653023500100686328378170596632356483904806391780588405000027538856024882589328855586845354154364937403121034338887358632409786573030779217854414800814080000000000000000000000000000000000000000000000000000000000000000000000000000, 54029781124381203196512495166417270218301626491490644623434370176160834098065807118755215148999739084027231732891343946633830982172450864499928072412920731713947751091923477554338195184067267303614138581951595167071837904264282153379190390470720117579801272890670444083143481241053654772585661243256182684455519502331053587229341059367081629199179189617025221572265578692668383957931328622273588244690958711152280694603622377304108764845975960771702233741373399524742827332093557013347438299630186553469465348613068034354572026514321111695481813931051126613490304397632026743277914207898780365799830536048180687388673906164138854413566164192943172818308484772302373569721876781476688430026841575189188367449888674227823289109945536445734649853382915878318739981531314217200178657375408766035630818929447591678946997586264632642427475866837048243368633546979726662591271884733005031532543439214354174241481592295063575160245549635918364338753461684312821616488997450197622330991284055711512899145105247890450916694214546780543484073609739782525289211795396296615198570922945998360208034497797225923240330470239250488697635224043306181930939596344131873784889571551948418678832719266979768518723035440308842471369504250570276294124210549768916926159977406604719568019179744943427929168618814792055469101102986507928962340308201060711393544521979176050919631976221499532780381656236951112180660534394337301181589491827635437760799326608028468397552425793374322954850968327460140618670503381866777909009278978831295181929857462319112856784725335132615484478859677583051954929127188970029653994424249057614644336471013978647011745665788917576495099040923882749497677368908862973906033395742683907725366979966713965963792975476437530204195763240517093126298953443597547815416713447515997050590079845904229948786343207784253252850265827745350142429157336347665682387657946634911560084146617324163101359891092846675035084562971969479475100007196922686882995617953758837188522617383709732853247605759916849036926537312711898099961983272971635676642493570543509648877329889041787086587713153455957170324026858867332960533061611100563651780511848849075483219826271117497726544458345620152034395665512915202179064744512524238214424687713545635036656393101796875497363868229005130838132549655390966161519568081746774792337344042315719708994552573975584799934728301636040244683610185258994972295924416463163552808305353227698681686043660793752987710519464599130675460404294070241634350388055226172034611571058164571726466752335194362549656161897935339496284717417320811717495861902034926884469966523181110567472007487961688934633732592482571825200130716953654658579693459027982757268989847224107746932636190497581584687463596664565587384585195228674720345354584785458688974679269924997737793854443567661162792162287521342966215036034075678710670875962610874803806799377076488815633537814965852585333789626116316149080680097380321083160727895756396653648205292272170115332917319234753680391294979215118351510768929760182564376380053070299626812323374980831871485537764497734407268530069473952517506552699533142090897807134328002837937097968322195107371933999297654771963420645858386673822846557850254269451436830680569426696474355299212875766753841911342355342029856042817286742151436968160639591734886776687261086431139725529995415253750634559228569096445494855324015202539148938670193936744473833119714393073859022434426695955213501140358537177792429846755888627562513008948254766924754464825573014471650981300274342223400966393681946557430670732891200748172776627923577309427873366592373625514320467210793668882593470853052548976074086324433381167106193286815747554567125343958379622460116397951964913168038778906288498194067652429258265028027003593699431966970990346542820300088854595340521923289200848526192085274633659356911317335888607354235547252084509645197440190902330599498081931702936398571708943908426363067430319958836941694609909808704457891446226685274019477105065901947779618745965959826514119300177049140710918995395124839116927889062871550392423875093331834260204880243333702732518044990379594942846410187854263802361152454496290765452463535395730705082602890882960016609556185536425376056149527337476787338155280028202503951262542994606967549849856550053187977509561006641144682213654276702555794923465788616505557656171921441251400291303501980738845942390133236903787890748039380382189832984257637454043568362220649996967344980363218895343458406901942995063545034849222339099173579207795942142524591156826605825481779180352035726960926076384979671130397366726898323962281869119873978752698527327602663816266012818625573977430275384728665275632463410414975461799958380701843733834686391707818920526754652989521720037129480022157340789404333813216288425977996050931025714327975754507596595646983494379908500893311732087575918340287230087936083359964586175828977466541076576430931551478692428833705762387939312034400049501523319043556911520599005295705185930924220009068724959392413684965958395437941675048015482312724889045137612165624248388260707481094966614985845147550082592848772351657300429654167672517375786371597833675620897852180440275475825278767516720766159427080003000845923988314873698455137343506597080484166447291232378393322307766695135500386796303212371341059508822564210177713448967635191816505242735702064433974450770729891335917958011348897516055438672357998911221463747528571546090870853179748135285888447899014085759633168822834248419921859657295404542264410807107312130809970082018514452421374045979927428930503618423839617139295786072054714799153768293662421677723716729838746825386464956585648480468743656190496856472079000162727365573096380388489393194197593058078083581579216137268112356178459705929945428996530193980185750270778860967990262938040358070122144319283234545213596859741455068430879366139759889402664903555029352754346752792878412302514636310174172766276950725656826895489826717469050024887436812068020441469118963848367260560953448833586930011325526908841549842523847671513538278076546030777219575392279220273003439520995742986942141704387252536662812674254013048542345491098262104644422837641525442710151533786725960454741185742510509213168232985167463456801965766235226985523056545539786484523001032602906571337498563314980689548296480572080371964465939473653277418142225864695717589447004480010618236542133872707721048579223365415479754152636580739518057977214138708860424001401283899379874746440056753370792962579752679578300631328756521465477542534403903904588075841132908782001494060215052981898873763990790071075341403313547017891264922433254830012600718185332064885290758623120069661580232827128036453059398192898319673258307560508957057849749009971281175798843003818693806180577081956274404527613040956279425366815322145007214931807307524152351320231473232001973672196736329861614294641995727554485201835632324218750000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L, 16178803617410847374165141033841379)
16178803617410847374165141033841379 = 24045464845378387 * 672842206272442417
Time: CPU 171.82 s, Wall: 178.25 s