5 ms·

Obviously this went way over my head, but what is the claimed time complexity here?

• ramboldio 6y ago
  "This proves the polynomial time bound."
  • ncann 6y ago
    I would be very skeptical if there is indeed a poly time algorithm for integer factorization. If that's actually what the paper claims then it's a very big claim.
  • dleslie 6y ago
    If true... Hot damn! There's NP-Hard problems that if we had polynomial time solutions for we could vastly improve the quality of life on earth.
    • gnulinux 6y ago
      Integer factorizatiom not proved to be NP-complete. It's been guessed to be "hard" for a while.
    • LeegleechN 6y ago
      Integer factoring is in a fairly sparse in-between zone between polynomial and NP Hard problems. This is why quantum computers can have a near exponential speedup from them (disregarding this claimed result) and only a polynomial speedup for NP Hard problems. So even if this result holds it can't be converted into a fast solution for all NP Hard problems.
      • dleslie 6y ago
        Ah, bummer. For some reason I thought it was NP-hard; thank-you for the correction.
      • hedora 6y ago
        Though, if conventional computers can factor in polynomial time after all, I wonder if that would suggest quantum computing is no better than a polynomial speedup.
    • sudosysgen 6y ago
      Which ones?
• thomasahle 6y ago
  It's hard to figure out what they are claiming, which makes the whole paper seem fishy. On page 14 they seem to claim a factor 2 improvement in the exponent of the quadratic number field sieve, which might be better that the general sieve for some N, but is still worse asymptotically.