mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Cunningham Tables (https://www.mersenneforum.org/forumdisplay.php?f=51)

 Raman 2008-06-23 19:32

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.

 xilman 2008-06-23 19:58

[QUOTE=Raman;136494]7,295-

[CODE]
Tue Jun 24 00:30:50 2008 prp81 factor: 204239004182680605398190478754212368873366912490836010105265524712426411236134031
Tue Jun 24 00:30:51 2008 prp111 factor: 393263672474017252292660491631044385409360056708958704520879019006886885032467377758314801669636946200575798561
[/CODE]

One minute...
Let me mail Prof. Sam Wagstaff before posting further information about it...[/QUOTE]Nice one!

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

Paul

 Raman 2008-06-23 20:33

[quote=xilman;136497]
Nice one!
I'm glad it worked out in the end. Good luck with the next.
[/quote]

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
x[sup]10[/sup]+x[sup]5[/sup]+1 divided by x[sup]2[/sup]+x+1
which is,

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

which has SNFS difficulty of 200 digits

 frmky 2008-06-23 21:15

[QUOTE=Raman;136500]
$$x^8-x^7+x^5-x^4+x^3-x+1$$

which has SNFS difficulty of 200 digits[/QUOTE]

Yep, but make it degree 4. Not great, but the best you can do.

[TEX]x^4-x^3-4x^2+4x+1[/TEX]

[TEX]10^{25}x-(10^{50}+1)[/TEX]

Greg

 Raman 2008-06-25 13:27

[quote=frmky;136505]
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)$$
[/quote]

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

 jasonp 2008-06-25 15:09

[QUOTE=Raman;136580]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?
[/QUOTE]
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 :)

 R.D. Silverman 2008-06-26 15:02

[QUOTE=jasonp;136586]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 :)[/QUOTE]

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+

 fivemack 2008-06-26 18:08

I'm about to start 10,259+ if nobody else is interested in it.

 bsquared 2008-06-26 19:09

I'm going after 10,339-

 R.D. Silverman 2008-06-26 19:25

[QUOTE=R.D. Silverman;136655]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+[/QUOTE]

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+

 Raman 2008-07-20 13:58

[quote=frmky;136505]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
[/quote]

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

:exclaim: [SIZE=4]EMERGENCY[/SIZE]
Also that I can't enter the value of [B]m[/B] in the GGNFS
poly file too, because of the fact that
$$\division_{10^{25}}^{(10^{50}+1)}$$
is again not an integer at all

All times are UTC. The time now is 23:21.