Efficient probabilistic algorithm for integer factorization given bounds for one factor

[Georgi Guninski]

Efficient probabilistic algorithm for integer factorization given
bounds for one factor

Me and Stefcho Guninski released preprint [1] Efficient probabilistic
algorithm for integer factorization given bounds for one factor.

We are interested if the algorithm can be improved and possibly compete with
zncoppersmith.

The sagemath code is at [2] and can be run in a browser.

The main idea:

For real $x$ and natural $N$, define $J(x,N)=\sin{\frac{\pi N}{x}}$.

The real zeros of $J$ are $\frac{N}{a}$ for integer $a$.

The integer zeros of $J$ are the divisors of $N$.

For real constant $D \ge 2$ and $N=pq$ with $\log{q} \approx D \log{p}$
and given bounds $B_1 < q < B_2$ and $ 0 < q-B_1,B_2-q <
q^{\frac{D-1}{D}}$ we find the factor $q$ in time polynomial in
$\log{N}$ using real root finding of the function
$J(x,N)=\sin{\frac{\pi N}{x}}$

To find the unique zero, we use mpmath's function
|mpmath.findroot(J,B\_1,B\_2)|
Experimentally it finds the zero $q$ efficiently using real root
finding in the range (B_1, B_2)

[1] https://www.researchgate.net/publication/386602587_Efficient_probabilistic_algorithm_for_integer_factorization_given_bounds_for_one_factor
[2] https://sagecell.sagemath.org/?z=eJyNVNFO2zAUfW6k_MNVJaSkmC6JWjayGWltNTQEFQ-gPSBAoXVSi8RObBeVPeyv9gP7sl07oYXBwx7iJOde33Ny74n7_b7vXSh5n93zkmvDF5CVhVTcrCrIpQIuDCuYgjxbGIR_ZoZLAQV_ZALu5VostU3zPSkYyBzMinWp2ve-rs1KqhTghElVcDhZCy70A_e974IbnpWg2CPXWDCFc6w6YwuAI4iTdDxKx2O4OIeryykkUTLyPd-70lnBUBDYe5WZVep7e2otcl4y0Fy0vMnQhn3P8IrBnExiMklowQwmxLrKyjJIBoNRFJER0YwtaRz63vTiCmy-TmGt8WNHw_gjaAL6CZHD0Qj-_MY3I01Wpl3Q935gLbfLQZ8sZJlTh4GKqZblI7O0QScj_Kzit2TJeHgE1TNbBGJH1YVecSWHDunbwfker2qpDFS17Yfv5UpW3QtsQzkpZeF7LTys6mGtmDFP9FKtma2xZDm8atCEzAjb0KhtUEQwnX7LSs1C7HjPMfcKJpjKDDa-ctqYNotMM1TWm9N60BCo4RdMCDS43s4QbuAApjF8gcZd-zBNCGRiiSCZJha7RdKguQ1mB3H4YRZabb0ZHFPARBtq8a0EnoMViP7SzNwpLCWrO4sEdsHtvZp2aK2wd8HEYs0_2GBgmVrRdktCsWNBE7YESEsjZMC7hbcKzmjXzryUUgU1eipgm9Ducp9Dry0L_jxBQtqUszB0P9SddfB1TJKbG0yexLRODqaxfUzwcX-atMRCGvw7DFLjulbi2coYfQ2QmjTbKUq5DDZk7uZU0GKxROu19Khtb96WLo7jXdliV9CN-LnUW_PuZt-uNusU6-5qdS3BXUH3WPPB_MPGdmXnvmWtKRoymFvYqKc3-3MulkpKE5ySoKW2mWyzYPWLfkRWaav1nonFqsrUg_Ni7PzbWbfkFY2jF9oRAKM4c8dWZ97tgfXfxnInY2QnidGCBVjVcfTePXBQj93UU_KdM8EG0IroFB4RN0AlcYLhX2tsoZw=&lang=sage&interacts=eJyLjgUAARUAuQ==