9
$\begingroup$

I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS.

And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms are TDM, FFM and VFactor.

Which of these is actually right?

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ This conference looks like a paper mill… IEEE is a big organization; its name alone means very little, and it is well-known that many of its publications are essentially academic scams. Except for a single (unused!) citation about the NFS, the authors of this paper appear to be completely unaware of any developments in integer factorization in the past thirty years. Throw it away; ignore the conference; nothing is to be learned here except a lesson about perverse incentives in publish-or-perish academic culture and profiteering academic publishers. $\endgroup$
    – Squeamish Ossifrage
    Apr 4, 2019 at 1:47

3 Answers 3

Reset to default
12
$\begingroup$

The IEEE paper is silly.

The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Well I think the point of the paper is to improve upon Fermat-Factoring class algorithms, so it is expected that the given algorithm(s) get beaten by the more standard ones for small sizes, but excel on large inputs with (relatively small) prime differences? $\endgroup$
    – SEJPM
    Apr 2, 2019 at 15:04
  • 4
    $\begingroup$ @SEJPM: if that's the case, then they probably shouldn't go on so much about RSA (where the probability of having a sufficiently small difference is tiny) $\endgroup$
    – poncho
    Apr 2, 2019 at 15:11
9
$\begingroup$

Which of these is actually right?

Both. From reading the abstract it appears the papper doesn't claim that "VFactor" or Fermat Factorization ("FFM") or Trial Division ("TDM") are the best methods in general. However, if the difference between primes $p,q$ with $n=pq$ is really small, like $\ll2^{100}$$\;\dagger$, then FFM (and probably the VFactor variants as well) will be a lot faster.

Though in general the difference between two same-length random primes is about $\sqrt{n}/2$ which is about $2^{1024}$ for realistically sized moduli, so these attacks don't work there. Even with 400-bit moduli, which are somewhat easily crackable using a home desktop using the GNFS, this difference is still about $2^{200}$ and thus way too large.

Of course the implementation of the key generation may be faulty and emit primes in a too small interval and it's in these cases where these specialized algorithms really shine.

$\dagger$: "$\ll$" meaning "a lot less" here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Actually, the claim in the paper is wrong. It states it is superior to Fermat in general, which is not true. Both VFactor and MVFactor are modified trial divisions, while Fermat covers a lot of potential trial divisions in 1 step. For a given maximum difference, there is a length, s.t. Fermat finds the result in 1 step (although it gets worse for later steps and has the same complexity in O-notation). The tested results don't even state the number of trials and thus are probably 1 each. $\endgroup$
    – tylo
    Apr 11, 2019 at 15:03
6
$\begingroup$

Quantum algorithms

There is of course Shor's algorithm, but as this algorithm only runs on quantum computers with a lot of qubits it's not capable to factor larger numbers than $21$ (reference).

There are multiple apparent new records using adiabatic quantum computation, although some are apparently stunts: See fgrieu's answer on a related question.

Classical algorithms

The general number field sieve is the fastest known classical algorithm for factoring numbers over $10^{100}$.

The Quadratic sieve algorithm is the fastest known classical algorithm for factoring numbers under $10^{100}$.

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ Actually, the factorization of 56153 was a stunt; the factors were deliberately chosen to have a special relation (differed in only 2 bits) and it's easy to factor when the factors have a known relation. AFAIK, the largest number that has been factored to date using a generic quantum factorization algorithm is 21. $\endgroup$
    – poncho
    Apr 2, 2019 at 14:55
  • $\begingroup$ I've always wondered why QS is (at least, consensually said to be) faster than GNFS below a certain thresold (not so consensual), and how much of that is due to lack of work on optimizing GNFS for smaller values. $\endgroup$
    – fgrieu ♦
    Apr 2, 2019 at 15:42
  • 1
    $\begingroup$ @poncho As far as I know, all quantum factorization claims to date are stunts, including the 15 and 21 claims. They do a trivial calculation on a tiny quantum computer and then find a tortured way to argue that it factored a prime since that sounds better in the press release. That was the point of the 56153-factorization paper (Quantum factorization of 56153 with only 4 qubits by Dattani and Bryans). $\endgroup$
    – benrg
    Apr 3, 2019 at 1:44
  • 1
    $\begingroup$ @poncho The paper with the 21-factoring claim is Experimental realisation of Shor's quantum factoring algorithm using qubit recycling by Martin-Lopez et al. I just skimmed it, and as far as I can tell, their actual experiment used a single qubit and a single qutrit. Can a machine with $1 + \log_2 3$ qubits run Shor's algorithm on the input 21? They say yes in the title, but I would say no. Dattani and Bryans agree that the factorizations of 15 and 21 "were not genuine implementations of Shor’s algorithm". $\endgroup$
    – benrg
    Apr 3, 2019 at 1:45
  • 1
    $\begingroup$ Er, factored a composite. $\endgroup$
    – benrg
    Apr 3, 2019 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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