mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Closed Thread
 
Thread Tools
Old 2008-06-23, 19:32   #23
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

Sieving was done rapidly on Core 2 Duos at my university (NIT, Trichy) which helped me to sieve rapidly at that time.
When vacation started on 29 Apr 2008, the sieving was 86% done on this number.

After that for 20 days, I was without any resources, so sieving was suspended
On 20 May 2008, we bought a new Core 2 Quad @ 2.4 GHz at home which helped to finish the sieving rapidly.

Around June 9th the sieving was sufficient enough with about 78 million special-q sieved.

Five days ago, the linear algebra was started on my Core 2 Duo laptop @ 1.7 GHz.
Since there wasn't enough virtual memory available in normal mode, the post processing went in safe mode
with the /3GB switch.

Regarding square root, each dependency takes about two hours to solve it up,
the first dependency failed. Cleverly simultaneously I picked up the 4th dependency on the other core of my
laptop. The dependency was a good choice to give me away with the factors!

I have chosen up with the fourth dependency in the square root stage because 2,1039- gave away the factors at the 4th dependency!

Notice that 6,305- took 8 months to complete. But 7,295- which is twice as harder took only 6 months,
eventhough I was idle for sometime between. Sieving was rushed through with those Core 2 Duos at my
college.

10,312+ is half-way through sieved. It will take a couple of weeks if 30 million special-q suffice.

Last fiddled with by Raman on 2008-06-23 at 20:01 Reason: M1039 gave up factors in 4th dependency
Raman is offline  
Old 2008-06-23, 19:58   #24
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11·1,039 Posts
Default

Quote:
Originally Posted by Raman View Post
7,295-

Code:
Tue Jun 24 00:30:50 2008  prp81 factor: 204239004182680605398190478754212368873366912490836010105265524712426411236134031
Tue Jun 24 00:30:51 2008  prp111 factor: 393263672474017252292660491631044385409360056708958704520879019006886885032467377758314801669636946200575798561
One minute...
Let me mail Prof. Sam Wagstaff before posting further information about it...
Nice one!

I'm glad it worked out in the end. Good luck with the next.


Paul
xilman is offline  
Old 2008-06-23, 20:33   #25
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by xilman View Post
Nice one!
I'm glad it worked out in the end. Good luck with the next.
What is the best polynomial that I can use so for 10,375-

Since 3 and 5 both divide 375,

So, the polynomial that I currently think so of, is
x10+x5+1 divided by x2+x+1
which is,

x^8-x^7+x^5-x^4+x^3-x+1

which has SNFS difficulty of 200 digits

Last fiddled with by Raman on 2008-06-23 at 20:38
Raman is offline  
Old 2008-06-23, 21:15   #26
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

2·3·11·37 Posts
Default

Quote:
Originally Posted by Raman View Post
x^8-x^7+x^5-x^4+x^3-x+1

which has SNFS difficulty of 200 digits
Yep, but make it degree 4. Not great, but the best you can do.

x^4-x^3-4x^2+4x+1

10^{25}x-(10^{50}+1)

Greg
frmky is online now  
Old 2008-06-25, 13:27   #27
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by frmky View Post
Yep, but make it degree 4. Not great, but the best you can do.
x^4-x^3-4x^2+4x+1
10^{25}x-(10^{50}+1)
Sure? Is biquadratic (aka quartic) the best polynomial that I can use so
for 10,375-? No quintics or sextics are available for it, of
course with difficulty 200?

And eighth degree is not feasible? I think that it makes the
algebraic coefficients too larger, right?

Code:
Similarly I think that for a multiple of 11, say 7,319-
you will certainly not be using
\sum_{i=0}^{10} x^i and x-7^{29}
You would be reducing it to degree 5, right?

And for a multiple of 13, for example 6,299-
\sum_{i=0}^{12} x^i should be reduced to degree 6.

Although both of these are reduced to degree 5 and 6,
a multiple of 17 or higher cannot be reduced this way to degree 8 or higher
and should be treated up as a prime exponent, right?

For example, for 2,799- Dr. Kleinjung et al. would certainly not have
used \sum_{i=0}^{16} x^i and x-2^{47} or of course, the one
reduced up to degree 8 for it.

I think that they would only have used up so with
2x^6-1 and x-2^{133} in the Bonn University.
What about reducing the degree 14 for 10,375- (since it is a multiple of 15)
this way up to degree 7 directly?

\sum_{i=0}^{14} x^i and x-10^{25}

Last fiddled with by Raman on 2008-06-25 at 14:24 Reason: Please remove this reason feature. One always edits so to add up with more points in the post.
Raman is offline  
Old 2008-06-25, 15:09   #28
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DD916 Posts
Default

Quote:
Originally Posted by Raman View Post
Sure? Is biquadratic (aka quartic) the best polynomial that I can use so
for 10,375-? No quintics or sextics are available for it, of
course with difficulty 200?

And eighth degree is not feasible? I think that it makes the
algebraic coefficients too larger, right?
Correct, the algebraic sieve values grow too large too quickly, so the number of algebraic sieve values that are smooth enough drops too fast. The asymptotic estimates for NFS indicate that a degree-7 polynomial is feasible only for inputs that have many hundreds, if not thousands, of digits.

Most of the smallest cunningham numbers that are left have similar difficulty; if an available cunningham number is unusually small, it's probably because the NFS polynomials involved are unusually bad :)

Last fiddled with by jasonp on 2008-06-25 at 15:09
jasonp is offline  
Old 2008-06-26, 15:02   #29
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts
Default

Quote:
Originally Posted by jasonp View Post
Correct, the algebraic sieve values grow too large too quickly, so the number of algebraic sieve values that are smooth enough drops too fast. The asymptotic estimates for NFS indicate that a degree-7 polynomial is feasible only for inputs that have many hundreds, if not thousands, of digits.

Most of the smallest cunningham numbers that are left have similar difficulty; if an available cunningham number is unusually small, it's probably because the NFS polynomials involved are unusually bad :)

Actually, there are a fair number of composites left under 230 digits that
do not require a quartic.

10,312+ Raman; in progress
2,2106L quartic; yech
10,378+
7,384+
5,341- reserved
2,1694M
3,517+ I will do shortly
7,393+
2,1104+ in progress; LA 75%
10,259+
10,339-
2,1119+
2,1128+
2,1149-
2,1161+
2,1161-
10,339+
7,396+
R.D. Silverman is offline  
Old 2008-06-26, 18:08   #30
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

I'm about to start 10,259+ if nobody else is interested in it.
fivemack is offline  
Old 2008-06-26, 19:09   #31
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

5·727 Posts
Default

I'm going after 10,339-
bsquared is offline  
Old 2008-06-26, 19:25   #32
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Actually, there are a fair number of composites left under 230 digits that
do not require a quartic.

10,312+ Raman; in progress
2,2106L quartic; yech
10,378+
7,384+
5,341- reserved
2,1694M
3,517+ I will do shortly
7,393+
2,1104+ in progress; LA 75%
10,259+
10,339-
2,1119+
2,1128+
2,1149-
2,1161+
2,1161-
10,339+
7,396+
And there are also lots of them that do require a quartic:

3,565-, 580+

6,335-
6,370+

5,370+, 400+, 410+ 430+

7,335- 320+, 340+

2,860+, 865+, 925+.....

etc. etc. etc.

7,320+, 340+

3,580+
R.D. Silverman is offline  
Old 2008-07-20, 13:58   #33
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

Quote:
Originally Posted by frmky View Post
Yep, but make it degree 4. Not great, but the best you can do.
x^4-x^3-4x^2+4x+1
10^{25}x-(10^{50}+1)
Greg
So, can you please explain to me up how you derived the 4th degree
polynomial from the 8th degree one for 10,375-
x^8-x^7+x^5-x^4+x^3-x+1
x-10^{25}
I am starting to sieve for 10,375- now.
10,312+ is in Linear Algebra and will finish up
within about 12 hours or so
(Matrix has less than 20 million rows!)

EMERGENCY
Also that I can't enter the value of m in the GGNFS
poly file too, because of the fact that
\division_{10^{25}}^{(10^{50}+1)}
is again not an integer at all

Last fiddled with by Raman on 2008-07-20 at 14:46
Raman is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
7+ table garo Cunningham Tables 87 2022-03-25 19:16
5+ table garo Cunningham Tables 100 2021-01-04 22:36
6+ table garo Cunningham Tables 80 2021-01-04 22:33
5- table garo Cunningham Tables 82 2020-03-15 21:47
6- table garo Cunningham Tables 41 2016-08-04 04:24

All times are UTC. The time now is 07:35.


Wed Aug 17 07:35:53 UTC 2022 up 41 days, 2:23, 1 user, load averages: 1.44, 1.11, 1.16

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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”