mersenneforum.org Real world complexeties
 Register FAQ Search Today's Posts Mark Forums Read

 2022-04-10, 00:22 #1 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 21008 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. gmp-ecm, 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.How can you find $$t(c, p)$$, where $$c$$ is the composite and $$p$$ the factor to be detected for ECM, P-1 and P+1? How can you find $$t(c)$$, where $$c$$ is the composite when looking at NFS and SIQS?
 2022-04-15, 18:30 #2 ThiloHarich     Nov 2005 23·13 Posts What is your system/algorithm? Do you have a runtime analysis for it? How did you came up with the L-notation? 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?
2022-04-15, 19:04   #3
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

108810 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).
Quote:
 Originally Posted by ThiloHarich What is your system/algorithm?
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.
Quote:
 Originally Posted by ThiloHarich Do you have a runtime analysis for it?
I would assume the runtime analyses found in the literature are the way to go. On top of that, there will be implementation-dependent runtimes for integer addition/multiplication/etc. But these might not lead to a "good real world approximation".
Quote:
 Originally Posted by ThiloHarich How did you came up with the L-notation?
Do you mean why I used the L-notation at all or how I came up with my example? The former: I assumed you can roughly apply L-notation even in real world scenarios. The latter: coming up in the next answer.
Quote:
 Originally Posted by ThiloHarich Where does the magic number 1.21 comes from? Is it based on some measurements on some runtimes?
I ran thousands of curves on numbers with existing factors, every time running something like ecm -I 1. Then, I had a look at the B1 values the factor was found, used the median, and saw that applying 1.21 as a constant fit my data best. Of course, this does not mean that this value is correct, it only was fine with my data. The general formula was taken from Wikipedia, but I replaced $$\sqrt{2}+\mathcal{o}(1)$$ by my empirical value of 1.21.
Quote:
 Originally Posted by ThiloHarich If so how big were the numbers you let it run on?
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:
 Originally Posted by ThiloHarich Do you have some factorings on big numbers with low factors?
Yes, I have some Aliquot data I want to examine.
Quote:
 Originally Posted by ThiloHarich Is it faster then QS, NFS, ECM on thoose numbers?
I am not sure what you are asking here. When given a "random" number, the most efficient way to factor it is using non-deterministic algorithms first and if these fail, use SIQS/NFS.

Last fiddled with by kruoli on 2022-04-15 at 19:40 Reason: Reformatting. Some corrections.

 Similar Threads Thread Thread Starter Forum Replies Last Post kriesel PrimeNet 17 2020-09-10 04:59 Uncwilly Programming 21 2015-04-25 20:20 kurtulmehtap Math 2 2014-09-29 14:16 Kathegetes Lone Mersenne Hunters 17 2012-07-22 13:54 CRGreathouse Math 21 2010-08-23 18:05

All times are UTC. The time now is 22:06.

Thu Aug 18 22:06:54 UTC 2022 up 19:35, 0 users, load averages: 1.58, 1.49, 1.44