Updated polynomial selection - Page 5

tristarman · 2011-02-12, 00:12

Quote:

Originally Posted by debrouxl

A C154 by GNFS... could that be a 512-bit RSA key, per chance ?

One third of duplicate relations is a rather large ratio, but not disproportionate. You'll just probably want to sieve further, until 65M or 70M raw relations.

and is normal 8 GB *.dat file ? first step on factorization this number running 22 days on Intel Core i7 870 - 2.93GHz and VGA ASUS -- GTX460 .. ?

debrouxl · 2011-02-13, 07:12

That sounds normal enough to me for a 512-bit RSA key.

debrouxl · 2011-02-13, 12:46

Final update on the 300-hour polynomial selection for the remaining C164 of near-repdigit http://hpcgi2.nifty.com/m_kamada/f/c.cgi?q=77771_297 on one core of Athlon II X4 640 @ 3 GHz:
* 78088 polys found, 64980 unique;

* 23158 of the 64980 (~35.63%) unique polys have e >= 5.5e-13, of which only 5638 (~8.68% of total) have e >= 6e-13.

* the best poly, which is currently being sieved by the RSALS grid, was found not too long after my previous post about this polynomial selection:

Code:

# norm 6.691697e-16 alpha -8.335395 e 8.743e-13 rroots 3
skew: 49446395.85
c0: -568999597259695268896128098030753819524712
c1:  103858401808105466114937104004368252
c2:  3575537295392949795887528186
c3: -157017216921428122607
c4:  2373605273136
c5:  11880
Y0: -73203616719348149697816500718063
Y1:  422983916724328819

* 20 best polys:

Code:

# norm 5.465754e-16 alpha -7.605223 e 7.550e-13 rroots 5
# norm 5.472974e-16 alpha -9.077833 e 7.577e-13 rroots 5
# norm 5.530163e-16 alpha -7.344872 e 7.749e-13 rroots 3
# norm 5.531328e-16 alpha -5.826451 e 7.757e-13 rroots 5
# norm 5.536231e-16 alpha -9.101452 e 7.641e-13 rroots 5
# norm 5.542633e-16 alpha -7.700554 e 7.646e-13 rroots 5
# norm 5.579459e-16 alpha -6.589118 e 7.831e-13 rroots 3
# norm 5.604403e-16 alpha -7.836440 e 7.789e-13 rroots 5
# norm 5.656121e-16 alpha -6.222926 e 7.921e-13 rroots 5
# norm 5.672590e-16 alpha -7.294301 e 7.853e-13 rroots 3
# norm 5.690402e-16 alpha -6.300193 e 7.798e-13 rroots 5
# norm 5.726098e-16 alpha -6.531180 e 7.914e-13 rroots 5
# norm 5.755527e-16 alpha -7.609863 e 7.904e-13 rroots 5
# norm 5.786062e-16 alpha -8.776453 e 7.922e-13 rroots 3
# norm 5.818739e-16 alpha -6.659529 e 8.049e-13 rroots 5
# norm 5.831477e-16 alpha -7.336733 e 7.980e-13 rroots 5
# norm 6.035177e-16 alpha -6.333451 e 8.178e-13 rroots 5
# norm 6.231503e-16 alpha -8.112288 e 8.412e-13 rroots 3
# norm 6.371171e-16 alpha -6.503278 e 8.544e-13 rroots 5
# norm 6.691697e-16 alpha -8.335395 e 8.743e-13 rroots 3

Maybe the ~5.1e-13 low bound is slightly loose for integers of that size ?
Just ask me if you need the file for further analysis or experiments

Batalov · 2011-03-09, 23:26

I have a feeling that in 107-108-digit size gnfs polynomial selection, the 1st or the 2nd stage bounds are just a bit too tight. Very few polys (maybe less than a dozen altogether) are produced but usually a workable poly is found. Right now, I am looking at a case where the number of polys was merely 2 (yes, two). (I haven't looked in the source, but this seem to be the upper range for degree 4; below 107, degree 4 has different tunings and produces more polys; above 108, degree 5 kicks in and also produces a lot of polys)
Not a high priority thing, but may benefit from a closer look and tuning...

Here's the stubborn input number:
35952843053348817054286503762888603876254836595059302676069851337424939349135291893712895113094245942935921
msieve -np (CPU-version) found two polys:
1:# norm 7.370705e-15 alpha -4.658241 e 3.695e-09 rroots 2
10:# norm 4.910513e-15 alpha -4.520566 e 3.082e-09 rroots 0

jasonp · 2011-03-10, 01:15

That's entirely possible, degree 4 is supposed to last up to 110 digits because the search space for degree 5 is too small at that size. But I didn't spend a lot of time adding the one extra parameter line.

Could you fiddle with the last entry of the prebuilt_params_deg4 array? Usually I make the parameters very low / generous, then set the E-value cutoff to get rid of ~90% of the results, then lower the other two values until the polynomials start disappearing.

(I can do it too, we can compare notes)

Batalov · 2011-03-10, 08:03

After a few runs, I've favored the following tweak:
--- gnfs/poly/poly_skew.c (revision 547)
+++ gnfs/poly/poly_skew.c (working copy)
@@ -39,8 +39,8 @@
{ 90, 1.00E+015, 5.00E+014, 3.80E-008},
{ 95, 1.00E+016, 1.00E+015, 1.50E-008},
{100, 3.10E+017, 4.00E+015, 8.30E-009},
- {105, 1.00E+018, 1.00E+016, 4.00E-009},
- {110, 3.00E+018, 4.00E+016, 1.20E-009},
+ {105, 1.00E+018, 1.50E+016, 3.00E-009},
+ {110, 9.00E+018, 5.00E+016, 1.00E-009},
};
Started getting some decent flares (for the same test number - up to e 4.396e-09 and altogether about a hundred candidates). More testing is needed though. I'll leave the patched binary for the two aliquot sequences that are bouncing around this range...

jasonp · 2011-03-10, 12:07

Updated in SVN, thanks.

Lionel, could you make the .p file from your C164 available if you still have it? I'd like to try a little data mining on it.

debrouxl · 2011-03-11, 06:47

Jason: sure

http://www.sendspace.com/file/r0x583

chris2be8 · 2011-03-27, 16:02

Hello,

I've written a version of factMsieve.pl that uses msieve for polynomial selection (I'm still testing it though). The next step is to run multiple polynomial selection tasks in parallel. I can see how to do it (copy the code to run several sieves in parallel). But I need some advice.

How large a range of leading coefficients should I search as a function of the size of the input number? And should I split the range evenly over however many CPUs the system has?

I plan to make it to scan the same range for a give input size, regardless of how many CPUs it has or how fast they are. So a faster system speeds all steps by roughly the same amount.

Chris K

debrouxl · 2011-03-28, 17:42

Maybe you could limit each instance of msieve to a single coefficient for a5, and move on to the next coefficient when msieve terminates ?
AFAICS, msieve searches for polynomials whose a5 coefficients are multiple of 12. Maybe it can change in future msieve versions, that said.

That you're modifying factMsieve.pl, which I'm still using too, makes me think that I need to get out the changes performed by Benjamin Moody to factMsieve.pl. We used his patched version at the beginning of our attempts at factoring several C154-C155 semiprimes, before the creation of RSALS. I have his written permission to do so. But I shall not deviate this topic further

fivemack · 2011-03-28, 19:50

It's worth noting that msieve is much slower for small a5 than for larger values, so you have either to parcel out at very fine granularity, or to cut the search area up fairly carefully. The curve's a bit rough, but search time is roughly proportional to 1/sqrt(a5), with the constant factor depending on the size of N.

For a C151 that I did a few weeks ago, I did 1844486 CPU-seconds of polynomial searching on 8 CPUs, for 5283710 CPU-seconds of sieving; that's probably a bit much, maybe 20% of the expected sieve time is worth doing. I did do one run on a large number where I was able to run the best-poly-after-24-hours-on-16-threads and best-poly-after-48-hours-on-16-threads and estimate the run time as having got better by about 200 CPU-hours; so I aborted when best-after-72-hours was the same as best-after-48-hours, since I'd be running sieving on 8 threads.

The time taken to run a5=1..1000 is a function of the size of the number but not a very clear one; I fear you have to calibrate that yourself. I've got results for twenty numbers on the same (i5 2.67GHz) hardware, but they're weirdly lumpy

123-130 digits took about 0.08 days
131-140 digits take about 0.17 days for 1..1000
141-150 digits take about 0.32 days
155 digits took 1.03 days
159 and 166 digits took about 0.65 days (yes, faster than the previous one !)

2011-03-09, 23:26	#48
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22405₈ Posts	in SVN 544 I have a feeling that in 107-108-digit size gnfs polynomial selection, the 1st or the 2nd stage bounds are just a bit too tight. Very few polys (maybe less than a dozen altogether) are produced but usually a workable poly is found. Right now, I am looking at a case where the number of polys was merely 2 (yes, two). (I haven't looked in the source, but this seem to be the upper range for degree 4; below 107, degree 4 has different tunings and produces more polys; above 108, degree 5 kicks in and also produces a lot of polys) Not a high priority thing, but may benefit from a closer look and tuning... Here's the stubborn input number: 35952843053348817054286503762888603876254836595059302676069851337424939349135291893712895113094245942935921 msieve -np (CPU-version) found two polys: 1:# norm 7.370705e-15 alpha -4.658241 e 3.695e-09 rroots 2 10:# norm 4.910513e-15 alpha -4.520566 e 3.082e-09 rroots 0

2011-03-10, 01:15	#49
jasonp Tribal Bullet Oct 2004 3541₁₀ Posts	That's entirely possible, degree 4 is supposed to last up to 110 digits because the search space for degree 5 is too small at that size. But I didn't spend a lot of time adding the one extra parameter line. Could you fiddle with the last entry of the prebuilt_params_deg4 array? Usually I make the parameters very low / generous, then set the E-value cutoff to get rid of ~90% of the results, then lower the other two values until the polynomials start disappearing. (I can do it too, we can compare notes) Last fiddled with by jasonp on 2011-03-10 at 01:17

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial selection	Max0526	NFS@Home	9	2017-05-20 08:57
SNFS Polynomial selection help?	mhill12	Factoring	59	2013-09-09 22:40
Best way to scale polynomial selection	pastcow	Msieve	6	2013-05-08 09:01
2^877-1 polynomial selection	fivemack	Factoring	47	2009-06-16 00:24
Polynomial selection	CRGreathouse	Factoring	2	2009-05-25 07:55

2011-02-13, 07:12	#46
debrouxl Sep 2009 977 Posts	That sounds normal enough to me for a 512-bit RSA key.

2011-03-10, 08:03	#50
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	After a few runs, I've favored the following tweak: --- gnfs/poly/poly_skew.c (revision 547) +++ gnfs/poly/poly_skew.c (working copy) @@ -39,8 +39,8 @@ { 90, 1.00E+015, 5.00E+014, 3.80E-008}, { 95, 1.00E+016, 1.00E+015, 1.50E-008}, {100, 3.10E+017, 4.00E+015, 8.30E-009}, - {105, 1.00E+018, 1.00E+016, 4.00E-009}, - {110, 3.00E+018, 4.00E+016, 1.20E-009}, + {105, 1.00E+018, 1.50E+016, 3.00E-009}, + {110, 9.00E+018, 5.00E+016, 1.00E-009}, }; Started getting some decent flares (for the same test number - up to e 4.396e-09 and altogether about a hundred candidates). More testing is needed though. I'll leave the patched binary for the two aliquot sequences that are bouncing around this range...

2011-03-10, 12:07	#51
jasonp Tribal Bullet Oct 2004 3,541 Posts	Updated in SVN, thanks. Lionel, could you make the .p file from your C164 available if you still have it? I'd like to try a little data mining on it.

2011-03-11, 06:47	#52
debrouxl Sep 2009 3D1₁₆ Posts	Jason: sure http://www.sendspace.com/file/r0x583

2011-03-27, 16:02	#53
chris2be8 Sep 2009 81E₁₆ Posts	Hello, I've written a version of factMsieve.pl that uses msieve for polynomial selection (I'm still testing it though). The next step is to run multiple polynomial selection tasks in parallel. I can see how to do it (copy the code to run several sieves in parallel). But I need some advice. How large a range of leading coefficients should I search as a function of the size of the input number? And should I split the range evenly over however many CPUs the system has? I plan to make it to scan the same range for a give input size, regardless of how many CPUs it has or how fast they are. So a faster system speeds all steps by roughly the same amount. Chris K

2011-03-28, 17:42	#54
debrouxl Sep 2009 977 Posts	Maybe you could limit each instance of msieve to a single coefficient for a5, and move on to the next coefficient when msieve terminates ? AFAICS, msieve searches for polynomials whose a5 coefficients are multiple of 12. Maybe it can change in future msieve versions, that said. That you're modifying factMsieve.pl, which I'm still using too, makes me think that I need to get out the changes performed by Benjamin Moody to factMsieve.pl. We used his patched version at the beginning of our attempts at factoring several C154-C155 semiprimes, before the creation of RSALS. I have his written permission to do so. But I shall not deviate this topic further

2011-03-28, 19:50	#55
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1100100010011₂ Posts	It's worth noting that msieve is much slower for small a5 than for larger values, so you have either to parcel out at very fine granularity, or to cut the search area up fairly carefully. The curve's a bit rough, but search time is roughly proportional to 1/sqrt(a5), with the constant factor depending on the size of N. For a C151 that I did a few weeks ago, I did 1844486 CPU-seconds of polynomial searching on 8 CPUs, for 5283710 CPU-seconds of sieving; that's probably a bit much, maybe 20% of the expected sieve time is worth doing. I did do one run on a large number where I was able to run the best-poly-after-24-hours-on-16-threads and best-poly-after-48-hours-on-16-threads and estimate the run time as having got better by about 200 CPU-hours; so I aborted when best-after-72-hours was the same as best-after-48-hours, since I'd be running sieving on 8 threads. The time taken to run a5=1..1000 is a function of the size of the number but not a very clear one; I fear you have to calibrate that yourself. I've got results for twenty numbers on the same (i5 2.67GHz) hardware, but they're weirdly lumpy 123-130 digits took about 0.08 days 131-140 digits take about 0.17 days for 1..1000 141-150 digits take about 0.32 days 155 digits took 1.03 days 159 and 166 digits took about 0.65 days (yes, faster than the previous one !)