Polynomial selection for 2,1109+ c225

[charybdis]

Originally Posted by sweety439

2^1109+1 should use SNFS instead of GNFS, see this page

If you'd actually bothered reading the thread, you'd have noticed that I, and others, have already come to the same conclusion by actually test-sieving, rather than using a guesstimate of GNFS equivalent difficulty which turns out to be fairly wrong (it's more like GNFS-223 or 224).

[sweety439]

Originally Posted by charybdis

If you'd actually bothered reading the thread, you'd have noticed that I, and others, have already come to the same conclusion by actually test-sieving, rather than using a guesstimate of GNFS equivalent difficulty which turns out to be fairly wrong (it's more like GNFS-223 or 224).

First, 223 or 224 is still smaller than 225 (the composite cofactor of 2^1109+1 has 225 digits), thus SNFS is still better

Second, SNFS difficulty is 334.143 is equivalent to GNFS difficulty 223 or 224, so this means SNFS difficulty 3*x is equivalent to GNFS difficulty 2*x?

[swellman]

Originally Posted by sweety439

First, 223 or 224 is still smaller than 225 (the composite cofactor of 2^1109+1 has 225 digits), thus SNFS is still better

Second, SNFS difficulty is 334.143 is equivalent to GNFS difficulty 223 or 224, so this means SNFS difficulty 3*x is equivalent to GNFS difficulty 2*x?

Indeed, the SNFS polynomial for 2^1109+1 seems to defy conventional wisdom but then this is not a conventional sized job. And with its simple form, one would expect the SNFS poly to sieve well. So well that it seems to perform better than Gimarel’s record setting poly search result to date!

[sweety439]

Originally Posted by swellman

Indeed, the SNFS polynomial for 2^1109+1 seems to defy conventional wisdom but then this is not a conventional sized job. And with its simple form, one would expect the SNFS poly to sieve well. So well that it seems to perform better than Gimarel’s record setting poly search result to date!

10^471+1 has SNFS difficulty 314 and equivalent to GNFS difficulty 205 (see this page), and the composite cofactor has 209 digits, and Bo Chen, Wenjie Fang, Alfred Eichhorn, Danilo Nitsche, Kurt Beschorner use SNFS instead of GNFS to factor this number (see this page)

[swellman]

Originally Posted by Gimarel

A few better polys:

n: 126451876805119252959661548967232013601866431183534308908427174011662073024932261126233275630388431500884665768427172907593022873289431612806891303891687570778305960728323476541491713906981621716831593952842244282430058291761
# norm 4.071969e-16 alpha -9.752538 e 2.347e-16 rroots 4
skew: 4099972.17
c0: 75411469889145395046741594539510303818011021471
c1: -19691135073162315084594784624103449198750
c2: -99438233376176899175468255217094130
c3: 4394174158803947144118894880
c4: 16400189169252108563099
c5: -232506169843650
c6: 4347000
Y0: -2754045785939680784737571685756365496
Y1: 4538373177770229797351
# MurphyF (Bf=6.872e+10,Bg=3.436e+10,area=1.766e+18) = 2.477e-09

n: 126451876805119252959661548967232013601866431183534308908427174011662073024932261126233275630388431500884665768427172907593022873289431612806891303891687570778305960728323476541491713906981621716831593952842244282430058291761
# norm 4.143131e-16 alpha -9.942142 e 2.339e-16 rroots 6
skew: 45290543.52
c0: -269505104302737992226579881824069273348411150390400
c1: 31592047037538685851862704375760833455315760
c2: 1703133447582614942920906384956167268
c3: -129971466498994600011942115252
c4: -2314332759744553531033
c5: 29445952854202
c6: 50400
Y0: -3686227314243652116010167240943024263
Y1: 30016011206759833401211
# MurphyF (Bf=6.872e+10,Bg=3.436e+10,area=1.766e+18) = 2.466e-09

n: 126451876805119252959661548967232013601866431183534308908427174011662073024932261126233275630388431500884665768427172907593022873289431612806891303891687570778305960728323476541491713906981621716831593952842244282430058291761
# norm 4.031559e-16 alpha -12.133288 e 2.292e-16 rroots 4
skew: 29346738.87
c0: 59455777517328054184793219662976360401235607337335
c1: 112779972076226040399992792530106515604140047
c2: -4298413822937233372631606035726816679
c3: -1413322411017627466877645728827
c4: -821206219249483879936
c5: 180781205008140
c6: 2494800
Y0: -2774524181546352716484898272284905686
Y1: 85331174827726081541743
# MurphyF (Bf=6.872e+10,Bg=3.436e+10,area=1.766e+18) = 2.433e-09

I'll continue searching if testsieving indicates that these are at least competitive to the snfs poly.

I took the liberty of adding the top scoring poly above to the record table. Of course I’ll update it if better scores are sought and found.

[charybdis]

Originally Posted by sweety439

First, 223 or 224 is still smaller than 225 (the composite cofactor of 2^1109+1 has 225 digits), thus SNFS is still better

Did you not read any more than the last 6 words of my post?? I literally said that I had already concluded SNFS was better. I don't know what sort of person you take me for if you think I need it pointed out to me that 223 and 224 are smaller than 225.

Had it been down to me, your original post would have ended up in the "more off-topic" thread along with other posts where you have demonstrated a spectacular lack of reading comprehension.

Second, SNFS difficulty is 334.143 is equivalent to GNFS difficulty 223 or 224, so this means SNFS difficulty 3*x is equivalent to GNFS difficulty 2*x?

At this size, for SNFS sextic polynomials with small coefficients, yes. In general, no.

Originally Posted by sweety439

10^471+1 has SNFS difficulty 314 and equivalent to GNFS difficulty 205 (see this page), and the composite cofactor has 209 digits, and Bo Chen, Wenjie Fang, Alfred Eichhorn, Danilo Nitsche, Kurt Beschorner use SNFS instead of GNFS to factor this number (see this page)

Don't believe the estimates that site gives. SNFS-314 is substantially harder than GNFS-205, and I would guess it is a bit harder than GNFS-209 too, but I can't speak for Kurt et al. Perhaps they preferred SNFS because they didn't want to run a polynomial search; perhaps they test-sieved the SNFS polynomial against an existing GNFS polynomial for a similarly-sized number and found that SNFS was preferable.

[Andrew Usher]

There's clearly no easy and definite rule here. I suspect that number, like this, fell very near the line between the two. If anyone's disappointed by not getting a record GNFS, well there are more potential large GNFS candidates; not sure if any good ones would be quite the right size though. Clearing those 'small' composites is not going to be extinct.