Python Driver for GGNFS and MSIEVE - Page 58

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

From
79^79+80^80 = (79^4) * (79^15)^5 + (80^16)^5
it's an easy leap to
84^84 + 85^85 = 84^4 * (84^16)^5 + (85^17)^5
but I worry that maybe the fact that 16 is a power of 2 may be
significant and maybe 17 won't do as well .
That may be a silly worry , but I don't know much about the
criteria , and I'm not too eager to devote 6 months to a poly
that can never work for some theoretical reason .

Code:

                residual digits
                left by ECM so far

87^87 + 88^88   145 
83^83 + 84^84   147
96^96 + 97^97   149
84^84 + 85^85   163 
91^91 + 92^92   165
95^95 + 96^96   169
98^98 + 99^99   192

Except these , all up to and including 102^102 + 103^103
are completely factored .
http://upforthecount.com/math/nnp.html is to be
updated ( but is still in a raw form , unpublished ) .

I don't know when it is appropriate to switch from ECM ,
that decision also depends on how much "little stuff" has been
extracted by ECM , but I have little hope anything smaller than
35 or 40 digits remains unexposed .

Do I need to know anything beyond what is in :
http://www.mersennewiki.org/index.ph...mial_Selection
before I start trials of factMsieve.py ?
Do I use the difficulty score it shows as the best test of a good
poly ?

fivemack , are you saying I don't need to know much , if anything ,
more than you've said , about parameter selection , just make a
guesstimate and then trial-sieve to find the optimal parameters ?

fivemack · 2011-09-21, 21:24

If you get the polynomial wrong, you'll get a message saying something like 'does not divide'; you're not going to spend weeks sieving and then discover at the end that the polynomial doesn't work.

I have once spent weeks sieving and then discovered that the input number was prime. I think the tools check this now

And there's nothing magic about sixteen, so the polynomial implied by your argument will work fine. Though

84*(84^84+85^85) = 84^85 + 84 * 85^85
=(84^17)^5 + 84*(85^17)^5
might give you a better polynomial - generally you want the numbers on the algebraic side, the c0 through c5, to be as small as possible.

But you can check which polynomial's better; sieve a short (but not too short .. -c 10000 is about right) interval for both and see which gets relations faster.

The idea for getting polynomials for your number is to multiply up by something to get the exponents to be multiples of five: for 83^83+84^84, you need to multiply by 83^2*84 to get

84 * 83^85 + 83^2 * 84^85

and you're factoring (83^2*84)*(83^83+84^84) for an SNFS difficulty of 167.4

fivemack · 2011-09-21, 21:26

I would generally run ECM for about 20% of the time that I'd expect the GNFS step to take - so maybe 24 hours for 83^83+84^84.

xilman · 2011-09-23, 09:14

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.

I'd add another caveat: the original number must be amenable to SNFS. If it is not, reducing a C200 to a C150 is a good use of ECM time!

Paul

axn · 2011-09-23, 13:41

Quote:

Originally Posted by Walter Nissen

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 .

He's got that one also covered

Walter Nissen · 2011-09-26, 14:25

Quote:

Originally Posted by Andi47

In my dataset, most of large GNFSes (i.e. above c135) and large SNFSes
seem to be oversieved on purpose to get smaller matrices.

Presumably , smaller matrices use less RAM and thus
will fit in a smaller machine , but is there also a saving
in CPU in the later stages ?
Is such a saving large ?
Are there also other implications ?

Andi47 · 2011-09-26, 17:30

Quote:

Originally Posted by Walter Nissen

Presumably , smaller matrices use less RAM and thus
will fit in a smaller machine , but is there also a saving
in CPU in the later stages ?
Is such a saving large ?
Are there also other implications ?

I have not done / witnessed enough large factorizations to produce proper statistics. As far as I have heared, there might be some CPU saving between an initial "ugly hughe matrix" and a somewhat smaller matrix after slight oversieving.

But I know neither how big this saving is (if any), nor the "optimal amount" of oversieving. Probably the "giants" can give better information on that.

henryzz · 2011-09-26, 17:46

Extra sieving to get a smaller matrix is not just done to reduce the overall cpu-time. Until recently the matrix could only be solved on one high-memory computer. Oversieving was done to stop the many sieving machines overtaking the relatively few matrix solving machines. The matrix solving machines are often much more expensive than others as much larger memory is bought. This difference is dying out though as the memory required to solve most matrices is cheap now. People also like small matrixes as it means they don't have a machine unavailable for 6 months.

jasonp · 2011-09-26, 19:03

The difference between a matrix built with 'just enough' relations and a matrix built with a huge amount of oversieving is about a factor of 1/3 the initial matrix size. So the matrix winds up smaller and probably a lot more dense. Right now the runtime saved by the smaller size dwarfs the runtime sacrificed because of the increased density.

It's been the forum's experience that deliberately oversieving only saves time when the input is huge and you do not have a large number of sieving machines; otherwise the calendar time taken up by the extra sieving is usually only a few hours to a day less than the time saved by the smaller matrix solve. Of course all the rules are different for the largest problems, since these actually may not fit in the solver machine unless there's a huge amount of oversieving, and even if it fits fine then a 15% faster matrix solve could save a week of calendar time.

axn · 2011-09-26, 19:38

Quote:

Originally Posted by jasonp

deliberately oversieving only saves time when the input is huge and you do not have a large number of sieving machines

Did you mean to have that negation there?

jasonp · 2011-09-26, 21:33

Oops, yes; you need a lot of machines to get the extra sieving over with quickly enough so that the faster linear algebra is a net win.

2011-09-21, 19:19	#628
Walter Nissen Nov 2006 Terra 2×3×13 Posts	polynomial selection and parameter determination From 79^79+80^80 = (79^4) * (79^15)^5 + (80^16)^5 it's an easy leap to 84^84 + 85^85 = 84^4 * (84^16)^5 + (85^17)^5 but I worry that maybe the fact that 16 is a power of 2 may be significant and maybe 17 won't do as well . That may be a silly worry , but I don't know much about the criteria , and I'm not too eager to devote 6 months to a poly that can never work for some theoretical reason . Code: residual digits left by ECM so far 87^87 + 88^88 145 83^83 + 84^84 147 96^96 + 97^97 149 84^84 + 85^85 163 91^91 + 92^92 165 95^95 + 96^96 169 98^98 + 99^99 192 Except these , all up to and including 102^102 + 103^103 are completely factored . http://upforthecount.com/math/nnp.html is to be updated ( but is still in a raw form , unpublished ) . I don't know when it is appropriate to switch from ECM , that decision also depends on how much "little stuff" has been extracted by ECM , but I have little hope anything smaller than 35 or 40 digits remains unexposed . Do I need to know anything beyond what is in : http://www.mersennewiki.org/index.ph...mial_Selection before I start trials of factMsieve.py ? Do I use the difficulty score it shows as the best test of a good poly ? fivemack , are you saying I don't need to know much , if anything , more than you've said , about parameter selection , just make a guesstimate and then trial-sieve to find the optimal parameters ?

2011-09-21, 21:26	#630
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1100100010110₂ Posts	When do you switch from ECM I would generally run ECM for about 20% of the time that I'd expect the GNFS step to take - so maybe 24 hours for 83^83+84^84.

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, 21:24	#629
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×13²×19 Posts	If you get the polynomial wrong, you'll get a message saying something like 'does not divide'; you're not going to spend weeks sieving and then discover at the end that the polynomial doesn't work. I have once spent weeks sieving and then discovered that the input number was prime. I think the tools check this now And there's nothing magic about sixteen, so the polynomial implied by your argument will work fine. Though 84(84^84+85^85) = 84^85 + 84 85^85 =(84^17)^5 + 84(85^17)^5 might give you a better polynomial - generally you want the numbers on the algebraic side, the c0 through c5, to be as small as possible. But you can check which polynomial's better; sieve a short (but not too short .. -c 10000 is about right) interval for both and see which gets relations faster. The idea for getting polynomials for your number is to multiply up by something to get the exponents to be multiples of five: for 83^83+84^84, you need to multiply by 83^284 to get 84 * 83^85 + 83^2 * 84^85 and you're factoring (83^284)(83^83+84^84) for an SNFS difficulty of 167.4

2011-09-26, 17:46	#635
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 5,881 Posts	Extra sieving to get a smaller matrix is not just done to reduce the overall cpu-time. Until recently the matrix could only be solved on one high-memory computer. Oversieving was done to stop the many sieving machines overtaking the relatively few matrix solving machines. The matrix solving machines are often much more expensive than others as much larger memory is bought. This difference is dying out though as the memory required to solve most matrices is cheap now. People also like small matrixes as it means they don't have a machine unavailable for 6 months.

2011-09-26, 19:03	#636
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	The difference between a matrix built with 'just enough' relations and a matrix built with a huge amount of oversieving is about a factor of 1/3 the initial matrix size. So the matrix winds up smaller and probably a lot more dense. Right now the runtime saved by the smaller size dwarfs the runtime sacrificed because of the increased density. It's been the forum's experience that deliberately oversieving only saves time when the input is huge and you do not have a large number of sieving machines; otherwise the calendar time taken up by the extra sieving is usually only a few hours to a day less than the time saved by the smaller matrix solve. Of course all the rules are different for the largest problems, since these actually may not fit in the solver machine unless there's a huge amount of oversieving, and even if it fits fine then a 15% faster matrix solve could save a week of calendar time.

2011-09-26, 21:33	#638
jasonp Tribal Bullet Oct 2004 3×1,181 Posts	Oops, yes; you need a lot of machines to get the extra sieving over with quickly enough so that the faster linear algebra is a net win.