McKee vs. SQFOF?

CRGreathouse · 2011-07-24, 19:15

I was wondering if anyone knew of a comparison of implementations of SQFOF vs. McKee's 1999 method. Both seem to be useful in the 10 to 20 digit range.

bsquared · 2011-07-24, 20:26

http://hal.inria.fr/inria-00188645_v3/

CRGreathouse · 2011-07-24, 20:53

Thanks, that was very helpful.

bsquared · 2011-07-24, 21:19

Thanks, I thought so too. It saved me from writing the fast return variant of SQUFOF, since in the size range I was interested in, it appeared to have a negligible speedup.

henryzz · 2011-07-25, 17:54

That paper compares the varying speeds of the different methods very well but it would be nice if it took a look at combining the methods for an optimal result. For example at what number of bits would we start doing a tiny bit of ecm or p-1 before siqs.
I am guessing the recent improvements in the smallqs code in YAFU are due to this paper.

2011-07-24, 19:15	#1
CRGreathouse Aug 2006 1011101011011₂ Posts	McKee vs. SQFOF? I was wondering if anyone knew of a comparison of implementations of SQFOF vs. McKee's 1999 method. Both seem to be useful in the 10 to 20 digit range.

2011-07-24, 20:26	#2
bsquared "Ben" Feb 2007 2·3·587 Posts	http://hal.inria.fr/inria-00188645_v3/

2011-07-24, 20:53	#3
CRGreathouse Aug 2006 3·1,993 Posts	Thanks, that was very helpful.

2011-07-24, 21:19	#4
bsquared "Ben" Feb 2007 6702₈ Posts	Thanks, I thought so too. It saved me from writing the fast return variant of SQUFOF, since in the size range I was interested in, it appeared to have a negligible speedup.

2011-07-25, 17:54	#5
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 7×29² Posts	That paper compares the varying speeds of the different methods very well but it would be nice if it took a look at combining the methods for an optimal result. For example at what number of bits would we start doing a tiny bit of ecm or p-1 before siqs. I am guessing the recent improvements in the smallqs code in YAFU are due to this paper.