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)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment