13 ms·

They only tested with numbers size of ~2^800, which is around 240 digits, but I believe (correct me if I'm wrong) there exists usages of RSA with over 600 digit

They only tested with numbers size of ~2^800, which is around 240 digits, but I believe (correct me if I'm wrong) there exists usages of RSA with over 600 digits, so it'll still take a massively long amount of time to factor those numbers...

munchbunny 6y ago
Typical key lengths for RSA these days are 2048 and 4096 bits. I don't know what that means for this paper, just happened to have those two key lengths off the top of my head.
- pkulak 6y ago
  So, 616 and 1233 digits, respectively.
  - ChuckMcM 6y ago
    Jinx! :-)
    - pkulak 6y ago
      lol. Oops. At least glad I didn't screw up the math.
      - r-w 6y ago
        You do have to remember to round up, since if log_b(n) = x.y then n still requires at least (x+1) digits to describe in base-b.
- ChuckMcM 6y ago
  2048 bits ~ 617 decimal digits, 4096 bits ~ 1234 digits.
paconbork 6y ago
It's worth noting that numbers of this size are already being factored with existing techniques. RSA-250, a 250 digit (829 binary digit) product of two primes was factored pretty recently: https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/202... Moreover, a 768 bit product was factored over 11 years ago, though it took two years to compute! https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge