Python Driver for GGNFS and MSIEVE - Page 57

fivemack · 2011-09-20, 18:38

axn: you're absolutely right, 54 was a typo on my part.

Running 2M - 3.9M (13e for 2M-3.5M and then by mistake 12e for the rest) took in total 22.3 CPU-hours and gave 3531784 relations, which allowed a 539k-squared matrix to be built in about four minutes and solved in about fifty more minutes.

Removing small factors doesn't have an effect on the SNFS difficulty; the parts of the sieve program which manipulate numbers the size of the number being factored are really very small.

Now, how did I decide which siever and which lp values to use? I start by picking the lp value, and I thought this was quite a small number so I would try lp=25. That means that I'd expect to need about three million relations. I'm aiming for two relations per Q, so in that case I'd want 1.5 million Q, so Q=1.5M to 3M would be where to start. So try alim=rlim=3M and see what happens; using siever-size = half of lp is probably sensible, so try 12e and 13e, and run '-c 1000' to get a little sample

Code:

12e: total yield: 762, q=3001001 (0.02178 sec/rel)
13e: total yield: 1770, q=3001001 (0.02185 sec/rel)

So 13e is about the same speed per relation and gets twice as many relations per Q; also, alim=3 million is a bit low (because I'm only getting 1.77 relations per Q), so try alim=4 million and 2M-4M ought to get at least enough.

This process works for any polynomial you might want to try sieving.

How about if I'd wanted lp=26. I'd want six million relations so try Q=3M to 6M, so sample at 6M.

Code:

6M, 12e: total yield: 1794, q=6001013 (0.01514 sec/rel)
6M, 13e: total yield: 3948, q=6001013 (0.01341 sec/rel)

But remember that I need twice as many relations at lp=26 as at lp=25, and I'm only getting them 50% faster, so lp=25 is definitely better. lp=27 would be very wrong for this size of number.

The problem is simply that the script is making too large an estimate for the number of relations it needs to collect before trying to filter; it collected six million when it only needed three and a half million.

Walter Nissen · 2011-09-21, 01:17

Quote:

Originally Posted by fivemack

redoing the whole thing ... by hand

Your comments are quite helpful .
I don't know how to do this by hand .
How many commands replace ..\factMsieve.py ?
Can you help me learn this ?

Quote:

Originally Posted by fivemack

The problem is simply that the script is making too large an estimate for the number of relations it needs to collect before trying to filter; it collected six million when it only needed three and a half million.

I've read about over-sieving causing disasters .
6M vs 3.5M seems like lot to me , but apparently it didn't cause a
fatal problem .
If I read the output correctly , using more relations , it built a matrix
almost 379K square .
I'm guessing that in the later stages , this would use less RAM than a
larger matrix .
How large an N will fit into this P4 with 1.5 GiB of RAM ?
Can I trade off more sieving for a smaller matrix and extend the
capability of the P4 ?

P. S. I'm ignoring your comments about the time consumed by the
later stages
( my attention is transfixed by the prospect of months or
years of sieving ) ,
but I don't have to .
If you want more info about the snfs 153 run on the P4 , I'm at
your service .
I'll summarize more , or attach the various smaller files , or
email them or whatever .

fivemack · 2011-09-21, 08:25

Looking through all my log files, a 149-digit GNFS-number completed the linear-algebra steps using at most 1247MB of memory so in principle should fit on your machine.

Similarly the 198-difficulty SNFS 35^128+1 at one point allocated 1049.7MB but no more.

If you become addicted to factorisation, get a Sandy Bridge machine with 16GB of memory (the memory costs less than $120 at the moment in the US) and you can happily cope with really quite large problems ...

284-difficulty SNFS
./2-941/msieve.log:Mon Nov 16 23:33:19 2009 memory use: 10367.2 MB

170-digit GNFS
./3270.632/la/msieve.log:Tue May 31 18:36:49 2011 memory use: 6046.6 MB

Walter Nissen · 2011-09-21, 13:41

Quote:

Originally Posted by fivemack

Removing small factors doesn't have an effect on the SNFS difficulty; the parts of the sieve program which manipulate numbers the size of the number being factored are really very small.

Does this imply the width of the residual cofactor after ECM only matters if
factoring the residual with gnfs can be done in less time than using snfs ?
Considering that as N grows larger , the residual grows more and more
intractable , would this not mean that if snfs is available , then the
usefulness of ECM is pretty much limited to the cases where it achieves a
complete factorization ?

Thanks for your last post ; helpful .

fivemack · 2011-09-21, 14:07

You're right: if you pull a 70-digit factor out of a 280-digit SNFS-number leaving a 210-digit GNFS-number, you're much better off factoring the original number by SNFS than trying to factor the cofactor with GNFS.

I had to look quite hard to find a GNFS job which was of around 200 digits and was easier by GNFS than SNFS.

fivemack · 2011-09-21, 14:13

Quote:

Originally Posted by Walter Nissen

Your comments are quite helpful .
I don't know how to do this by hand .
How many commands replace ..\factMsieve.py ?
Can you help me learn this ?

Code:

gnfs-lasieve4I13e -a -f 2000000 -c 1000000  (in one window)
gnfs-lasieve4I13e -a -f 3000000 -c 1000000  (in another window)

copy gnfs as msieve.fb, change 'cX:' to 'AX' and 'YX:' to 'RX', change 'n:' to 'N', change 'skew:' to 'SKEW' and remove the rest of the lines

put the number to factor as worktodo.ini

wait until the lasieve jobs have finished

copy gnfs.lasieve-0.2000000-3000000+gnfs.lasieve-0.3000000-4000000 > msieve.dat
msieve -v -nc -t 2

fivemack · 2011-09-21, 14:34

It happens that I've just finished a C127 on one core of the same machine that I used for the S153 timing test above:

Code:

Polynomial selection  10h50m
Sieving (26-bit large primes, 13e siever)  79h47m
msieve  2h27m (memory use 326MB)

So (as we knew) 153-digit SNFS is a good deal easier than 127-digit GNFS.

Andi47 · 2011-09-21, 15:13

Quote:

Originally Posted by fivemack

You're right: if you pull a 70-digit factor out of a 280-digit SNFS-number leaving a 210-digit GNFS-number, you're much better off factoring the original number by SNFS than trying to factor the cofactor with GNFS.

I had to look quite hard to find a GNFS job which was of around 200 digits and was easier by GNFS than SNFS.

Yes, but ecm-preparation is useful anyway: If you pull an ECM-factor (be it large or not) out of a huge SNFS number, leaving a prime (say e.g. you pull a p70 out of a 280-digit SNFS-number, leaving a 210-digit prime), you have saved a great deal of time, which you otherwise would have used for SNFS.

fivemack · 2011-09-21, 15:58

Quote:

Originally Posted by Andi47

Yes, but ecm-preparation is useful anyway: If you pull an ECM-factor (be it large or not) out of a huge SNFS number, leaving a prime (say e.g. you pull a p70 out of a 280-digit SNFS-number, leaving a 210-digit prime), you have saved a great deal of time, which you otherwise would have used for SNFS.

That's what Walter meant by 'the usefulness of ECM is pretty much limited to the cases where it achieves a complete factorization'; I had a caveat of that form in the original version of my message, but removed it because I saw Walter had considered that case.

Andi47 · 2011-09-21, 16:41

Quote:

Originally Posted by fivemack

That's what Walter meant by 'the usefulness of ECM is pretty much limited to the cases where it achieves a complete factorization'; I had a caveat of that form in the original version of my message, but removed it because I saw Walter had considered that case.

ooops, sorry, I missed that part.

Walter Nissen · 2011-09-21, 19:16

Quote:

Originally Posted by fivemack

Quote:

Originally Posted by Andi47

If you pull an ECM-factor out of a huge SNFS number leaving a prime, you have saved a great deal of time

... meant by 'the usefulness of ECM is pretty much limited to the cases where it achieves a complete factorization'

There are some of these in the aforementioned
http://upforthecount.com/math/nnp.html
E.g. , letting np ( n ) = n^n + (n+1)^(n+1) ,
np ( 415 ) = 29 * p1089
That one was found by trial division .
BTW , I use there the notation "p1089" to denote a proven prime , and
p?11585 to denote a number which has failed a compositeness test ,
usually 2-Fermat .
Also , David Broadhurst has posted some to
http://www.primenumbers.net/prptop/s...2By^y%29%2F%3F
and
http://tech.dir.groups.yahoo.com/gro.../message/20907
and vicinity , including np ( 23619 ) = 7187 * p?103294 .

2011-09-20, 18:38	#617
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6422₁₀ Posts	finished Linux timing axn: you're absolutely right, 54 was a typo on my part. Running 2M - 3.9M (13e for 2M-3.5M and then by mistake 12e for the rest) took in total 22.3 CPU-hours and gave 3531784 relations, which allowed a 539k-squared matrix to be built in about four minutes and solved in about fifty more minutes. Removing small factors doesn't have an effect on the SNFS difficulty; the parts of the sieve program which manipulate numbers the size of the number being factored are really very small. Now, how did I decide which siever and which lp values to use? I start by picking the lp value, and I thought this was quite a small number so I would try lp=25. That means that I'd expect to need about three million relations. I'm aiming for two relations per Q, so in that case I'd want 1.5 million Q, so Q=1.5M to 3M would be where to start. So try alim=rlim=3M and see what happens; using siever-size = half of lp is probably sensible, so try 12e and 13e, and run '-c 1000' to get a little sample Code: 12e: total yield: 762, q=3001001 (0.02178 sec/rel) 13e: total yield: 1770, q=3001001 (0.02185 sec/rel) So 13e is about the same speed per relation and gets twice as many relations per Q; also, alim=3 million is a bit low (because I'm only getting 1.77 relations per Q), so try alim=4 million and 2M-4M ought to get at least enough. This process works for any polynomial you might want to try sieving. How about if I'd wanted lp=26. I'd want six million relations so try Q=3M to 6M, so sample at 6M. Code: 6M, 12e: total yield: 1794, q=6001013 (0.01514 sec/rel) 6M, 13e: total yield: 3948, q=6001013 (0.01341 sec/rel) But remember that I need twice as many relations at lp=26 as at lp=25, and I'm only getting them 50% faster, so lp=25 is definitely better. lp=27 would be very wrong for this size of number. The problem is simply that the script is making too large an estimate for the number of relations it needs to collect before trying to filter; it collected six million when it only needed three and a half million. Last fiddled with by fivemack on 2011-09-20 at 18:38

2011-09-21, 14:07	#621
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×13²×19 Posts	You're right: if you pull a 70-digit factor out of a 280-digit SNFS-number leaving a 210-digit GNFS-number, you're much better off factoring the original number by SNFS than trying to factor the cofactor with GNFS. I had to look quite hard to find a GNFS job which was of around 200 digits and was easier by GNFS than SNFS. Last fiddled with by fivemack on 2011-09-21 at 14:07

2011-09-21, 14:34	#623
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×13²×19 Posts	It happens that I've just finished a C127 on one core of the same machine that I used for the S153 timing test above: Code: Polynomial selection 10h50m Sieving (26-bit large primes, 13e siever) 79h47m msieve 2h27m (memory use 326MB) So (as we knew) 153-digit SNFS is a good deal easier than 127-digit GNFS.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve & ggnfs on MacOS	xilman	Msieve	8	2017-05-20 00:12
Factorizing with MSIEVE, GGNFS & Factmsieve.py	Romuald	Msieve	24	2015-11-09 20:16
Infinite loop for ggnfs or msieve	Greebley	Aliquot Sequences	4	2013-02-06 19:28
Error running GGNFS+msieve+factmsieve.py	D. B. Staple	Factoring	6	2011-06-12 22:23
A new driver? (or type of driver?)	10metreh	Aliquot Sequences	3	2010-02-15 15:57

2011-09-21, 08:25	#619
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1100100010110₂ Posts	Looking through all my log files, a 149-digit GNFS-number completed the linear-algebra steps using at most 1247MB of memory so in principle should fit on your machine. Similarly the 198-difficulty SNFS 35^128+1 at one point allocated 1049.7MB but no more. If you become addicted to factorisation, get a Sandy Bridge machine with 16GB of memory (the memory costs less than $120 at the moment in the US) and you can happily cope with really quite large problems ... 284-difficulty SNFS ./2-941/msieve.log:Mon Nov 16 23:33:19 2009 memory use: 10367.2 MB 170-digit GNFS ./3270.632/la/msieve.log:Tue May 31 18:36:49 2011 memory use: 6046.6 MB