mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Another factor algorithm using lattice reduction (https://www.mersenneforum.org/showthread.php?t=27096)

Till 2021-08-24 13:29

Another factor algorithm using lattice reduction
 
Hi all,
yesterday I found the following article: [URL]https://arxiv.org/ftp/arxiv/papers/1308/1308.2891.pdf[/URL]

It claims to present the fastest deterministic integer factoring algorithm, having complexity [FONT=serif]O[/FONT][FONT=serif]([/FONT][FONT=serif]N^[/FONT][FONT=serif]1/6+[/FONT][FONT=sans-serif]ε[/FONT][FONT=serif]).[/FONT]
Like Schnorr, the author is relying on lattice reduction methods.

charybdis 2021-08-24 14:03

This paper looks sloppily written and uses some unconventional terminology, eg "largest integer function" for what I presume is the floor function. More recent papers on the topic do not reference it. That should be enough to tell us that it's flawed. There may well be multiple errors; one conspicuous one is in equation (7), where the author seems to have cancelled out N with (floor(√N))^2. Of course if these two were equal then N would be square and we wouldn't be trying to factor it!

It should also be noted that these algorithms are only of theoretical interest at present, because QS and NFS, while technically non-deterministic, are much faster and almost always work in practice.


All times are UTC. The time now is 17:36.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.