mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   ElevenSmooth (https://www.mersenneforum.org/forumdisplay.php?f=31)
-   -   Status (https://www.mersenneforum.org/showthread.php?t=1460)

ryanp 2017-09-09 17:27

[QUOTE=rcv;467390]Is the c156 of 2^1344+1 of interest? [URL]http://www.factordb.com/index.php?id=1100000000032321623[/URL]

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.[/QUOTE]

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[/CODE]

rcv 2017-09-11 23:08

Speaking of fishing lessons...

There is another unfactored 11-smooth number with 213 digits: [URL="http://www.factordb.com/index.php?id=1100000000192857669"]c213.of.2^3150+1L[/URL]

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,
[TEX]2^n+1 = LL[n] \times MM[n][/TEX], where n is an odd multiple of 2
[TEX]LL[n]=2\times2^{(n-2)\div 2}-2\times 2^{(n-2)\div 4}+1[/TEX]
[TEX]MM[n]=2\times2^{(n-2)\div 2}+2\times 2^{(n-2)\div 4}+1[/TEX]

By recursively dividing out the algebraic factors, I obtain an algebraic expression for the Aurifeuillean L primitive of 2^3150+1:
[TEX]\frac{LL[210] LL[3150] MM[90] MM[150]}{LL[30] LL[450] MM[630] MM[1050]}=\text{c217}\qquad\qquad(1)[/TEX]

The result is [URL="http://www.factordb.com/index.php?id=1100000000493609236"]a 217-digit number[/URL], 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:
[TEX]\frac{LL[30] LL[450]}{MM[90] MM[150]}=\text{c37}\qquad\qquad(2)[/TEX]

The result is [URL="http://www.factordb.com/index.php?id=1100000000001689431"]a 37-digit number[/URL], which has been fully factored.

Multiplying (1) by (2), we obtain an expression that when fully expanded should have fewer terms:
[TEX]\frac{LL[210] LL[3150]}{MM[630] MM[1050]}=\text{c217}\times\text{c37}=\text{c253}\qquad\qquad(3)[/TEX]

The result is [URL="http://www.factordb.com/index.php?id=1100000000967684817"]a 253-digit number[/URL], whose logarithm is approximately 252.865.

Setting a=2, I can rewrite (3) in a standard algebaic form:
[TEX]\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)[/TEX]

Setting [TEX]b=a^{52}[/TEX], I can rewrite (4) in an even simpler form:
[TEX]\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)[/TEX]

Now, with the help of Mathematica, I expand the numerator and denominator:
[TEX]\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)[/TEX]

Mathematica's PolynomialRemainder function reports the remainder is 0. The PolynomialQuotient function provides the long-division as:
[TEX]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)[/TEX]

Now, the path becomes less clear, and I could use some guidance. (Fishing lessons.)

I factor out [TEX]b^8[/TEX] from (7):
[TEX]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)[/TEX]

Next, I substitute [TEX]b=\frac{d}{\sqrt{2}}[/TEX].
[TEX]\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)[/TEX]

[TEX]=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)[/TEX]

How do we complete this? Can someone provide the detailed algebra to obtain an SNFS polynomial? Thanks in advance.

swellman 2017-09-12 20:46

@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!

rcv 2017-09-12 22:00

[QUOTE=swellman;467657]@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![/QUOTE]
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, [TEX]d^{-k}+d^k[/TEX], 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 [TEX](d+1/d)[/TEX], then calculate [TEX](d^3+1/d^3)[/TEX].

[TEX](d+d^{-1})^3=d^3+3d+3d^{-1}+d^{-3}[/TEX]
[TEX]-3(d+d^{-1})=-3d-3d^{-1}[/TEX]
[TEX](d+d^{-1})^3-3(d+d^{-1})=d^3+d^{-3}[/TEX]

So, if [TEX]d+d^{-1}=3[/TEX], then [TEX]d^3+d^{-3}=18[/TEX]

rcv 2017-09-13 06:41

[TEX]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)[/TEX]

Let [TEX]e=d+d^{-1}[/TEX]

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 [TEX]e[/TEX]:
[TEX]3=3[/TEX]

[TEX]-2\sqrt{2}(d^1+d^{-1})=-2\sqrt{2}(e)[/TEX]

[TEX]3(d^2+d^{-2})=3(e^2-2)[/TEX]

[TEX]-2\sqrt{2}(d^3+d^{-3})=-2\sqrt{2}(e^3-3e)[/TEX]

[TEX]2(d^4+d^{-4})=2(e^4-4e^2+2)[/TEX]

[TEX]-\sqrt{2}(d^5+d^{-5})=-sqrt{2}(e^5-5e^3+5e)[/TEX]

[TEX]1(d^6+d^{-6})=1(e^6-6e^4+9e^2-2)[/TEX]

[TEX]-\sqrt{2}(d^7+d^{-7})=-sqrt{2}(e^7-7e^5+14e^3-7e)[/TEX]

[TEX]1(d^8+d^{-8})=1(e^8-8e^6+20e^4-16e^2+2)[/TEX]

Summing, and replacing the right hand factor, we get
[TEX]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)[/TEX]

Now, I substitute [TEX]e=\frac{f}{\sqrt{2}}[/TEX]

[TEX]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)[/TEX]

[TEX]\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)[/TEX]

Recall that [TEX]d=\sqrt{2}b[/TEX]
[TEX]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)[/TEX]

[TEX]e=d+d^{-1}=\sqrt{2}b+\frac{1}{\sqrt{2}b}\quad\quad(15)[/TEX]

[TEX]f=\sqrt{2}e=2b+\frac{1}{b}\quad\longrightarrow\quad fb=2b^2+1\quad\quad(16)[/TEX]

Let [TEX]g=fb\quad\quad(17)[/TEX]

[TEX]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)[/TEX]

[TEX]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)[/TEX]

[TEX]b=2^{52}=4503599627370496\quad\quad(20)[/TEX]

[TEX]g-1=2^{105}=40564819207303340847894502572032\quad\quad(21)[/TEX]

[TEX]c253 \equiv 40564819207303331840695247831041 \quad\pmod{g-1}\quad\quad(22)[/TEX]

Is there any chance this is correct?

rcv 2017-09-17 04:13

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

swellman 2017-09-17 11:25

[QUOTE=rcv;467931]

Meanwhile, a new ElevenSmooth 49-digit factor of M(29700) has appeared in factordb. (Not my work.)

p49 = 26400155219669229975537170269019760942301[/QUOTE]

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.

ryanp 2017-09-25 19:46

For those keeping score at home, also got a p60 ECM hit on this c564 cofactor of 2^2800 + 1:

[PASTEBIN]3W56qS3j[/PASTEBIN]

swellman 2017-10-12 17:41

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[/code]

Leaving a [url=http://factordb.com/index.php?id=1100000001052887866]C938 cofactor[/url].


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[/code]

Leaving a [url=http://factordb.com/index.php?id=1100000001052882724]C645 cofactor[/url].

rcv 2017-10-13 23:36

[QUOTE=swellman;469712]Ryan continues to run ECM on the ElevenSmooth project. Two recent results.[/QUOTE]
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?

swellman 2017-10-14 01:20

[QUOTE=rcv;469809]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?[/QUOTE]

Yes Ryan found that factor. Sorry it wasn’t reported here, as M5600 isn’t displayed on the [url=http://home.earthlink.net/~elevensmooth/Progress.html]ElevenSmooth progress tables[/url]. 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.


All times are UTC. The time now is 09:18.

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