SNFS basics (ggnfs + factLat)

[CRGreathouse]

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.

[10metreh]

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.

2. Create a poly file with the selected polynomial and whatever voodoo is needed for the removed factors.

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.

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!

[henryzz]

if you want to cheat with poly selection try:
http://www.mersenneforum.org/showpos...3&postcount=15

[10metreh]

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.

[henryzz]

Originally Posted by 10metreh

AFAIK it only works for cyclotomics.

yes i forgot about that
this will also work with some numbers:
http://www.mersenneforum.org/showthread.php?t=8739