mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > ElevenSmooth

 
 
Thread Tools
Old 2017-09-09, 17:27   #34
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

331 Posts
Default

Quote:
Originally Posted by rcv View Post
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
ryanp is offline  
Old 2017-09-11, 23:08   #35
rcv
 
Dec 2011

11×13 Posts
Default

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<br />
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 <br />
+ 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 <br />
    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
rcv is offline  
Old 2017-09-12, 20:46   #36
swellman
 
swellman's Avatar
 
Jun 2012

62038 Posts
Default

@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!
swellman is online now  
Old 2017-09-12, 22:00   #37
rcv
 
Dec 2011

11×13 Posts
Default

Quote:
Originally Posted by swellman View Post
@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
rcv is offline  
Old 2017-09-13, 06:41   #38
rcv
 
Dec 2011

11×13 Posts
Default

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
rcv is offline  
Old 2017-09-17, 04:13   #39
rcv
 
Dec 2011

11×13 Posts
Default

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
rcv is offline  
Old 2017-09-17, 11:25   #40
swellman
 
swellman's Avatar
 
Jun 2012

3,203 Posts
Default

Quote:
Originally Posted by rcv View Post

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.
swellman is online now  
Old 2017-09-25, 19:46   #41
ryanp
 
ryanp's Avatar
 
Jun 2012
Boulder, CO

33110 Posts
Default

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

ryanp is offline  
Old 2017-10-12, 17:41   #42
swellman
 
swellman's Avatar
 
Jun 2012

3,203 Posts
Default 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
swellman is online now  
Old 2017-10-13, 23:36   #43
rcv
 
Dec 2011

11×13 Posts
Default

Quote:
Originally Posted by swellman View Post
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
rcv is offline  
Old 2017-10-14, 01:20   #44
swellman
 
swellman's Avatar
 
Jun 2012

3,203 Posts
Default

Quote:
Originally Posted by rcv View Post
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
swellman is online now  
 

Thread Tools


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

All times are UTC. The time now is 20:53.


Mon Oct 25 20:53:36 UTC 2021 up 94 days, 15:22, 0 users, load averages: 1.84, 2.08, 2.07

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.