mersenneforum.org Brent tables reservations
 Register FAQ Search Today's Posts Mark Forums Read

2022-06-22, 13:03   #496
charybdis

Apr 2020

19·43 Posts

Quote:
 Originally Posted by kruoli Where is my error thinking that both have >300 SNFS difficulty? Is this wrong because of algebraic factors?
Yes, both exponents are divisible by 3 so you can divide out the algebraic factors 13^94+1 and 13^96+1 respectively. So you have to multiply the size of the number by 2/3 to get the actual difficulty.

2022-06-22, 14:17   #497
sweety439

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

72×73 Posts

Quote:
 Originally Posted by charybdis Yes, both exponents are divisible by 3 so you can divide out the algebraic factors 13^94+1 and 13^96+1 respectively. So you have to multiply the size of the number by 2/3 to get the actual difficulty.
The nontrivial parts are Phi(564,13) and Phi(576,13), where Phi is the cyclotomic polynomial, thus the SNFS difficulty should be eulerphi(564)*log(13) = 204.9656 and eulerphi(576)*log(13) = 213.8771, right?

Last fiddled with by sweety439 on 2022-06-22 at 14:21

2022-06-22, 14:35   #498
charybdis

Apr 2020

81710 Posts

Quote:
 Originally Posted by sweety439 The nontrivial parts are Phi(564,13) and Phi(576,13), where Phi is the cyclotomic polynomial, thus the SNFS difficulty should be eulerphi(564)*log(13) = 204.9656 and eulerphi(576)*log(13) = 213.8771, right?
Correct for the second one, but not the first.
288 = 2*3*47, so 13^288+1 has algebraic factors 13^94+1 and 13^6+1, which themselves share a common factor 13^2+1. We can't pull out both algebraic factors and end up with a usable SNFS polynomial; even with the degree-halving trick we would have a degree-46 polynomial.

 2022-06-22, 15:37 #499 chris2be8     Sep 2009 236910 Posts 13^282+1 is probably easier by GNFS, SNFS 210 is about as hard as GNFS 155, but 13^282+1's cofactor is 147 digits. 13^288+1 is about equal difficulty by SNFS and GNFS. SNFS 214 is about as hard as GNFS 152 which is how many digits the cofactor is. Neither should take you too long on a decent PC.
 2022-06-22, 16:21 #500 chris2be8     Sep 2009 1001010000012 Posts Update, I've generated a .poly for 13^288+1 and msieve rates it's e-score as 4.429e-12 which is only slightly worse that the record for GNFS 152 (5.193e-12). So SNFS might be quicker since it saves time looking for a .poly. If you want to use the SNFS .poly it is: Code: n: 71438373999729136352606292343760129183029739070786196603000989067197279062061478948276862644139546551399870347831118641859705696979258190407032284290689 type: snfs # m=13^32 m: 442779263776840698304313192148785281 c6: 1 c3: -1 c0: 1 # msieve rating: skew 1.00, size 1.484e-10, alpha 1.996, combined = 4.429e-12 rroots = 0
2022-06-22, 16:42   #501
charybdis

Apr 2020

19·43 Posts

Quote:
 Originally Posted by chris2be8 Update, I've generated a .poly for 13^288+1 and msieve rates it's e-score as 4.429e-12 which is only slightly worse that the record for GNFS 152 (5.193e-12). So SNFS might be quicker since it saves time looking for a .poly.
Usual warning that you can't directly compare E-scores for polys with different degrees. Lower degrees overpeform their scores, higher degrees underperform.

2022-06-28, 17:32   #502
sweety439

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

72×73 Posts

Quote:
 Originally Posted by chris2be8 SNFS 210 is about as hard as GNFS 155
What is the approximately equivalent for SNFS and GNFS? I guess that SNFS difficulty n is approximately equivalent to GNFS difficulty (2/3)*n, however, if my guess is true, then SNFS 210 is approximately equivalent to GNFS 140

2022-06-29, 00:17   #503
swellman

Jun 2012

3,643 Posts

Quote:
 Originally Posted by sweety439 What is the approximately equivalent for SNFS and GNFS? I guess that SNFS difficulty n is approximately equivalent to GNFS difficulty (2/3)*n, however, if my guess is true, then SNFS 210 is approximately equivalent to GNFS 140
The commonly used ratio of GNFS/SNFS is 0.68 to 0.69. This ratio doesn’t hold true here for the case of SNFS 210 ~ GNFS 155 but those values are on the low side.

The ratio holds much better at higher difficulty.

2022-07-18, 05:59   #504
sweety439

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

67718 Posts

Quote:
 Originally Posted by swellman The commonly used ratio of GNFS/SNFS is 0.68 to 0.69. This ratio doesn’t hold true here for the case of SNFS 210 ~ GNFS 155 but those values are on the low side. The ratio holds much better at higher difficulty.
So can you factor these two numbers (the composite cofactors of 13^282+1 and 13^288+1)? They are much smaller than your C193, also they have simple SNFS polynomials, while your C193 can only be used GNFS

2022-07-18, 11:10   #505
swellman

Jun 2012

3,643 Posts

Quote:
 Originally Posted by sweety439 So can you factor these two numbers (the composite cofactors of 13^282+1 and 13^288+1)? They are much smaller than your C193, also they have simple SNFS polynomials, while your C193 can only be used GNFS

 Similar Threads Thread Thread Starter Forum Replies Last Post Zeta-Flux Factoring 74 2010-04-07 22:03 S485122 Math 1 2009-08-23 15:21 FactorEyes Factoring 23 2008-02-22 00:36 bsquared Factoring 9 2007-05-18 19:24 jhillenb Factoring 4 2005-01-11 23:50

All times are UTC. The time now is 16:25.

Wed Aug 17 16:25:26 UTC 2022 up 41 days, 11:12, 1 user, load averages: 1.25, 1.21, 1.30