mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-05-25, 02:42   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173216 Posts
Default 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.
CRGreathouse is offline   Reply With Quote
Old 2009-05-25, 06:56   #2
10metreh
 
10metreh's Avatar
 
Nov 2008

232210 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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!
10metreh is offline   Reply With Quote
Old 2009-05-25, 07:09   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·3·7·137 Posts
Default

if you want to cheat with poly selection try:
http://www.mersenneforum.org/showpos...3&postcount=15
henryzz is offline   Reply With Quote
Old 2009-05-25, 07:47   #4
10metreh
 
10metreh's Avatar
 
Nov 2008

91216 Posts
Default

Quote:
Originally Posted by henryzz View Post
if you want to cheat with poly selection try:
http://www.mersenneforum.org/showpos...3&postcount=15
AFAIK it only works for cyclotomics.
10metreh is offline   Reply With Quote
Old 2009-05-25, 08:05   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

167A16 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trying to refresh math from basics... where to start ? awholenumber Math 9 2017-05-31 13:15
basics of relativity science_man_88 Science & Technology 172 2014-04-11 01:02
fun with snfs masser Sierpinski/Riesel Base 5 36 2008-04-18 02:39
As Math Scores Lag, a New Push for the Basics -- New York Times ewmayer Soap Box 14 2006-11-17 09:40
is GGNFS checking for SNFS number? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.