mersenneforum.org SNFS basics (ggnfs + factLat)
 Register FAQ Search Today's Posts Mark Forums Read

 2009-05-25, 02:42 #1 CRGreathouse     Aug 2006 173216 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 4-5. 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. 13-14.
2009-05-25, 06:56   #2
10metreh

Nov 2008

232210 Posts

Quote:
 Originally Posted by CRGreathouse 1. Select a good polynomial, probably something like (a^d)^e + c with e around 4-5.
There's the obvious (a^d)^e + c as you mentioned. However, you don't want the coefficients to become too large. So for 10^100+13 (already factored), the poly would be x^4 + 13 with rational poly x - 10^25 (this is normally x - the root). Degree 5 becomes superior to degree 4 around difficulty 115. If you end up with coefficients getting too large, you have extra methods if the base is composite, e.g. for 10^113+13, you can make this into 1000x^5 + 13, but it is better to do this: 10^113 + 13 = 2^113 * 5^113 + 13, and then multiply and divide by powers of 2 and 5:
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:
 2. Create a poly file with the selected polynomial and whatever voodoo is needed for the removed factors.
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
The cX's can be dropped if they are zero. And it is important to make sure that "n" is the remaining composite, not the original composite! The script will then choose some parameters and do its job.

Quote:
 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?)
For larger SNFS jobs (above difficulty ~170?) the script's parameters start becoming sub-optimal. BTW, download the latest GGNFS svn from here! This includes factMsieve.pl, which is basically factLat.pl hacked to use msieve for postprocessing. You will need to replace the msieve that comes with the svn with the latest version (1.41), edit the paths in factMsieve.pl, and run!

 2009-05-25, 07:09 #3 henryzz 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
2009-05-25, 07:47   #4
10metreh

Nov 2008

91216 Posts

Quote:
 Originally Posted by henryzz if you want to cheat with poly selection try: http://www.mersenneforum.org/showpos...3&postcount=15
AFAIK it only works for cyclotomics.

2009-05-25, 08:05   #5
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

167A16 Posts

Quote:
 Originally Posted by 10metreh AFAIK it only works for cyclotomics.
this will also work with some numbers:

 Similar Threads Thread Thread Starter Forum Replies Last Post awholenumber Math 9 2017-05-31 13:15 science_man_88 Science & Technology 172 2014-04-11 01:02 masser Sierpinski/Riesel Base 5 36 2008-04-18 02:39 ewmayer Soap Box 14 2006-11-17 09:40 Washuu Factoring 10 2005-08-11 05:09

All times are UTC. The time now is 02:25.

Fri Dec 4 02:25:03 UTC 2020 up 22:36, 1 user, load averages: 1.14, 1.46, 1.66