Skip to content

Instantly share code, notes, and snippets.

@grocid
Created May 3, 2020 17:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save grocid/c9229df90e2821b8bf36e8d0311f2d18 to your computer and use it in GitHub Desktop.
Save grocid/c9229df90e2821b8bf36e8d0311f2d18 to your computer and use it in GitHub Desktop.
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