 mersenneforum.org Brent tables reservations
 Register FAQ Search Today's Posts Mark Forums Read  2022-06-22, 13:03   #496
charybdis

Apr 2020

7·107 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

3,461 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

7·107 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 22×587 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 234810 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

7·107 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

3,461 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

2·1,777 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.   Thread Tools Show Printable Version Email this Page 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 11:03.

Sun Jul 3 11:03:27 UTC 2022 up 80 days, 9:04, 0 users, load averages: 1.81, 1.50, 1.51