Which poly to use? - Page 3

Karl M Johnson · 2010-06-02, 07:12

Now I noticed it runs longer than the limit allows. Marvellous!

Batalov · 2010-06-02, 07:38

Quote:

Originally Posted by Karl M Johnson

Factoring RSA-100 with FactMsieve.py script took 3816 seconds(that's excluding Polynomial selection).

In 2 hours for a similar number, you may find an excellent poly and then run the factoring for 3600 seconds. Or you may find a boring, average poly in 0.5 hr and then run the factoring for 4200 seconds. Which of these two scenarios would you rather choose, -- if you are going to run a hundred of similar factorizations (e.g. in a context of a small aliquot sequence)?

The deadlines are usually chosen with the above in mind.

Karl M Johnson · 2010-06-02, 08:39

Now that I've found out how to force Msieve to select polynomials longer, I will rather let msieve look for it longer, than sieve longer.Poly selection is the most accelerated step right now.
After running Msieve for 2.5 hours selecting Polys in [1,20480] selection, it finally stopped with the following:

Code:

name: rsa110
n: 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667
skew: 60693.32
Y0 -1753366490265555850692
Y1 221316341387
c0 26296772189237990432320457
c1 39506829751983394903574
c2 784404813837512059
c3 -25719356093546
c4 -164980728
c5 2160
#size 2.360848e-010, alpha -6.151039, combined = 5.194095e-011

jasonp · 2010-06-02, 10:33

As Serge mentioned, the objective is to finish in the shortest total time. Beyond a certain point you are not going to find a polynomial that sieves sufficiently faster to justify the extra search time. My personal rule of thumb is that poly searching should not take up more than 5% of the total time, so if you have multiple machines or small jobs then you should be searching for less time.

Also, there is a per-leading-coefficient timeout that always applies to the search, so the amount of searching you do for any particular leading coefficient is capped. Spending longer on the search means you try larger and larger coefficients, which find polynmials more often but the average quality deteriorates.

Karl M Johnson · 2010-06-02, 10:57

As far as I understand it, the better the factorized number by GNFS, the better the polynomial should be.
If it's RSA-100, well, the difference could be at most half of hour.
However, if it's RSA-190, I'd spend a generous amout of time(but, of course, not more than 10% estimated) on poly selection.
Since the right, optimized polynomial would probably reduce sieving by weeks, maybe months.

xilman · 2010-06-02, 14:19

Quote:

Originally Posted by jasonp

As Serge mentioned, the objective is to finish in the shortest total time. Beyond a certain point you are not going to find a polynomial that sieves sufficiently faster to justify the extra search time. My personal rule of thumb is that poly searching should not take up more than 5% of the total time, so if you have multiple machines or small jobs then you should be searching for less time.

Also, there is a per-leading-coefficient timeout that always applies to the search, so the amount of searching you do for any particular leading coefficient is capped. Spending longer on the search means you try larger and larger coefficients, which find polynmials more often but the average quality deteriorates.

I don't know how well the following the following information applies to piddlling small numbers (C200, say), but the RSA-768 factorization used around 1700 cpu-years in total, of which only 40 were devoted to polynomial searching. Approximately 1500 cpu-years were spent sieving and about 160 on the linear algebra.

Paul

tgrdy · 2010-06-09, 02:41

I have run the ggnfs's pol51,to select a poly for C157 (521 bits) number.
On a Xeon E52xx 2.26GHZ CPU. After about 8 days, got tens of poly.
from [1 , 1e6] , but the best Murphy_E I got is 1.16e-012.

Code:

name: r521b
n: 6324666027462161015374006516548809863047964221242277240375351792972562172787622497643929756032157742653281817116005744464806258176388463009478862122997883673
skew: 2512911.25
# norm 6.72e+22
c5: 34560
c4: -2753123542773
c3: 251250956198164109144
c2: -6573799638436659003576612
c1: -6939158294213211437888489648304
c0: 1043837895933284046379368850656155200
# alpha -5.6
Y1: 8366733557212756391
Y0: -2834739740500764201115157936497
# Murphy_E 1.16e-12
# M 6077405585972345190556134149536147968610833235011994916549251816755061928330606441736881566874101467919376550894267605033517780265853017943605279215773277905

Then, I stopped the pol51, run it again, search start
[1e7, 1e8] , after 1 day, The best Murphy_E is 1.27e-012 found.
I confused
(1) should I run poly select more days?
searching start in bigger initial value [1e9, 1e10] or even [1e11, 1e12]?
(2) If two polys has the same Murphy_E, chose the the one with bigger skewness or smaller skewness ?

Thanks,

Code:

BEGIN POLY #skewness 270409.05 norm 7.82e+021 alpha -5.00 Murphy_E 1.26e-012
X5 10095300
X4 490122068621841
X3 12650182371187893413
X2 -25274951897553389105616769
X1 -187789772472816573120308681060
X0 295319180816958386453362218541258000
Y1 275566077122592487
Y0 -910714807038441699895224119493
M 802680827088953490610867482101805500144346324846102232192678208362621447925028150796428874035416424908958175273260621733507161329032896688515102460754239971
END POLY

BEGIN POLY #skewness 384992.31 norm 1.21e+022 alpha -5.40 Murphy_E 1.27e-012
X5 10389660
X4 462323084357023
X3 1269766856649885916
X2 -49673879752070101959131274
X1 -146307325149773959555747658610
X0 1027628669381046423799102167286486800
Y1 4015565701661113127
Y0 -905461758932060039359654249241
M 2595593278705307416439607540574251926079835555367475275724738182420327440991316202990882833805544641598767671844683625904356132529164160657892148152584671915
END POLY

BEGIN POLY #skewness 681093.45 norm 4.44e+022 alpha -5.61 Murphy_E 1.23e-012
X5 10548180
X4 65872414443674
X3 346000775732392099095
X2 -3268571414296022939325696
X1 -17770017691404932559946270671390
X0 -68272594283809518618028718791391900
Y1 1004117691684491791
Y0 -902758133106403305692244038331
M 651886633353005919381771687043765238846851954879473207330954413419787252845136965036205569645777678252656625234256966016315353397642097567365327054578108901
END POLY

BEGIN POLY #skewness 393387.88 norm 2.65e+022 alpha -6.06 Murphy_E 1.26e-012
X5 10622640
X4 -650082728680806
X3 -75474926880251900980
X2 16655239617613541173921372
X1 8213895936711165839350678384329
X0 635987225522108651958069126252736860
Y1 4088351820732338687
Y0 -901540280334504005500195732591
M 5853027790057908631823647806294840738592764688317492100000167684302954155083969230336410807181597234570412111784750920826126980267529770814995939979858884082
END POLY

jasonp · 2010-06-09, 02:51

pol51 gets much less efficient when the leading coefficient you give it is too small; each size of input number has a preferred size of leading coefficient that increases the rate of polynomials found while maintaining their quality. For your input size that preferred range is around 1e7 or so.

The E-value is not an exact measure of how good a polynomial is; it only isolates the few best polynomials, but you then have to sieve each polynomial a little bit to get its true efficiency. The skewness is not a tiebreaker between polynomials with similar E-values; it is just a number that is needed for a polynomial to achieve its calculated E-value.

2010-06-02, 08:39	#25
Karl M Johnson Mar 2010 19B₁₆ Posts	Now that I've found out how to force Msieve to select polynomials longer, I will rather let msieve look for it longer, than sieve longer.Poly selection is the most accelerated step right now. After running Msieve for 2.5 hours selecting Polys in [1,20480] selection, it finally stopped with the following: Code: name: rsa110 n: 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667 skew: 60693.32 Y0 -1753366490265555850692 Y1 221316341387 c0 26296772189237990432320457 c1 39506829751983394903574 c2 784404813837512059 c3 -25719356093546 c4 -164980728 c5 2160 #size 2.360848e-010, alpha -6.151039, combined = 5.194095e-011 Last fiddled with by Karl M Johnson on 2010-06-02 at 09:21

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Poly search candidates	schickel	Msieve	32	2013-11-05 19:11
Good enough poly for c155?	theuser	Msieve	4	2012-10-07 09:00
GNFS poly selection	frmky	Factoring	14	2012-07-23 01:57
Can someone run a couple of poly searches for me?	schickel	Msieve	12	2012-05-25 03:45
poly selection in MPQS	bsquared	Factoring	3	2007-02-28 14:22

2010-06-02, 07:12	#23
Karl M Johnson Mar 2010 3·137 Posts	Now I noticed it runs longer than the limit allows. Marvellous!

2010-06-02, 10:33	#26
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	As Serge mentioned, the objective is to finish in the shortest total time. Beyond a certain point you are not going to find a polynomial that sieves sufficiently faster to justify the extra search time. My personal rule of thumb is that poly searching should not take up more than 5% of the total time, so if you have multiple machines or small jobs then you should be searching for less time. Also, there is a per-leading-coefficient timeout that always applies to the search, so the amount of searching you do for any particular leading coefficient is capped. Spending longer on the search means you try larger and larger coefficients, which find polynmials more often but the average quality deteriorates.

2010-06-02, 10:57	#27
Karl M Johnson Mar 2010 3·137 Posts	As far as I understand it, the better the factorized number by GNFS, the better the polynomial should be. If it's RSA-100, well, the difference could be at most half of hour. However, if it's RSA-190, I'd spend a generous amout of time(but, of course, not more than 10% estimated) on poly selection. Since the right, optimized polynomial would probably reduce sieving by weeks, maybe months.

2010-06-09, 02:51	#30
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	pol51 gets much less efficient when the leading coefficient you give it is too small; each size of input number has a preferred size of leading coefficient that increases the rate of polynomials found while maintaining their quality. For your input size that preferred range is around 1e7 or so. The E-value is not an exact measure of how good a polynomial is; it only isolates the few best polynomials, but you then have to sieve each polynomial a little bit to get its true efficiency. The skewness is not a tiebreaker between polynomials with similar E-values; it is just a number that is needed for a polynomial to achieve its calculated E-value.