mersenneforum.org Some code for factoring numbers up to 2^63
 Register FAQ Search Today's Posts Mark Forums Read

2017-11-09, 16:13   #78
Till

"Tilman Neumann"
Jan 2016
Germany

10118 Posts

Quote:
 Originally Posted by henryzz 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)

2017-11-09, 17:26   #79
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

7×859 Posts

Quote:
 Originally Posted by Till 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.

 2017-11-09, 18:23 #80 jasonp Tribal Bullet     Oct 2004 2×52×71 Posts 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.
2018-03-15, 17:32   #81
bsquared

"Ben"
Feb 2007

1110100010112 Posts

Quote:
 Originally Posted by jasonp 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

2018-03-15, 17:59   #82
jasonp
Tribal Bullet

Oct 2004

2×52×71 Posts

Quote:
 Originally Posted by bsquared 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

2018-03-15, 18:33   #83
bsquared

"Ben"
Feb 2007

3·17·73 Posts

Quote:
 Originally Posted by jasonp 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.

2019-07-08, 19:06   #84
bsquared

"Ben"
Feb 2007

3·17·73 Posts
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
 tinyecm.c (39.3 KB, 202 views)

2019-07-08, 21:18   #85
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts

Quote:
 Originally Posted by bsquared 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]

2019-07-08, 21:23   #86
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts

Quote:
 Originally Posted by R.D. Silverman 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?

2019-07-08, 21:26   #87
bsquared

"Ben"
Feb 2007

3·17·73 Posts

Quote:
 Originally Posted by R.D. Silverman 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

2019-07-08, 21:30   #88
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

749610 Posts

Quote:
 Originally Posted by bsquared 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 18 2017-08-27 14:56 ShridharRasal Factoring 10 2008-03-20 17:17 Peter Nelson Software 9 2005-03-30 18:28 Axel Fox Software 14 2003-07-04 18:57 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