Real world complexeties

[kruoli]

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?

[ThiloHarich]

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?

[kruoli]

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).

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.

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".

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.

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.

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.

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.

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.