Seeking GNFS factoring advice... - Page 2

chris2be8 · 2012-03-05, 17:54

There are several Brent tables candidates. Eg the c160 from 93^128+1 below would be much easier by GNFS than SNFS.

Code:

2737329477235549359319751778813739148018531585442290374029198239639683745876975366145341781069052888071580309121439324144612850710770429956756075243241117400577

Chris K

VBCurtis · 2012-05-01, 07:56

I am considering a GNFS attempt on F(1509), a C160. I have used the python script to factor a few 130-digit numbers for OPN, and will factor something around C140 to make sure I understand how to split the sieving ranges among multiple machines before trying this C160.

1. Are the default parameters in msieve / factmsieve scripts good enough for a C160? If not, what variants of params should I alter or consider altering?

2. I have one (laptop) CUDA available, as well as 8 modern CPU cores. I have read here that for large problems like this, msieve's poly search runs on a subspace of the leading coefficients about 1/400th of the total space. With under 10 cores, does this mean I can just run 9 copies of factmsieve among the machines, wait 2 days, and test-sieve among the 2-3 best polys? Alternately, should I run msieve -np on some of the cores starting at a higher leading coefficient to imitate a single CPU running selection for a week?
Using fivemack's estimate of 6 cpu-months to sieve this, I figure ~15 cpu-days is enough for poly search. True?

3a. At what size number do the default params lack enough completed factorizations to establish agreed-standard settings?

3b. Is there a size beyond which experiments should be run on a number-by-number basis to tweak the parameters? At 140 digits, we wouldn't save enough CPU time to bother, but this thread contains replies that suggest some experimentation is beneficial at C180 so I wonder where such testing becomes meaningful.

-Curtis

Batalov · 2012-05-01, 08:15

Quote:

Originally Posted by VBCurtis

I am considering a GNFS attempt on F(1509), a C160.

This number is much easier with SNFS (difficulty 210.2): this is because F(1509) is divisible by F(503). Don't do it by GNFS.

Search the forum with the magic word "lindep". (learned this trick from Tom W.)
It is much more interesting to do this trick yourself. If you will get into trouble, let us know.
_____

If you'd rather want a GNFS, there's L(1121) c158, a very close ("wanted") hole. And a faraway number ~~L(5385B) c159~~, which is reserved. Then some c162-c163s.

VBCurtis · 2012-05-01, 23:24

Thanks! I read the links, will study the math trick to create the SNFS polys mentioned there. If I wish to stick with GNFS, I think that thread admits F1097 as GNFS-worthy, though it's C162.

I have not yet gotten an SNFS poly file to 'work'- while I understand the math for the easy SNFS tasks on OPN, I have some syntax problem. Once I find my mistake and get some experience with easy SNFS tasks, I'll try to create the SFNS poly for F1509 and see if it's something I want to tackle.
Thanks again for the search tip.
-Curtis

Batalov · 2012-05-02, 00:29

F1097 is most likely SNFS. (Practically, one would just go with SNFS - there's no time overhead for the poly selection.)

Only for some testing purposes it could be significantly polyselected to almost reach (or maybe surpass) the SNFS poly's E value which is 1.194e-12. It could be an interesting experiment. My guess would be that it is an even bet (except for GNFS polyselect overhead; with it, SNFS probably wins right away).

chris2be8 · 2012-05-20, 18:48

While trying to factor a 76 digit number I found that if you try to run polynomial selection msieve actually just factors the number with QS, which confused factMsieve.pl.

I've patched my copy of factMsieve.pl to use QS for small numbers but what is the right border?

Chris

Dubslow · 2012-05-20, 19:00

YAFU uses tune data for each computer, but lacking that, defaults to a 95 digit cutoff. Presumably Msieve would have similar characteristics, perhaps a slightly lower cutoff.

jasonp · 2012-05-20, 22:19

Msieve refuses to use NFS for inputs below 85 digits; the cutoff is hardcoded into the library.

2012-03-05, 17:54	#12
chris2be8 Sep 2009 2×1,039 Posts	There are several Brent tables candidates. Eg the c160 from 93^128+1 below would be much easier by GNFS than SNFS. Code: 2737329477235549359319751778813739148018531585442290374029198239639683745876975366145341781069052888071580309121439324144612850710770429956756075243241117400577 Chris K Last fiddled with by wblipp on 2012-03-06 at 12:56 Reason: Add code tags

2012-05-01, 07:56	#13
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	I am considering a GNFS attempt on F(1509), a C160. I have used the python script to factor a few 130-digit numbers for OPN, and will factor something around C140 to make sure I understand how to split the sieving ranges among multiple machines before trying this C160. 1. Are the default parameters in msieve / factmsieve scripts good enough for a C160? If not, what variants of params should I alter or consider altering? 2. I have one (laptop) CUDA available, as well as 8 modern CPU cores. I have read here that for large problems like this, msieve's poly search runs on a subspace of the leading coefficients about 1/400th of the total space. With under 10 cores, does this mean I can just run 9 copies of factmsieve among the machines, wait 2 days, and test-sieve among the 2-3 best polys? Alternately, should I run msieve -np on some of the cores starting at a higher leading coefficient to imitate a single CPU running selection for a week? Using fivemack's estimate of 6 cpu-months to sieve this, I figure ~15 cpu-days is enough for poly search. True? 3a. At what size number do the default params lack enough completed factorizations to establish agreed-standard settings? 3b. Is there a size beyond which experiments should be run on a number-by-number basis to tweak the parameters? At 140 digits, we wouldn't save enough CPU time to bother, but this thread contains replies that suggest some experimentation is beneficial at C180 so I wonder where such testing becomes meaningful. -Curtis Last fiddled with by VBCurtis on 2012-05-01 at 07:56

2012-05-01, 23:24	#15
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Thanks! I read the links, will study the math trick to create the SNFS polys mentioned there. If I wish to stick with GNFS, I think that thread admits F1097 as GNFS-worthy, though it's C162. I have not yet gotten an SNFS poly file to 'work'- while I understand the math for the easy SNFS tasks on OPN, I have some syntax problem. Once I find my mistake and get some experience with easy SNFS tasks, I'll try to create the SFNS poly for F1509 and see if it's something I want to tackle. Thanks again for the search tip. -Curtis Last fiddled with by VBCurtis on 2012-05-01 at 23:24

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factoring a 1024-bit RSA with GNFS?	BotXXX	Factoring	25	2015-09-02 08:27
Advice for large GNFS jobs?	WraithX	Factoring	59	2013-07-30 01:13
need some advice: gnfs C164 from 162126:i4274	Syd	Aliquot Sequences	7	2011-03-14 18:35
buying computer for factoring, looking for advice	jasong	Factoring	3	2006-10-24 04:43
any good GNFS factoring programs?	ixfd64	Factoring	1	2004-04-27 09:41

2012-05-02, 00:29	#16
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	F1097 is most likely SNFS. (Practically, one would just go with SNFS - there's no time overhead for the poly selection.) Only for some testing purposes it could be significantly polyselected to almost reach (or maybe surpass) the SNFS poly's E value which is 1.194e-12. It could be an interesting experiment. My guess would be that it is an even bet (except for GNFS polyselect overhead; with it, SNFS probably wins right away).

2012-05-20, 18:48	#17
chris2be8 Sep 2009 81E₁₆ Posts	While trying to factor a 76 digit number I found that if you try to run polynomial selection msieve actually just factors the number with QS, which confused factMsieve.pl. I've patched my copy of factMsieve.pl to use QS for small numbers but what is the right border? Chris

2012-05-20, 19:00	#18
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 1110000110101₂ Posts	YAFU uses tune data for each computer, but lacking that, defaults to a 95 digit cutoff. Presumably Msieve would have similar characteristics, perhaps a slightly lower cutoff.

2012-05-20, 22:19	#19
jasonp Tribal Bullet Oct 2004 3,541 Posts	Msieve refuses to use NFS for inputs below 85 digits; the cutoff is hardcoded into the library.