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

797 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

67578 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

797 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

94016 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

26×37 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

797 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

356710 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

24×227 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 online now   Reply With Quote
Old 2022-07-18, 05:59   #504
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

356710 Posts
Default

Quote:
Originally Posted by swellman View Post
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
sweety439 is offline   Reply With Quote
Old 2022-07-18, 11:10   #505
swellman
 
swellman's Avatar
 
Jun 2012

24×227 Posts
Default

Quote:
Originally Posted by sweety439 View Post
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
I can help you work these numbers. Please PM me.
swellman is online now   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 20:37.


Thu Aug 11 20:37:13 UTC 2022 up 35 days, 15:24, 2 users, load averages: 1.16, 1.05, 1.13

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.

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