From Fibonacci and Base-12 Factors to Brent Factors.ppt

Microsoft Research, USA From Fibonacci and Base-12 Factors to Brent Factors Peter L. Montgomery Microsoft Research and CWI Abstract After I wrote factoring codes in 1983, I focused on Fibonacci Fn and Lucas Ln cofactors. Three of us published those tables in 1988, with many gaps. Both tables were complete for n ? 1000 by 2003. I switched to base-12, and cut its composite cofactor list in half. Now that the “easy” base-12 have been done, I am transitioning to Brent’s tables. Ein R?tsel Exclusive OR the letters in BRENT + U + ANTS Remove repeats Insert other duplicates Rearrange As in BRENT + ERECT = CANBERRA What fitting 10-letter word can we get? CWI “Factory” Jobs Run nights and weekends in Amsterdam Typical hours 18:30 to 08:00. My awake hours in western USA. Only machines where owner consents. Owner can kill factory job at any time. ECM and NFS jobs 80-100 machines usable 80-100 hours/week. Mostly AMD Athlons Forty more machines added June, 2006. Also have budget at nearby SARA, on IA-64’s. Fibonacci and Lucas tables 1988 Math. Comp. paper with John Brillhart and Robert Silverman had Fibonacci factorizations Fn (n ? 1000) and Lucas factorizations Ln (n ? 500). 140 Fn and 10 Ln incomplete (out of 1050 entries). By April, 2003, both complete for n ? 1000. /mathematics/fibonacci/ How 150 factorizations completed 53 ECM 51 SNFS 43 MPQS 2 P?1/FFT (Silverman) 1 GNFS (Kleinjung) ----- 150 Many had earlier ECM or P?1/FFT factor. Sizes of non-largest Fibonacci factors missed in 1986 23 p21-p24 44 p25-p29 35 p30-p34 31 p35-p39 17 p40-p44 10 p45-p49 34 higher ----- 194 Fibonacci Contributors 1988-2003 Richard Brent Nicolas Daminelli Marije Elkenbracht-Huizing Jens Franke Sean Irvine Thorsten Kleinjung Joe Leherbauer Mark Manasse (MPQS network) Robert Silverman Thomas Sosnowski I used systems at Unisys, UCLA, Oregon State, CWI, SARA. 2003 -- Time to Switch Tables Cunningham table has