closefactor.py

import os
import math
import random

import multiprocessing

THREADS = multiprocessing.cpu_count()

def close_factor_worker(n, delta, ub, ret):

    def isqrt(n):
        x = n
        y = (x + 1) // 2
        while y < x:
            x = y
            y = (x + n // x) // 2
        return x

    f = 4 * THREADS
    phi_approx = int(n - 2 * isqrt(n) + 2)
    phi_approx += (-phi_approx) % 4 + 4 * delta

    h = pow(2, phi_approx, n)
    ub = ub // f + 1
    N = isqrt(int(ub)) + 1
    M = dict()

    # random walk function setup
    k = 0
    b = pow(2, f)
    while (2**k < N**4):
        r = random.randint(1, N)
        M[k] = (r, pow(b, r, n))
        k += 1

    # first random walk
    H = pow(b, ub, n)
    c = ub
    for i in xrange(N):
        r, e = M[hash(H) % k]
        H = H * e % n
        c += r

    # second random walk
    t,H,d,res = H,h,0,0
    while c - d >= 0:
        if H == t and ub > c - d:
            res = (c - d)*f
            break
        r, e = M[hash(H) % k]
        H = H * e % n
        d += r

    if res:
        assert(pow(2, res, n) == h)
        print res
        phi = phi_approx - res
        m = n - phi + 1
        roots = (m - isqrt(m ** 2 - 4 * n)) / 2, \
                (m + isqrt(m ** 2 - 4 * n)) / 2
        assert(roots[0] * roots[1] == n)
        ret[delta] = roots

def close_factor(n, ub):
    return_dict = multiprocessing.Manager().dict()
    jobs = []

    for i in range(THREADS):
        p = multiprocessing.Process(
            target=close_factor_worker, args=(n, i, ub**2, return_dict))
        jobs.append(p)
        p.start()

    for proc in jobs:
        proc.join()
    return return_dict.values()


if __name__ == '__main__':
    n = 2462649746477364143454082050368305440553491900304388646893610847386194301369924385009730987303651345060031438478297733694036327257723431468649220444397635127530301992505638291521092898714917678389314956983918603221732358628680256253537449204312287724750669208856634711056863315465220853759428826555838536733
    print(close_factor(n, 10000000))