mersenneforum.org Status
 Register FAQ Search Today's Posts Mark Forums Read

2017-09-09, 17:27   #34
ryanp

Jun 2012
Boulder, CO

23·5·7 Posts

Quote:
 Originally Posted by rcv Is the c156 of 2^1344+1 of interest? http://www.factordb.com/index.php?id...00000032321623 The exponent has one too many factors of 2 to be among William Lipp's "official" eleven-smooth numbers. (1344=2^6*3*7). And it's just beyond the official Cunningham Table limits. Factor isn't presently shown in factordb or jcrombie's database.
I'll leave that for the forum, or for a later time. Right now I'm sieving the M2200 c213 using this SNFS poly:

Code:
n: 126995944778384428343817467782763835965797446765537889426743251291836133619348289537505627894595882345088764593485439135004224536319773689870707463091317828498596530820195257967005647404285565398502129893378166401
# 2^1100+1^1100, difficulty: 264.91, skewness: 1.00, alpha: 1.45
# cost: 2.54145e+19, est. time: 12102.14 GHz days (not accurate yet!)
skew: 1.000
c4: 1
c3: -1
c2: 1
c1: -1
c0: 1
Y1: -1
Y0: 1684996666696914987166688442938726917102321526408785780068975640576
m: 1684996666696914987166688442938726917102321526408785780068975640576
type: snfs

 2017-09-11, 23:08 #35 rcv   Dec 2011 11×13 Posts Speaking of fishing lessons... There is another unfactored 11-smooth number with 213 digits: c213.of.2^3150+1L jcrombie's Web Site reports a degree 8 polynomial with SNFS difficulty 252.865. (I'm hoping to understand how that is obtained, so I might apply the method to numbers with larger bases.) I define two functions, applicable to base 2 Cunninghams, $2^n+1 = LL[n] \times MM[n]$, where n is an odd multiple of 2 $LL[n]=2\times2^{(n-2)\div 2}-2\times 2^{(n-2)\div 4}+1$ $MM[n]=2\times2^{(n-2)\div 2}+2\times 2^{(n-2)\div 4}+1$ By recursively dividing out the algebraic factors, I obtain an algebraic expression for the Aurifeuillean L primitive of 2^3150+1: $\frac{LL[210] LL[3150] MM[90] MM[150]}{LL[30] LL[450] MM[630] MM[1050]}=\text{c217}\qquad\qquad(1)$ The result is a 217-digit number, which has been partially factored to: 12601 * c213 (as shown above). The algebraic expression for the L primitive seems too complex to use in SNFS. A long division of (1) would result in not fewer than 105 terms. Obviously, since (1) computes the primitive, nothing will divide it. However, it may be that multiplication by some of the algebraic factors which were removed might result in a simpler algebraic expression. Indeed, the Aurifeuillean L-primitive of 2^450+1 is: $\frac{LL[30] LL[450]}{MM[90] MM[150]}=\text{c37}\qquad\qquad(2)$ The result is a 37-digit number, which has been fully factored. Multiplying (1) by (2), we obtain an expression that when fully expanded should have fewer terms: $\frac{LL[210] LL[3150]}{MM[630] MM[1050]}=\text{c217}\times\text{c37}=\text{c253}\qquad\qquad(3)$ The result is a 253-digit number, whose logarithm is approximately 252.865. Setting a=2, I can rewrite (3) in a standard algebaic form: $\frac{(1 - 2 a^{52} + 2 a^{104})(1 - 256 a^{780} + 32768 a^{1560})}{(1 + 4 a^{156} + 8 a^{312})(1 + 8 a^{260} + 32 a^{520})}=\text{c253}\qquad\qquad(4)$ Setting $b=a^{52}$, I can rewrite (4) in an even simpler form: $\frac{(1 - 2 b + 2 b^2)(1 - 256 b^{15} + 32768 b^{30})}{(1 + 4 b^3 + 8 b^6)(1 + 8 b^5 + 32 b^{10})}=\text{c253}\qquad\qquad(5)$ Now, with the help of Mathematica, I expand the numerator and denominator: $\frac{1 - 2 b + 2 b^2 - 256 b^{15} + 512 b^{16} - 512 b^{17} + 32768 b^{30} - 65536 b^{31} + 65536 b^{32}}{1 + 4 b^3 + 8 b^5 + 8 b^6 + 32 b^8 + 32 b^{10} + 64 b^{11} + 128b^{13} + 256 b^{16}}=\text{c253}\qquad\qquad(6)$ Mathematica's PolynomialRemainder function reports the remainder is 0. The PolynomialQuotient function provides the long-division as: $1 - 2 b + 2 b^2 - 4 b^3 + 8 b^4 - 16 b^5 + 24 b^6 - 32 b^7 + 48 b^8 - 64 b^9 + 96 b^{10} - 128 b^{11} + 128 b^{12} - 128 b^{13} + 128 b^{14} - 256 b^{15} + 256 b^{16}=\text{c253}\qquad\qquad(7)$ Now, the path becomes less clear, and I could use some guidance. (Fishing lessons.) I factor out $b^8$ from (7): $b^8\left(b^{-8} - 2 b^{-7} + 2 b^{-6} - 4 b^{-5} + 8 b^{-4} - 16 b^{-3} + 24 b^{-2} - 32 b^{-1} + 48 b^0 - 64 b^1 + 96 b^2 - 128 b^3 + 128 b^4 - 128 b^5 + 128 b^6 - 256 b^7 + 256 b^8\right)=\text{c253}\qquad\qquad(8)$ Next, I substitute $b=\frac{d}{\sqrt{2}}$. $\frac{d^8}{16}\left(16 d^{-8}-16\sqrt 2 d^{-7}+16 d^{-6}-16 \sqrt 2 d^{-5}+32 d^{-4} -32\sqrt 2 d^{-3}+48 d^{-2}-32\sqrt 2 d^{-1}+ 48-32 \sqrt 2 d+ 48 d^2 -32 \sqrt 2 d^3+32 d^4 -16 \sqrt 2 d^5+16 d^6 -16 \sqrt 2 d^7 + 16 d^8\right)=\text{c253}\qquad\qquad(9)$ $=d^8\left(d^{-8}-\sqrt 2 d^{-7}+d^{-6}-\sqrt 2 d^{-5}+2 d^{-4} -2\sqrt 2 d^{-3}+3 d^{-2}-2\sqrt 2 d^{-1}+ 3-2 \sqrt 2 d+ 3 d^2 -2 \sqrt 2 d^3+2 d^4 - \sqrt 2 d^5+ d^6 - \sqrt 2 d^7 + d^8\right)=\text{c253}\qquad\qquad(10)$ How do we complete this? Can someone provide the detailed algebra to obtain an SNFS polynomial? Thanks in advance. Last fiddled with by rcv on 2017-09-11 at 23:41
 2017-09-12, 20:46 #36 swellman     Jun 2012 5×599 Posts @rcv - do you intend to factor the C213 from 2^3150+1L? I ran some test sieving on it and it's a tough composite to crack - on the order of 400-500,000 core-hours to sieve. The octic demands its toll! As to your algebra problem, (10) seems almost intractable but I'm no expert. Good luck!
2017-09-12, 22:00   #37
rcv

Dec 2011

100011112 Posts

Quote:
 Originally Posted by swellman @rcv - do you intend to factor the C213 from 2^3150+1L? I ran some test sieving on it and it's a tough composite to crack - on the order of 400-500,000 core-hours to sieve. The octic demands its toll! As to your algebra problem, (10) seems almost intractable but I'm no expert. Good luck!
No, I don't have anything close to the CPU resources to crack this number! I am just hoping to learn, so I might apply the method to factor other numbers with Aurifeuillean factors.

As far as my equation (10), this is in the form (as I recall, with palindromic coefficients) by which each pair of terms, $d^{-k}+d^k$, which have identical coefficients, can be combined to a single term, perhaps in another variable and perhaps with a different coefficient.

I have approached this several times, but each time I have run into a dead end. I have been working at this from the point of view of the old high school algebra question, if you are given $(d+1/d)$, then calculate $(d^3+1/d^3)$.

$(d+d^{-1})^3=d^3+3d+3d^{-1}+d^{-3}$
$-3(d+d^{-1})=-3d-3d^{-1}$
$(d+d^{-1})^3-3(d+d^{-1})=d^3+d^{-3}$

So, if $d+d^{-1}=3$, then $d^3+d^{-3}=18$

Last fiddled with by rcv on 2017-09-12 at 22:04

 2017-09-13, 06:41 #38 rcv   Dec 2011 100011112 Posts $d^8\left(d^{-8}-\sqrt 2 d^{-7}+d^{-6}-\sqrt 2 d^{-5}+2 d^{-4} -2\sqrt 2 d^{-3}+3 d^{-2}-2\sqrt 2 d^{-1}+ 3-2 \sqrt 2 d+ 3 d^2 -2 \sqrt 2 d^3+2 d^4 - \sqrt 2 d^5+ d^6 - \sqrt 2 d^7 + d^8\right)=\text{c253}\qquad\qquad(10)$ Let $e=d+d^{-1}$ Using the method outlined in my previous post, we combine pairs of terms from the right hand factor of (10) and write them in terms of $e$: $3=3$ $-2\sqrt{2}(d^1+d^{-1})=-2\sqrt{2}(e)$ $3(d^2+d^{-2})=3(e^2-2)$ $-2\sqrt{2}(d^3+d^{-3})=-2\sqrt{2}(e^3-3e)$ $2(d^4+d^{-4})=2(e^4-4e^2+2)$ $-\sqrt{2}(d^5+d^{-5})=-sqrt{2}(e^5-5e^3+5e)$ $1(d^6+d^{-6})=1(e^6-6e^4+9e^2-2)$ $-\sqrt{2}(d^7+d^{-7})=-sqrt{2}(e^7-7e^5+14e^3-7e)$ $1(d^8+d^{-8})=1(e^8-8e^6+20e^4-16e^2+2)$ Summing, and replacing the right hand factor, we get $d^8\left(e^8-\sqrt{2}e^7-7e^6+6\sqrt{2}e^5+16e^4-11\sqrt{2}e^3-12e^2+6\sqrt{2}e+1\right)=\text{c253}\quad\quad(11)$ Now, I substitute $e=\frac{f}{\sqrt{2}}$ $d^8\left(\frac{f^8}{16}-\frac{f^7}{8}-\frac{7f^6}{8}+\frac{6f^5}{4}+\frac{16f^4}{4}-\frac{11f^3}{2}-\frac{12f^2}{2}+\frac{6f}{1}+\frac{1}{1}\right)=\text{c253}\quad\quad(12)$ $\frac{d^8}{16} \left(f^8-2f^7-14f^6+24f^5+64f^4-88f^3-96f^2+96f+16\right)=\text{c253}\quad\quad(13)$ Recall that $d=\sqrt{2}b$ $b^8 \left(f^8-2f^7-14f^6+24f^5+64f^4-88f^3-96f^2+96f+16\right)=\text{c253}\quad\quad(14)$ $e=d+d^{-1}=\sqrt{2}b+\frac{1}{\sqrt{2}b}\quad\quad(15)$ $f=\sqrt{2}e=2b+\frac{1}{b}\quad\longrightarrow\quad fb=2b^2+1\quad\quad(16)$ Let $g=fb\quad\quad(17)$ $g^8-2g^7b-14g^6b^2+24g^5b^3+64g^4b^4-88g^3b^5-96g^2b^6+96gb^7+16b^8=\text{c253}\quad\quad(18)$ $1-2b-14b^2+24b^3+64b^4-88b^5-96b^6+96b^7+16b^8\equiv\text{c253}\quad\pmod {g-1}\quad\quad(19)$ $b=2^{52}=4503599627370496\quad\quad(20)$ $g-1=2^{105}=40564819207303340847894502572032\quad\quad(21)$ $c253 \equiv 40564819207303331840695247831041 \quad\pmod{g-1}\quad\quad(22)$ Is there any chance this is correct? Last fiddled with by rcv on 2017-09-13 at 06:44
 2017-09-17, 04:13 #39 rcv   Dec 2011 11·13 Posts With respect to my previous series of posts, I think I have it figured out. I believe the algebra shown above is basically correct for the algebraic side. Disregard the last few numbered equations which were an irrational stab at the rational side. I will plan to post something about the corresponding rational side when I have the time to write something cogent. Meanwhile, a new ElevenSmooth 49-digit factor of M(29700) has appeared in factordb. (Not my work.) p49 = 26400155219669229975537170269019760942301
2017-09-17, 11:25   #40
swellman

Jun 2012

56638 Posts

Quote:
 Originally Posted by rcv Meanwhile, a new ElevenSmooth 49-digit factor of M(29700) has appeared in factordb. (Not my work.) p49 = 26400155219669229975537170269019760942301
That's the work of Ryan Propper. He's got most or all of the composite cofactors of M(3326400) < 1000 digits undergoing ECM. He's found a couple of factors in the big fdb list, as well as a couple from the list on the ElevenSmooth project page. Anything found from the list on the 11S page is reported here.

Ryan is also attempting the lowest difficulty SNFS composites as well, with factors reported here. There do not appear to be many feasible SNFS factorization jobs left in that project.

 2017-09-25, 19:46 #41 ryanp     Jun 2012 Boulder, CO 23·5·7 Posts For those keeping score at home, also got a p60 ECM hit on this c564 cofactor of 2^2800 + 1:
 2017-10-12, 17:41 #42 swellman     Jun 2012 5×599 Posts 2 more ECM hits by RyanP Ryan continues to run ECM on the ElevenSmooth project. Two recent results. M12096 composite cofactor C996 yielded an ECM hit Code: Using B1=2900000000, B2=81523616554398, polynomial Dickson(30), sigma=3904585649 ... Found probable prime factor of 58 digits: 7899984695355088860500288590353045075963122543602810243969 Leaving a C938 cofactor. M23100L cofactor C701 also got an ECM hit Code: Using B1=7600000000, B2=322813090700118, polynomial Dickson(30), sigma=3343323451 ... Found probable prime factor of 56 digits: 48760786864644474856730499321644513230245978254290690801 Leaving a C645 cofactor. Last fiddled with by swellman on 2017-10-12 at 17:47
2017-10-13, 23:36   #43
rcv

Dec 2011

100011112 Posts

Quote:
 Originally Posted by swellman Ryan continues to run ECM on the ElevenSmooth project. Two recent results.
Thanks for the info! Subsequent to Ryan's p60 hit on 2^2800+1 (two posts up), someone reported a p58+p447 split to factordb.com. I presume that was also Ryan?

Last fiddled with by rcv on 2017-10-13 at 23:39

2017-10-14, 01:20   #44
swellman

Jun 2012

299510 Posts

Quote:
 Originally Posted by rcv Thanks for the info! Subsequent to Ryan's p60 hit on 2^2800+1 (two posts up), someone reported a p58+p447 split to factordb.com. I presume that was also Ryan?
Yes Ryan found that factor. Sorry it wasn’t reported here, as M5600 isn’t displayed on the ElevenSmooth progress tables. Everything is reported to factordb of course.

Also found by Ryan was a p57 prime factor of a C852 cofactor of 2^5400+1, leaving a C795. Results reported to factordb.

Last fiddled with by swellman on 2017-10-14 at 01:33

 Similar Threads Thread Thread Starter Forum Replies Last Post Primeinator Operation Billion Digits 5 2011-12-06 02:35 1997rj7 Lone Mersenne Hunters 27 2008-09-29 13:52 Uncwilly Operation Billion Digits 22 2005-10-25 14:05 paulunderwood 3*2^n-1 Search 2 2005-03-13 17:03 1997rj7 Lone Mersenne Hunters 25 2004-06-18 16:46

All times are UTC. The time now is 10:27.

Fri May 14 10:27:34 UTC 2021 up 36 days, 5:08, 0 users, load averages: 2.28, 2.14, 2.17