Is the new preprint “An Algorithm For Factoring Integers” by Yingpu Deng and Yanbin Pan worth reading?

Question

I just discovered on the eprint server of the IACR the paper mentioned in the title. Scanning quickly over the paper I didn't find anything spectacular, so I doubt that their new(?) approach will be any good. But as I'm not an expert in the field of factorization, and as the proof for Primality $\in$ P is also deceptively "low-level", I wonder if someone here with more knowledge about factorization could quickly judge if the paper is worth reading.

---

EDIT: The paper I'm wondering about seems to be connected to the polynomial time primality test by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. So please be sure to know (or better: understand) the AKS-test before answering here.

Answer 1

Actually, from my examination of the paper, I don't know if the result is of even academic interest.

One generic way to factor a value $n$ is to take a function $F$ and define:

for i = 1 to some_upper_limit do
    temp = F( n, i )
    factor = gcd( temp, n )
    if 1 < factor and factor < n
        output factor; halt
output Failed

This will work for any function $F$. In essence, this is what they are doing; they are computing the various polynomial coefficients $a_i$, and checking if those have a factor in common with $n$.

There's nothing wrong with that; however, it does beg the question: is there a reason we would expect that those specific $a_i$ values to yield factors more often than, say, SHA512? Well, looking at the data they provide, it appears that the number of $a_i$ values they test before finding something are about the same size as the factors (which is about what we would expect for a random function), so experimentally, it doesn't do better than SHA512 would be expected to.

Now, their argument behind the algorithm appears to be that, if we were able to get at the coefficients of $(x + a) ^ n \bmod n$, that some of those are likely to yield nontrivial factors; and while that is impractical to evaluate, why don't we evaluate something related. However, they compute the coefficients of $(x + a) ^ n \bmod (x^r - 1, n)$, and I don't see any immediate reason to expect that the additional modulo operation would not mess up the coefficients (especially since the coefficients we'd like to see are not the lower ones, but the ones greater than the smaller prime factor, which is much larger than r).

Answer 2

No.

The paper reports success factoring integers of 13 digits 15 digits in an hour, or of the form $n = p\cdot (p+2)$, which are factored in seconds with existing algorithms (Pollard rho or ECM, Fermat). There is no comparison of the proposed algorithms against these classics. The proposed algorithms are useless as a direct method for factoring numbers of cryptographic interest.

Answer 3

If you have to ask, you are probably not the intended audience. Quoting the introduction of the paper:

We implemented our method on a PC using Shoup’s NTL library version 5.4.1 [7]. Unfortunately, we have to say that the practical effect of our method is not good on a single PC, it is worse than many known algorithms on this problem. However, we believe that our method yields interesting phenomena, and it is worth for further study.