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.


closed as primarily opinion-based by e-sushi Dec 16 '17 at 19:57

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.


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.

  • 2
    $\begingroup$ What do you think the intended audience is? People with plenty of time? $\endgroup$ – Someone Mar 1 '12 at 10:42
  • 1
    $\begingroup$ More or less, the authors write themselves that they say nothing of immediate practical interest, but only of academic interest. $\endgroup$ – Henrick Hellström Mar 1 '12 at 10:44


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.

  • $\begingroup$ My strong concerns towards the paper come from the tables in the appendix. They only have tiny examples where calling FAC(n, 1) etc. small made little sense as they are about the size of the square root of the prime factors. But of course as the numbers are so tiny, FAC(n, 1) has also the size of $\log(n)^2$ times a little constant... $\endgroup$ – Someone Mar 1 '12 at 10:40

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).

  • $\begingroup$ The additional modulo operation of $(x + a) ^ n \bmod (x^r - 1, n)$ might come from the deterministic primality test. $\endgroup$ – Someone Mar 2 '12 at 16:08
  • $\begingroup$ @Someone: the use of the additional modulo operation was certainly inspired by that use of the modulo within the AKS test; however, the current authors fail to justify why the polynomial coefficients might be interesting. The AKS test uses the fact that if the result of that is not congruent to the polynomial $x^n + a$, then $n$ is not prime; AKS says nothing about what the polynomial may be if it is not congruent, and the paper gives no justification (either theoretical or experimental) for us the expect the coefficients of that polynomial to be at all interesting. $\endgroup$ – poncho Mar 2 '12 at 17:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.