20170228, 16:03  #12 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110001100_{2} Posts 
Thanks for pointing out the dead link! That is the correct paper. I find it an interesting method, and it turned out to be useful for a small range of tiny composites to maximize performance. For native ints outside that range I don't use it however (after trial and power detection I find Brent/Rho, P1, and SQUFOF are the methods that work best for me). I don't call it at all for my general factoring of larger inputs, but it's useful to have available.

20170228, 19:14  #13 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10671_{10} Posts 
Indeed.
Back in the heyday of MPQS I started a search for algorithms optimised for factoring double large prime residues. If you don't know what that means, it's essentially composites known to be the product of two primes of roughly comparable magnitude. If Fermat's method stands a chance, it's here. My experiments showed that Fermat was pretty good, though slightly inferior to SQFOF in practice. Pollard rho wasn't bad but the P \pm 1 methods were hopeless on average. Needless to say, trial division wasn't in the running. Peter Montgomery joined in the search and broadly reproduced my findings. Eventually a carefully optimised ECM proved to be the best and, AFAIK, it's still used today. 
20170228, 22:13  #14  
"Ben"
Feb 2007
3,433 Posts 
Quote:


20170301, 00:09  #15  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
16EC_{16} Posts 
Quote:
I don't know if CADO uses ecm. It might. 

20170306, 11:23  #16 
Tribal Bullet
Oct 2004
3537_{10} Posts 
CADO uses very highly optimized P+1 and ECM. Small MPQS was under development last time I looked.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Windows 10 in Ubuntu, good idea, bad idea, or...?  jasong  jasong  8  20170407 00:23 
Simple Script to get Trial Factoring Work  jfamestad  PrimeNet  3  20161106 20:32 
Simple factoring challenge + questions  siegert81  Factoring  12  20160528 18:36 
This simple algorithm incomplete can only calculate prime numbers?  Ale  Miscellaneous Math  38  20151129 23:27 
Simple Idea for SIQS  ThiloHarich  Factoring  5  20060316 08:22 