Created
May 3, 2020 17:46
-
-
Save grocid/c9229df90e2821b8bf36e8d0311f2d18 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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