Is there an algorithm for factoring N, which is just as simple as this one, but faster?

Question

I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA (paywall-free).

It basically works like this:

• You reverse the digits in $N$, let's call this value $Ň$

• You pick an integer, $k$ (normally 1, but can be other values)

• A variable, $Δ$, can be any integer value between the square root of $N$ and the square root of $Ň$

You then calculate four values, if any return a value other than 1, then you have one of your prime factors:

• $\gcd[N, (k × Ň) + Δ]$
• $\gcd[N, (k × Ň) - Δ]$
• $\gcd[N, (Δ × Ň) + k]$
• $\gcd[N, (Δ × Ň) - k]$

Using this algorithm and the GMP library, it would factor 18014417929109603 in 3 seconds.

I was wondering if there were any other algorithms which were faster than this, but just as easy to implement? I know the GNFS is the fastest, but it is also incredibly hard to implement.

Answer 1

Pure nonsense. For choosing the random $\Delta$ between $\sqrt{\min(N, Ň)}$ and $\sqrt{\max(N, Ň)}$ there are too many possibilities for it to work. For example whenever the first and last digits of $N$ differ, you get something like $\frac{1}{10} \cdot \sqrt N$ possibilities (the exact formula doesn't matter).

So you can replace the first formula $\gcd[N, (k × Ň) + Δ]$ with $k=1$ by this one: $\gcd[N, \Delta]$. Try all $\Delta$ between $1$ and $\sqrt N$, the number of possibilities is within some small factor.

Compared to the division, computing $\gcd(N, x)$ has the advantage that at each attempt you try all factors of $x$. This is good in case $N$ has some small factors, which in case of RSA is surely not true.

I see no advantage of the linked algorithm to trial division. Trying all primes up to $\sqrt N$ is probably faster, terminates also when $N$ is prime, and has a bounded time.

Summary: pure nonsense.

Answer 2

Yes there are several algorithms, as simple or even simpler as the proposed algorithm, that are expected to factor $N$ much faster. The simplest and oldest is trial division by primes up to the square root of $N$ obtained using the Sieve of Eratosthenes. There's also Fermat's factoring method, preferably with the easy sieve improvement to recognize squares efficiently (which works when $N$ is the product of two primes $P$ and $Q$ with $|P-Q|$ of the same order of magnitude as $\min(P,Q)$, which seems the aim of the article). Arguably, the more efficient Pollard's Rho is on the other side of the simplicity threshold.

The algorithm proposed in the question and article essentially attempts to factor a semi-prime $N=P\cdot Q$ by repeatedly picking a pseudo-random integer $R$ smaller than a few times $N$, and computing $G=\mathtt{GCD}(N,R)$, until that is not $1$. The last $G$ is generally either $P$ or $Q$ (the only other possibility, $G=N$, is rare).

Odds of success at each $\mathtt{GCD}$ test is about $1/P+1/Q$ (thus less than $N^{1/2}/2$ steps are expected). For a 1024-bit RSA key odds of success per $\mathtt{GCD}$ may be $2^{-510}\ll10^{-153}$. The distributed attack envisioned at the end of the article expects to make $10^{14}$ such $\mathtt{GCD}$ tests, and thus has odds less than $10^{-139}$ to succeed. Hélas, I have no reason to doubt that the article was accepted in an IEEE-endorsed conference despite absence of practical interest and discussion about its (in-)efficiency.