mersenneforum.org Polynomial selection for 2,1109+ c225
 Register FAQ Search Today's Posts Mark Forums Read

2022-12-20, 13:45   #45
charybdis

Apr 2020

22×3×79 Posts

Quote:
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).

2022-12-20, 13:57   #46
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

2·7·263 Posts

Quote:
 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?

2022-12-20, 14:21   #47
swellman

Jun 2012

3×1,303 Posts

Quote:
 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!

2022-12-20, 14:38   #48
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

2×7×263 Posts

Quote:
 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)

Last fiddled with by sweety439 on 2022-12-20 at 14:38

2022-12-20, 16:33   #49
swellman

Jun 2012

F4516 Posts

Quote:
 Originally Posted by Gimarel A few better polys: Code: 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.

2022-12-20, 19:34   #50
charybdis

Apr 2020

3B416 Posts

Quote:
 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.

Quote:
 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.

Quote:
 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.

 2022-12-21, 04:27 #51 Andrew Usher   Dec 2022 31210 Posts 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. Last fiddled with by Andrew Usher on 2022-12-21 at 04:28

 Similar Threads Thread Thread Starter Forum Replies Last Post Max0526 NFS@Home 9 2017-05-20 08:57 jasonp Msieve 65 2011-05-01 19:06 Unregistered Information & Answers 3 2011-04-16 14:24 fivemack Factoring 47 2009-06-16 00:24 CRGreathouse Factoring 2 2009-05-25 07:55

All times are UTC. The time now is 23:12.

Mon Mar 27 23:12:09 UTC 2023 up 221 days, 20:40, 0 users, load averages: 1.02, 0.92, 0.93