20090525, 02:42  #1 
Aug 2006
1732_{16} Posts 
SNFS basics (ggnfs + factLat)
I'm trying to learn how to use ggnfs to do a SNFS factorization. In particular, I have numbers of the form a^b + c with c much smaller than a^b and b reasonably large (5 to 200) with some small factors removed.
I've read the ggnfs documentation, though not with any great understanding. I've used the perl script and done the first few steps manually  though the documentation didn't really help much here, I was mostly mimicking the script. I imagine the process to come down to 1. Select a good polynomial, probably something like (a^d)^e + c with e around 45. 2. Create a poly file with the selected polynomial and whatever voodoo is needed for the removed factors. 3. Build factor base, sieve, process, matrix, sqrt. #3 can be done with the perl script, and since I know nothing that should be good enough for the time being. (Any idea of how much time is lost by using the script vs. using expert settings? 20% slowdown? 200% slowdown?) But I'm looking for tips on #1 and directions for #2, basically something going beyond the documentation on pp. 1314. 
20090525, 06:56  #2  
Nov 2008
2322_{10} Posts 
Quote:
25(2^113 * 5^113 + 13) = 2^113 * 5^115 + 325 = 8(2^110 * 5^115) + 325 = 8x^5 + 325 with rational poly x  2^22 * 5^23. Have a read of http://www.mersennewiki.org/index.ph...mial_Selection. Quote:
Code:
n: <remaining_composite> c6: <x^6 coefficient> c5: <x^5 coefficient> c4: <x^4 coefficient> c3: and so on down to: c0: <constant> Y1: 1 Y0: <the_root> skew: a number around 1, shouln't affect sieving much, but you do need it type: snfs Quote:


20090525, 07:09  #3 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·3·7·137 Posts 
if you want to cheat with poly selection try:
http://www.mersenneforum.org/showpos...3&postcount=15 
20090525, 07:47  #4  
Nov 2008
912_{16} Posts 
Quote:


20090525, 08:05  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
167A_{16} Posts 
yes i forgot about that
this will also work with some numbers: http://www.mersenneforum.org/showthread.php?t=8739 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Trying to refresh math from basics... where to start ?  awholenumber  Math  9  20170531 13:15 
basics of relativity  science_man_88  Science & Technology  172  20140411 01:02 
fun with snfs  masser  Sierpinski/Riesel Base 5  36  20080418 02:39 
As Math Scores Lag, a New Push for the Basics  New York Times  ewmayer  Soap Box  14  20061117 09:40 
is GGNFS checking for SNFS number?  Washuu  Factoring  10  20050811 05:09 