20171109, 16:13  #78  
"Tilman Neumann"
Jan 2016
Germany
1011_{8} Posts 
Quote:
I found that TIFA tried it: https://hal.inria.fr/inria00188645v1/document But crossreading 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) 

20171109, 17:26  #79  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
7×859 Posts 
Quote:


20171109, 18:23  #80 
Tribal Bullet
Oct 2004
2×5^{2}×71 Posts 
The smallMPQS implementation in CADONFS 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.

20180315, 17:32  #81  
"Ben"
Feb 2007
111010001011_{2} Posts 
Quote:
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 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 20180315 at 17:37 Reason: some numbers fixed 

20180315, 17:59  #82  
Tribal Bullet
Oct 2004
2×5^{2}×71 Posts 
Quote:
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 20180315 at 18:10 

20180315, 18:33  #83  
"Ben"
Feb 2007
3·17·73 Posts 
Quote:


20190708, 19:06  #84 
"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 (64bit). 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 
20190708, 21:18  #85  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×937 Posts 
Quote:
known that the smallest factor is large, e.g. > 10^8???? [or perhaps only 10^7] 

20190708, 21:23  #86  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:
(say 10^3) then ECM. Also, how do you select your parameters? Are you using 2step ECM? 

20190708, 21:26  #87  
"Ben"
Feb 2007
3·17·73 Posts 
Quote:
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 56bit row in the table means all of the methods are fed 56bit inputs composed of two 28bit primes (roughly 2*10^8). Last fiddled with by bsquared on 20190708 at 21:26 

20190708, 21:30  #88  
"Bob Silverman"
Nov 2003
North of Boston
7496_{10} Posts 
Quote:
semiprimes. The factors of a semiprime need not be nearly equal. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170827 14:56 
Factoring Big Numbers In c#  ShridharRasal  Factoring  10  20080320 17:17 
Question about factoring code  Peter Nelson  Software  9  20050330 18:28 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 
Questions about SSE2 code and Factoring  Joe O  Software  2  20020913 23:39 