20220410, 00:22  #1 
"Oliver"
Sep 2017
Porta Westfalica, DE
11×89 Posts 
Real world complexeties
When trying to evaluate an "optimal" factoring strategy, real work complexities are much more important than theoretical complexities. For example, I got
\[e^{1.21\sqrt{\ln p~\cdot{}\ln\ln p}}\] is the estimated amount of work I need to find some factor \(p\) with my system ignoring the composite's size. How does one find a general answer to this (with different sizes of composites) for e.g. gmpecm, msieve/CADO, yafu's QS etc.? In the following, a function \(t(\dots)\) represents a function returning how much time a computation needs assuming one core and no side effects.

20220415, 18:30  #2 
Nov 2005
103 Posts 
What is your system/algorithm?
Do you have a runtime analysis for it? How did you came up with the Lnotation? Where does the magic number 1.21 comes from? Is it based on some measurements on some runtimes? If so how big were the numbers you let it run on? The runtime for algorithms not combining some relations (x^2 = r) mod n usually is expoential. i.e. n^e with e beeing a constant > 1/4. The ECM is the only not exponential factoring algorithm working good on numbers with a small factor, I know of. If you have such a kind of algorithm it would be of real interest. Do you have some factorings on big numbers with low factors? Is it faster then QS, NFS, ECM on thoose numbers? 
20220415, 19:04  #3  
"Oliver"
Sep 2017
Porta Westfalica, DE
11·89 Posts 
In the meantime, I found that with my system and YAFU version, I get
\[\mathcal{O}\left(2^{\frac{\log_2{n}}{12}}\right)\] for SIQS (empirically tested from 128 to 320 bits). In general, I would like to apply this to different systems. The measurements I did were on a 5950X. The algorithms I would like to examine are at least trial division (which is rather simple), ECM, SIQS and NFS. I would assume the runtime analyses found in the literature are the way to go. On top of that, there will be implementationdependent runtimes for integer addition/multiplication/etc. But these might not lead to a "good real world approximation". Do you mean why I used the Lnotation at all or how I came up with my example? The former: I assumed you can roughly apply Lnotation even in real world scenarios. The latter: coming up in the next answer. Quote:
Since for the first step, I only wanted to get the expected B1 to find a factor (with I 1 increments), I used the smallest numbers possible for each candidate. Quote:
I am not sure what you are asking here. When given a "random" number, the most efficient way to factor it is using nondeterministic algorithms first and if these fail, use SIQS/NFS. Last fiddled with by kruoli on 20220415 at 19:40 Reason: Reformatting. Some corrections. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Hmm, is this real?  kriesel  PrimeNet  17  20200910 04:59 
Real world problem, involving the the surface of the earth.  Uncwilly  Programming  21  20150425 20:20 
Is this for real???  kurtulmehtap  Math  2  20140929 14:16 
real people at last  Kathegetes  Lone Mersenne Hunters  17  20120722 13:54 
Is this guy for real?  CRGreathouse  Math  21  20100823 18:05 