Factoring Algorithms for Exponential Speed | Tips & Advice

  • Context: Graduate 
  • Thread starter Thread starter paradigmjump
  • Start date Start date
  • Tags Tags
    Speed
Click For Summary

Discussion Overview

The discussion revolves around factoring algorithms, specifically those that operate at exponential speed. Participants are exploring comparisons between different algorithms and their efficiencies, particularly in the context of factoring large numbers.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant inquires about factoring algorithms that achieve exponential speed, expressing a need for comparison with their own algorithm.
  • Another participant suggests that trial division could be considered exponential, citing the number of attempts required based on the length of the number.
  • A different participant clarifies that they are referring to reducing beyond the root exponentially, which they argue significantly decreases the time needed for factoring large numbers.
  • There is a challenge regarding the clarity of what is meant by "reducing beyond the root exponentially" and whether this approach is indeed better than existing algorithms, which are suggested to operate below exponential time.

Areas of Agreement / Disagreement

The discussion contains multiple competing views regarding the efficiency and classification of factoring algorithms. There is no consensus on the definitions or the effectiveness of the proposed exponential approaches compared to existing algorithms.

Contextual Notes

Participants have not fully defined their terms, such as "reducing beyond the root exponentially," and there are unresolved questions about the assumptions underlying the comparisons being made.

paradigmjump
Messages
2
Reaction score
0
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
 
Physics news on Phys.org
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.
 
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,
 
Which reference, and what do you mean with "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.
Better than existing algorithms? Those are way below exponential time...
 

Similar threads

  • · Replies 13 ·
Replies
13
Views
2K
  • · Replies 9 ·
Replies
9
Views
5K
  • · Replies 51 ·
2
Replies
51
Views
5K
  • · Replies 2 ·
Replies
2
Views
3K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 11 ·
Replies
11
Views
4K
Replies
3
Views
2K
Replies
41
Views
5K
  • · Replies 14 ·
Replies
14
Views
2K
  • · Replies 3 ·
Replies
3
Views
6K