Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Exponetial speed

  1. Dec 15, 2013 #1
    Is anyone aware of any factoring algorithms that factor in exponential speed?
    Working on improving mine and need a comparison.

    Have not had much luck finding such.
    Thanks
     
  2. jcsd
  3. Dec 15, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Isn't trial division exponential? For a number of length n, you need at most ##\left(\sqrt{2}\right)^n## attempts to find a factor and there is at most one really time-consuming step, so all other factors can be neglected. Assuming base 2, base 10 just changes this to ##\left(\sqrt{10}\right)^n##.
    Good algorithms are much better, so I don't see why you want a comparison with exponential algorithms.
     
  4. Dec 31, 2013 #3
    My reference is to reducing beyond the root exponentially. For very large numbers this greatly reduces time and makes factoring of large numbers possible within a useful period of time.
    Thanks,
     
  5. Dec 31, 2013 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Which reference, and what do you mean with "reducing beyond the root exponentially"?

    Better than existing algorithms? Those are way below exponential time...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Exponetial speed
Loading...