mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-04-10, 00:22   #1
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

11×89 Posts
Default 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?
kruoli is offline   Reply With Quote
Old 2022-04-15, 18:30   #2
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

103 Posts
Default

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?
ThiloHarich is offline   Reply With Quote
Old 2022-04-15, 19:04   #3
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

11·89 Posts
Default

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 View Post
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 View Post
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 View Post
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 View Post
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 View Post
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 View Post
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 View Post
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.
kruoli is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hmm, is this real? kriesel PrimeNet 17 2020-09-10 04:59
Real world problem, involving the the surface of the earth. Uncwilly Programming 21 2015-04-25 20:20
Is this for real??? kurtulmehtap Math 2 2014-09-29 14:16
real people at last Kathegetes Lone Mersenne Hunters 17 2012-07-22 13:54
Is this guy for real? CRGreathouse Math 21 2010-08-23 18:05

All times are UTC. The time now is 00:20.


Mon May 23 00:20:25 UTC 2022 up 38 days, 22:21, 0 users, load averages: 1.32, 1.27, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔