Interesting Question

R.D. Silverman · 2009-09-21, 12:11

Consider 2,980+ (currently C162)

We might do it by GNFS (C162) , or we might do it by SNFS with a quartic
(C237), or we might ignore the factor of 5 and doit it via a sextic using
the factor of 7.

A C237 with a quartic will be very slow. It is distinctly sub-optimal.
OTOH, the SNFS/GNFS ratio would be .69 -- a toss-up except for the
quartic.

The sextic would be a C253 and the SNFS/GNFS ratio would be .64,
suggesting GNFS, but perhaps not strongly so.

This might be the first Cunningham number for which we have 3 alternative
and reasonable choices for doing it. GNFS appears to be the winner,
but it is somewhat close.

Batalov · 2009-09-22, 05:29

I believe that I may have found another interesting project in a similar vein, but will write about it later in detail. In short, the choices are:
1. gnfs
2. a huge quartic
3. a very low (a giveaway hint here! the lowest current for any Cunningham composite) complexity -- but with a totally outrageous polynomial that no-one usually considers.

Ah, makes no sense beating around the bush ...I pretty much gave out the identity of this number. It is 2,2190L c163 (complexity 175 with an [I]octic[/I]).
Test sieved it today -- it's tons of fun. I think the results show that it should be done as choice #3!

Andi47 · 2009-09-22, 11:31

Quote:

Originally Posted by Batalov

It is 2,2190L c163 (complexity 175 with an [I]octic[/I]).
Test sieved it today -- it's tons of fun. I think the results show that it should be done as choice #3!

Are gnfs-lasieve4I1?e and msieve able to process octics? (sieving and postprocessing)?

R.D. Silverman · 2009-09-22, 11:55

Quote:

Originally Posted by Batalov

I believe that I may have found another interesting project in a similar vein, but will write about it later in detail. In short, the choices are:
1. gnfs
2. a huge quartic
3. a very low (a giveaway hint here! the lowest current for any Cunningham composite) complexity -- but with a totally outrageous polynomial that no-one usually considers.

Ah, makes no sense beating around the bush ...I pretty much gave out the identity of this number. It is 2,2190L c163 (complexity 175 with an [I]octic[/I]).
Test sieved it today -- it's tons of fun. I think the results show that it should be done as choice #3!

I would have thought that an octic would have much too high a degree....
One would have to use a very small sieve region.

jasonp · 2009-09-22, 17:22

Quote:

Originally Posted by Andi47

Are gnfs-lasieve4I1?e and msieve able to process octics? (sieving and postprocessing)?

The siever can handle up to degree 9 and msieve can handle degree up to 7 (Serge added a patch for degree 8 but I foolishly ignored it :)

Andi47 · 2009-09-23, 05:38

Quote:

Originally Posted by R.D. Silverman

I would have thought that an octic would have much too high a degree....
One would have to use a very small sieve region.

So - speaking of GGNFS - one would have to chose smaller lambdas?

Code:

#name: 5^323+3^323
n: 4971380243569283028414891120004230306923472384265736983215546750747114457572769792702042748259665376620561056315918403864065659680137456759402000875793430569143186242305169054280569277104043383538743
c8: 1
c7: -1
c6: -7
c5: 6
c4: 15
c3: -10
c2: -10
c1: 4
c0: 1
skew: 1 <-- any suggestion for better skew?
type: snfs
Y1: 22168378200531005859375
Y0: -363797882060023012839007714
rlim: 33554431
alim: 33554431
lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
rlambda: 2.6 <-- better 2.3 or still smaller?
alambda: 2.6 <-- better 2.3 or still smaller?

Did I get this right, that this one would be difficulty 213?

gnfs-lasieve4I14e -r 5_3_323+.poly -o test.out -f 33000000 -c 500
Warning: lowering FB_bound to 32999999.
total yield: 83, q=33000547 (4.74529 sec/rel) <-- on a busy P4. Better use 15e?

Quote:

Originally Posted by jasonp

The siever can handle up to degree 9 and msieve can handle degree up to 7 (Serge added a patch for degree 8 but I foolishly ignored it :)

Hmmmm... not yet sure if I will do the above factorization (it seems to be quite at (or beyond) the edge of home computing range - and I will do some ECM pretesting before considering SNFS), but if Batalov does his octic experiment, the patch will soon be needed.

Batalov · 2009-09-23, 06:46

I didn't say octics make sense always. Rather, almost never!
This one is unconvincing. The price to pay for the suboptimality of the octic is too high to use it over the bland sextic which is only 1/17th higher in complexity.

For the 2,2190L, however, the sextic has complexity 330 (which spells "fuggetaboutit!"), quartic (after trading off 1/3 of complexity -- note the difference vs. saving merely 1/17th) is still awful with complexity 220, but the octic is suboptimal to the other norm, yet saves another 1/5 of complexity (down to 175).

To do better than handwaving, here are the not yet optimized octic (and quartic to match). Try them, for example, with
gnfs-lasieve4I15e -f 10000000 -c 2000 -a t8.poly
gnfs-lasieve4I15e -f 10000000 -c 2000 -r t4.poly

Code:

n: 4135774020613762075941241874733050337283231502167725297846874446576670830078921006822902162501646672246299154843959725024946362810915383423304879883062336882176361
Y0: -9444732965739290427393
Y1: 68719476736
c0: 16
c1: 96
c2: -96
c3: -88
c4: 64
c5: 24
c6: -14
c7: -2
c8: 1
skew: 1.4
type: snfs
lpbr: 28
lpba: 28
mfbr: 56
mfba: 56
rlambda: 2.6
alambda: 2.6
rlim: 20000000
alim: 20000000

Code:

n: 4135774020613762075941241874733050337283231502167725297846874446576670830078921006822902162501646672246299154843959725024946362810915383423304879883062336882176361
Y0: -6129982163463555433433388108601236734474956488734408704
Y1: 1
c0: 1
c1: -2
c2: 2
c3: -4
c4: 4
skew: 1
type: snfs
lpbr: 30
lpba: 28
mfbr: 60
mfba: 56
rlambda: 2.6
alambda: 2.6
rlim: 80000000
alim: 20000000

Take into account that they will need different amount of relations; t4.poly needs to be 30/28-bit project (need ~60M relns), while t8.poly may quite work with 28-bit (and will need ~25M relations). quartic needs the -r side, octic surely, the -a side.

These tests are simplistic but I just want to demonstrate that t8.poly sieves reasonably well, and better than the quartic.

P.S. How do we get to that poly? In pari/GP use
factor(2^15*x^30-2^8*x^15+1), then transform the degree-16 cofactor via t=(2*x^2+1)/x.

Andi47 · 2009-09-23, 11:45

Quote:

Originally Posted by Batalov

I didn't say octics make sense always. Rather, almost never!
This one is unconvincing. The price to pay for the suboptimality of the octic is too high to use it over the bland sextic which is only 1/17th higher in complexity.

After I saw the yield, I almost thought that the answer to my poly would be "forget about it". I will do a little bit of test sieving on the algebraic side, just to see, how it compares to -r sieving, but I do not plan to sieve it. (I had reserved it today in the morning, but I will unreserve it when I am back home tonight.)

Quote:

For the 2,2190L, however, the sextic has complexity 330 (which spells "fuggetaboutit!"), quartic (after trading off 1/3 of complexity -- note the difference vs. saving merely 1/17th) is still awful with complexity 220, but the octic is suboptimal to the other norm, yet saves another 1/5 of complexity (down to 175).

To do better than handwaving, here are the not yet optimized octic (and quartic to match). Try them, for example, with
gnfs-lasieve4I15e -f 10000000 -c 2000 -a t8.poly
gnfs-lasieve4I15e -f 10000000 -c 2000 -r t4.poly

In your case, the octic seems to sieve quite well (tested on a C2D under WinXP 32 bit):
total yield: 2010, q=10002007 (1.42138 sec/rel)

the quartic (so far):
total yield: 417, q=10001053 (2.26493 sec/rel)

BTW: Are you considering to use the 14e siever for the octic?
total yield: 1450, q=10002007 (0.61529 sec/rel)

-- Possible. I haven't optimized any parameters, just took first ballparks off the top of my head. S.B.

Batalov · 2010-02-20, 04:39

In the spirit of the original message:
consider 5,785L c162. I expect it to be a smaller-but-wanted number very soon, after all c160-s finish.

The gnfs/snfs ratio is 0.74, which looks like snfs would win.
But because its difficulty 219 is high for a quartic, it is actually seriously handicapped; it does sieve, but approximately at a rate of an average snfs-248 (i.e. one with a good sextic poly): the Murphy E is 2.44e-13.
A gnfs poly with E > 6e-13 (and quite possibly 6.6e-13) can be found in a couple CPU days (or a GPU-day), and the gnfs will finish at least twice faster.

Its twin 5,785M will remain a fairly doable quartic with size c211 and a difficulty of its sibling.

Raman · 2010-02-20, 16:12

Did you refer to my wiki table while reserving numbers, that's why you left out 5,785L c162, along with the other GNFS candidates?

2,935- is supposed to be due today, but that Linear Algebra seems to be extending a bit. No idea what is happening inside at all. Maybe that it is possible that it could be due tomorrow as well. It has been running upon node 13, an unlucky node, since Friday, February 5, 2010, that occasionally corrupts files in the head node file system within the compute cluster only.

Batalov · 2010-02-20, 20:19

It is a borderline number, far from obvious, and that's why it is interesting.
I didn't need to look in the Wiki thing: it is not just "N*logM*fudge", you need the real polynomial and sims on it.

Another interesting (albeit trivial) fact: with a few last reported numbers,the number of remaining Cunnigham composites dropped below 500. (It is 497 now.)

2009-09-21, 12:11	#1
R.D. Silverman Nov 2003 2²×5×373 Posts	Interesting Question Consider 2,980+ (currently C162) We might do it by GNFS (C162) , or we might do it by SNFS with a quartic (C237), or we might ignore the factor of 5 and doit it via a sextic using the factor of 7. A C237 with a quartic will be very slow. It is distinctly sub-optimal. OTOH, the SNFS/GNFS ratio would be .69 -- a toss-up except for the quartic. The sextic would be a C253 and the SNFS/GNFS ratio would be .64, suggesting GNFS, but perhaps not strongly so. This might be the first Cunningham number for which we have 3 alternative and reasonable choices for doing it. GNFS appears to be the winner, but it is somewhat close.

2009-09-23, 06:46	#7
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴×593 Posts	a bit more than handwaving I *didn't* say octics make sense always. Rather, almost never! This one is unconvincing. The price to pay for the suboptimality of the octic is too high to use it over the bland sextic which is only 1/17th higher in complexity. For the 2,2190L, however, the sextic has complexity 330 (which spells "fuggetaboutit!"), quartic (after trading off 1/3 of complexity -- note the difference vs. saving merely 1/17th) is still awful with complexity 220, but the octic is suboptimal to the other norm, yet saves another 1/5 of complexity (down to 175). To do better than handwaving, here are the not yet optimized octic (and quartic to match). Try them, for example, with gnfs-lasieve4I15e -f 10000000 -c 2000 -a t8.poly gnfs-lasieve4I15e -f 10000000 -c 2000 -r t4.poly Code: n: 4135774020613762075941241874733050337283231502167725297846874446576670830078921006822902162501646672246299154843959725024946362810915383423304879883062336882176361 Y0: -9444732965739290427393 Y1: 68719476736 c0: 16 c1: 96 c2: -96 c3: -88 c4: 64 c5: 24 c6: -14 c7: -2 c8: 1 skew: 1.4 type: snfs lpbr: 28 lpba: 28 mfbr: 56 mfba: 56 rlambda: 2.6 alambda: 2.6 rlim: 20000000 alim: 20000000 Code: n: 4135774020613762075941241874733050337283231502167725297846874446576670830078921006822902162501646672246299154843959725024946362810915383423304879883062336882176361 Y0: -6129982163463555433433388108601236734474956488734408704 Y1: 1 c0: 1 c1: -2 c2: 2 c3: -4 c4: 4 skew: 1 type: snfs lpbr: 30 lpba: 28 mfbr: 60 mfba: 56 rlambda: 2.6 alambda: 2.6 rlim: 80000000 alim: 20000000 Take into account that they will need different amount of relations; t4.poly needs to be 30/28-bit project (need ~60M relns), while t8.poly may quite work with 28-bit (and will need ~25M relations). quartic needs the -r side, octic surely, the -a side. These tests are simplistic but I just want to demonstrate that t8.poly sieves reasonably well, and better than the quartic. P.S. How do we get to that poly? In pari/GP use factor(2^15x^30-2^8x^15+1), then transform the degree-16 cofactor via t=(2*x^2+1)/x.

2010-02-20, 04:39	#9
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴×593 Posts	5,785L In the spirit of the original message: consider 5,785L c162. I expect it to be a smaller-but-wanted number very soon, after all c160-s finish. The gnfs/snfs ratio is 0.74, which looks like snfs would win. But because its difficulty 219 is high for a quartic, it is actually seriously handicapped; it does sieve, but approximately at a rate of an average snfs-248 (i.e. one with a good sextic poly): the Murphy E is 2.44e-13. A gnfs poly with E > 6e-13 (and quite possibly 6.6e-13) can be found in a couple CPU days (or a GPU-day), and the gnfs will finish at least twice faster. Its twin 5,785M will remain a fairly doable quartic with size c211 and a difficulty of its sibling.

2010-02-20, 16:12	#10
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts	Did you refer to my wiki table while reserving numbers, that's why you left out 5,785L c162, along with the other GNFS candidates? 2,935- is supposed to be due today, but that Linear Algebra seems to be extending a bit. No idea what is happening inside at all. Maybe that it is possible that it could be due tomorrow as well. It has been running upon node 13, an unlucky node, since Friday, February 5, 2010, that occasionally corrupts files in the head node file system within the compute cluster only. Last fiddled with by Raman on 2010-02-20 at 16:21

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Interesting question from the arxiv	fivemack	Other Mathematical Topics	4	2014-10-11 06:46
Interesting hypothetical question.	Uncwilly	Lounge	21	2014-01-20 10:26
Interesting Question	R.D. Silverman	NFSNET Discussion	0	2007-10-11 14:54
Interesting contest...	Xyzzy	Programming	0	2004-05-20 12:52
Something Interesting	clowns789	Hardware	1	2003-12-20 12:36

2009-09-22, 05:29	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴·593 Posts	I believe that I may have found another interesting project in a similar vein, but will write about it later in detail. In short, the choices are: 1. gnfs 2. a huge quartic 3. a very low (a giveaway hint here! the lowest current for any Cunningham composite) complexity -- but with a totally outrageous polynomial that no-one usually considers. Ah, makes no sense beating around the bush ...I pretty much gave out the identity of this number. It is 2,2190L c163 (complexity 175 with an [I]octic[/I]). Test sieved it today -- it's tons of fun. I think the results show that it should be done as choice #3!

2010-02-20, 20:19	#11
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2⁴·593 Posts	It is a borderline number, far from obvious, and that's why it is interesting. I didn't need to look in the Wiki thing: it is not just "NlogMfudge", you need the real polynomial and sims on it. Another interesting (albeit trivial) fact: with a few last reported numbers,the number of remaining Cunnigham composites dropped below 500. (It is 497 now.)