mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-06-22, 13:03   #496
charybdis
 
charybdis's Avatar
 
Apr 2020

22×11×17 Posts
Default

Quote:
Originally Posted by kruoli View Post
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.
charybdis is offline   Reply With Quote
Old 2022-06-22, 14:17   #497
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,449 Posts
Default

Quote:
Originally Posted by charybdis View Post
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
sweety439 is offline   Reply With Quote
Old 2022-06-22, 14:35   #498
charybdis
 
charybdis's Avatar
 
Apr 2020

13548 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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.
charybdis is offline   Reply With Quote
Old 2022-06-22, 15:37   #499
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22×587 Posts
Default

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.
chris2be8 is offline   Reply With Quote
Old 2022-06-22, 16:21   #500
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22·587 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2022-06-22, 16:42   #501
charybdis
 
charybdis's Avatar
 
Apr 2020

74810 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
charybdis is offline   Reply With Quote
Old 2022-06-28, 17:32   #502
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

3,449 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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
sweety439 is offline   Reply With Quote
Old 2022-06-29, 00:17   #503
swellman
 
swellman's Avatar
 
Jun 2012

67368 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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.
swellman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Vanishing Fermat Quotients and Brent's List Zeta-Flux Factoring 74 2010-04-07 22:03
Brent-Suyama extension of P-1 factoring S485122 Math 1 2009-08-23 15:21
Brent-Montgomery-te Riele numbers FactorEyes Factoring 23 2008-02-22 00:36
brent suyama extension in P-1 bsquared Factoring 9 2007-05-18 19:24
Brent's p-1 - How to deal with memory problems? jhillenb Factoring 4 2005-01-11 23:50

All times are UTC. The time now is 05:51.


Wed Jun 29 05:51:49 UTC 2022 up 76 days, 3:53, 1 user, load averages: 1.18, 1.20, 1.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔