mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2017-11-09, 16:13   #78
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

10118 Posts
Default

Quote:
Originally Posted by henryzz View Post
Could Bernstein's method be useful for splitting large primes in SIQS or GNFS? It is certainly possible to have a lot of numbers to factor simultaneously. I get the impression that memory usage would be an issue for GNFS at least.
This is also what I am interested in. (though I guess you mean splitting the auxiliary ("Q") numbers instead of primes?)
I found that TIFA tried it: https://hal.inria.fr/inria-00188645v1/document
But cross-reading the paper I didn't find anything about results for SIQS.

In total, I think that Roberts approach is addressing a special case of what we were considering here. Very interesting if you can assemble many numbers to factor at once, probably not that interesting if you can't do that.

Anyway, good job!
(didn't manage yet on my own to implement Bernstein studd)
Till is offline   Reply With Quote
Old 2017-11-09, 17:26   #79
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Liverpool (GMT/BST)

7×859 Posts
Default

Quote:
Originally Posted by Till View Post
This is also what I am interested in. (though I guess you mean splitting the auxiliary ("Q") numbers instead of primes?)
I found that TIFA tried it: https://hal.inria.fr/inria-00188645v1/document
But cross-reading the paper I didn't find anything about results for SIQS.

In total, I think that Roberts approach is addressing a special case of what we were considering here. Very interesting if you can assemble many numbers to factor at once, probably not that interesting if you can't do that.

Anyway, good job!
(didn't manage yet on my own to implement Bernstein studd)
It wasn't very clear about SIQS with and without. It also sounded like their implementation wasn't that optimized. I plan to experiment with this method as part of my own SIQS implementation.
henryzz is offline   Reply With Quote
Old 2017-11-09, 18:23   #80
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×52×71 Posts
Default

The small-MPQS implementation in CADO-NFS uses batch factoring. Msieve's line sieve uses remainder trees to rapidly detect whether hits from sieving would make valid relations, before attempting to find 2 or 3 large prime factors with SQUFOF and MPQS. In a sense this trades off increased memory to remove QS as a bottleneck, because 95% of the time with NFS you will not find relations with three large primes such that all the primes are small enough.
jasonp is offline   Reply With Quote
Old 2018-03-15, 17:32   #81
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1110100010112 Posts
Default

Quote:
Originally Posted by jasonp View Post
My pleasure, consider it public domain and include anywhere.

The code has nothing to do with RDS' original sieve, it was part of an early project to build a line sieve suitable for kilobit-scale GNFS. I never did anything else with it and dusted it off when there was a chance RDS would contribute to the group effort for sieving 2,991- if his code could be overhauled to scale up to problems that large. Unfortunately just adding 3LP cofactorization wasn't enough to make his lattice sieve scale up to handle large numbers, but at least the code is out there.

ISTR the SIQS code that is in the Franke-Kleinjung sievers was twice as fast as this when I last benchmarked it a lifetime ago, but it does have a 96-bit limit.
This code is excellent! I spent some time working with it recently, just to see if any of yafu's SIMD tricks would help at all. It turns out that they do help a little bit. Parameter tweaking made a larger difference. Here is the end result on a Xeon E5-2647 machine w/AVX2 :

Code:
Bitsize	   original	           new	     speed ratio       spBrent
           (sec for 100k)                                    
55         35.2                    13.6      2.59              9.8
58                                 16.4                        16.9
60         43.2                    18.2      2.36              23.6
64         49.7                    21.6      2.31              48.6
70         54                      31.2      1.72              --
80         85                      57.1      1.49  
                                                                         
Bitsize	   original	           new	     speed ratio  
           (sec for 10k)                                        
90         15.5                    9.89      1.56  
100        28.1                    19.5      1.44  
110        51.6                    41.0      1.25
On this machine at least, spBrent now crosses over to siqs as the fastest method for semiprimes starting at 58 bits. Brent-rho or some other method is still needed as a backup because there are occasional siqs failures (4 or 5 out of 100k).

I will commit the code to the yafu project, as this is far and away better than my current smallmpqs routine, and of course you are welcome to incorporate any of the changes as well to msieve.

Last fiddled with by bsquared on 2018-03-15 at 17:37 Reason: some numbers fixed
bsquared is offline   Reply With Quote
Old 2018-03-15, 17:59   #82
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×52×71 Posts
Default

Quote:
Originally Posted by bsquared View Post
I will commit the code to the yafu project, as this is far and away better than my current smallmpqs routine, and of course you are welcome to incorporate any of the changes as well to msieve.
Thanks. Now I feel bad because in the last flurry of interest I did update some of the internals to have variable-size sieve intervals, achieving a speedup that sounds comparable to yours.

I've committed what I have and maybe that can inform your own changes. I don't have the time to continue, so if you want you can host the official version of this.

Last fiddled with by jasonp on 2018-03-15 at 18:10
jasonp is offline   Reply With Quote
Old 2018-03-15, 18:33   #83
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·17·73 Posts
Default

Quote:
Originally Posted by jasonp View Post
Thanks. Now I feel bad because in the last flurry of interest I did update some of the internals to have variable-size sieve intervals, achieving a speedup that sounds comparable to yours.

I've committed what I have and maybe that can inform your own changes. I don't have the time to continue, so if you want you can host the official version of this.
No worries, thanks for the update! I'll take a look and merge as appropriate.
bsquared is offline   Reply With Quote
Old 2019-07-08, 19:06   #84
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·17·73 Posts
Default New contender

I've been playing around with ECM lately and I thought I'd try to implement a toy version that works for inputs that fit in a single machine word (64-bit). Here are timings for lists of 100k random semiprimes compared to other methods explored in this thread:

Code:
Bits   ECM     Lehman  Brent   Factor64    SIQS
42     1.03    0.65    1.31    1.32       
44     1.19    1.18    1.73    1.75       
46     1.41    1.63    2.27    2.35       
48     1.72    2.67    3.15    3.25       
50     2.17    4.31    4.35    4.54       
52     2.82    6.89    6.1     6.29       
54     3.33    10.7    8.5     8.82       
56     3.97    16.8    11.9    12.5       
58     5.02    26.5    16.9    17.6        16.44
60     6.25    42.2    23.6    24.8        18.2
62     7.57            33.1    35.2        
64     9.83            48.6    53.1        21.6
It scales quite well, crossing over with Lehman at around 44 bits and remaining well ahead of all others up to 64 bits. Combined with a bit of trial division I imagine it would work well for arbitrary inputs too.
Attached Files
File Type: c tinyecm.c (39.3 KB, 202 views)
bsquared is offline   Reply With Quote
Old 2019-07-08, 21:18   #85
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts
Default

Quote:
Originally Posted by bsquared View Post
I've been playing around with ECM lately and I thought I'd try to implement a toy version that works for inputs that fit in a single machine word (64-bit). Here are timings for lists of 100k random semiprimes compared to other methods explored in this thread:

Code:
Bits   ECM     Lehman  Brent   Factor64    SIQS
42     1.03    0.65    1.31    1.32       
44     1.19    1.18    1.73    1.75       
46     1.41    1.63    2.27    2.35       
48     1.72    2.67    3.15    3.25       
50     2.17    4.31    4.35    4.54       
52     2.82    6.89    6.1     6.29       
54     3.33    10.7    8.5     8.82       
56     3.97    16.8    11.9    12.5       
58     5.02    26.5    16.9    17.6        16.44
60     6.25    42.2    23.6    24.8        18.2
62     7.57            33.1    35.2        
64     9.83            48.6    53.1        21.6
It scales quite well, crossing over with Lehman at around 44 bits and remaining well ahead of all others up to 64 bits. Combined with a bit of trial division I imagine it would work well for arbitrary inputs too.
How does it (all of them, actually) compare when splitting QS/NFS cofactors where it is
known that the smallest factor is large, e.g. > 10^8???? [or perhaps only 10^7]
R.D. Silverman is offline   Reply With Quote
Old 2019-07-08, 21:23   #86
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
How does it (all of them, actually) compare when splitting QS/NFS cofactors where it is
known that the smallest factor is large, e.g. > 10^8???? [or perhaps only 10^7]
Also, how does it compare with a combined method, e.g. trial division to bound B,
(say 10^3) then ECM. Also, how do you select your parameters? Are you using 2-step
ECM?
R.D. Silverman is offline   Reply With Quote
Old 2019-07-08, 21:26   #87
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·17·73 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
How does it (all of them, actually) compare when splitting QS/NFS cofactors where it is
known that the smallest factor is large, e.g. > 10^8???? [or perhaps only 10^7]

If I understand you correctly, that is what it is currently doing. The inputs are each composed of two primes of roughly the same size. For example the 56-bit row in the table means all of the methods are fed 56-bit inputs composed of two 28-bit primes (roughly 2*10^8).

Last fiddled with by bsquared on 2019-07-08 at 21:26
bsquared is offline   Reply With Quote
Old 2019-07-08, 21:30   #88
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

749610 Posts
Default

Quote:
Originally Posted by bsquared View Post
If I understand you correctly, that is what it is currently doing. The inputs are each composed of two primes of roughly the same size. For example the 56-bit row in the table means all of the methods are fed 56-bit inputs composed of two 28-bit primes (roughly 2*10^8).
Ah. A semi-prime is an integer that is the product of two primes. You said "random"
semi-primes. The factors of a semi-prime need not be nearly equal.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring Mersenne numbers paulunderwood Miscellaneous Math 18 2017-08-27 14:56
Factoring Big Numbers In c# ShridharRasal Factoring 10 2008-03-20 17:17
Question about factoring code Peter Nelson Software 9 2005-03-30 18:28
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57
Questions about SSE2 code and Factoring Joe O Software 2 2002-09-13 23:39

All times are UTC. The time now is 23:40.


Fri Dec 2 23:40:58 UTC 2022 up 106 days, 21:09, 0 users, load averages: 0.87, 0.78, 0.84

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.

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