20150813, 19:30  #34 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
163C_{16} Posts 

20150813, 20:00  #35 
Bamboozled!
May 2003
Down not across
2^{4}·5·127 Posts 

20150813, 20:30  #36 
"Robert Gerbicz"
Oct 2005
Hungary
10101011010_{2} Posts 
http://cr.yp.to/papers/sf.pdf
If you have nonspecial numbers then see section 6. If you have lots of numbers then see section 7, I had a direct implementation of this in gmp. 
20150813, 22:14  #37  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
2^{2}·1,423 Posts 
Quote:
The paper Robert linked to made a valid point about ecm being potentially faster. Could a similar study be done with fixed curves/bounds of ecm be done similar to https://millerrabin.appspot.com/ finding small sets of curves that will find all factors < y. For what size y would this become faster than trial division? With B1=1e4 B2=1e4 it seems to take only ~89 curves to find all the factors of 1000000#/2 Last fiddled with by henryzz on 20150813 at 22:24 

20150814, 09:46  #38  
Bamboozled!
May 2003
Down not across
10160_{10} Posts 
Quote:
More productively: if you can prove that all factors must have a specific algebraic form, as do factors of Mersenne numbers for instance, that can surely be exploited to speed up trial division. Another simple, but still only linear speedup, is to use a wheel of a size which fits a SIMD machine such as a GPU. Note that phi(11#) = 480 which may well match a GPU quite well. 

20150814, 10:14  #39  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
2^{2}×1,423 Posts 
Quote:
In addition to methods I was looking for code programs. This seems a bit of a hole in the available programs. Something like the method starting at the bottom of page 159 could be interesting. The problem being finding the small quadratic residues. https://books.google.com/books?id=4...0gauss&f=false Last fiddled with by henryzz on 20150814 at 10:19 

20150814, 14:02  #40  
Nov 2003
1110100100100_{2} Posts 
Quote:
Of course you might actually learn something by writing one for yourself. GMP is readily available for the arithmetic. Trial division is simple. Or are you just too lazy? 

20150814, 15:05  #41  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT)
2^{2}×1,423 Posts 
Quote:
However, I don't have the time or experience to fully optimise them. My aim really is to fully understand the methods. I am hoping that someone has already worked on a version that is well optimized. Maybe later I will go back and create my own version. 

20150814, 15:33  #42  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Trial division is simple. And the optimizations are mostly done for you via GMP. 

20150814, 15:54  #43 
Sep 2009
2^{2}·3·5·31 Posts 
Odd perfect related roadblocks are of the form (p^q1)/(p1) where p and q are odd primes.
I assume you are looking for a way to prove a given roadblock has no factors below a certain bound. I can remember a discussion where I suggested running P1 with B1=1e6 and B2=1e12 should find all factors below 1e12. Someone (possibly Batalov) said that could miss factors where P1 has a prime power greater than B1 and gave a way to get round that. But I can't remember when it was or find it by searching the forum. I hope this jogs someone's memory. Chris 
20150814, 18:08  #44  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Links to Factoring Projects  rogue  Factoring  20  20141119 01:08 
Links to Factoring Programs  rogue  Factoring  32  20090917 11:40 
factoring programs  henryzz  Factoring  6  20070919 13:47 
looking for Fermat factoring programs  ixfd64  Factoring  1  20050908 12:13 
any good GNFS factoring programs?  ixfd64  Factoring  1  20040427 09:41 