Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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

share|improve this answer
    
The additional modulo operation of $(x + a) ^ n \bmod (x^r - 1, n)$ might come from the deterministic primality test. –  Someone Mar 2 '12 at 16:08
    
@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. –  poncho Mar 2 '12 at 17:09

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.

share|improve this answer
    
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... –  Someone Mar 1 '12 at 10:40

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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