Current status

[akruppa]

Originally Posted by bdodson

I'm not sure what the person you're asking is thinking about, but
if I recall correctly, Peter was able to get degree 5 from a factor
of 11, and degree 6 from 13.

Hi Bruce,

how are you? It was really nice to meet you at ANTS!

The problem with 2,1586L and 2,1606M is that they are Aurifeullian factors. For plain a^(11k)±1 numbers it is easy to get degree 5 (and for 13k degree 6), but afaik noone discovered a way to do the same for Aurifeullians with index divisible by 11 or 13 yet.

Alex

Edit: Paul beat me to it...

[R.D. Silverman]

Originally Posted by frmky

Is a 196-digit quartic really THAT bad? Even with a good poly like x^4+x^3+x^2+x+1? I realize that a quartic is not optimal, but with good choice of factor base sizes, I didn't think it'd be too bad considering I've done a 185-digit with a quintic on a single computer with GGNFS.



Likewise, would a sextic be too difficult for 2,1586L? 2 x^6 - 2 x^3 + 1 with difficulty of 239 digits would rival the effort for M811, but would the sextic make it much harder than the quintic used then?

Greg

Yes, a quartic on numbers that size is really bad. I did 2,815- and 2,820+
with quartics and they were quite slow.

A quintic is sub-optimal for numbers bigger than about 220 digits.

[frmky]

Originally Posted by R.D. Silverman

A quintic is sub-optimal for numbers bigger than about 220 digits.

So 2 x^6 - 2 x^3 + 1 would be perfect for 2,1586L with difficulty of 239 digits. It should be easier than M811, but not by much. It'd still be a HUGE effort.

Greg

Edit: Likewise, x^6 + 2 x^3 + 2 at 243 digits for 2,1606M would be about the same difficulty.

[R.D. Silverman]

Originally Posted by frmky

So 2 x^6 - 2 x^3 + 1 would be perfect for 2,1586L with difficulty of 239 digits. It should be easier than M811, but not by much. It'd still be a HUGE effort.

Greg

Uhh..... Wacky did ask for relatively easy numbers......

Also, why would NFSNET do 2,1586L ahead of (say) 2,772+, 2,779+ etc?
The latter are first holes... Not only is 1586L harder, but it isn't currently
wanted.....

Finally, the cofactor for 2,1586L is only 156 digits; It would be easier with
GNFS than SNFS.

[bdodson]

Originally Posted by xilman

Hi Bruce, please let us know how to get a reciprocal polynomial for those two numbers so that we can then use the degree-halving trick to reduce them to a quintic and a sextic.

I can't yet see how to do it. Perhaps I need to think about it more.
Paul

Not on my account, please. I got distracted by the "why would [one]
think" part of Bob's post, and hadn't meant to suggest that the trick
in question could be applied and/or modified to work for Aurifeullians
(spelling courtesy of Alex's post). On content, Bob wins on this one:
so far as I know, neither 2,1586L nor 2,1606M have polyn making use
of the factors of 13, resp 11; and I know for a fact (from cleaning-
up (some of) the last of the difficulty < 190's, including 2LM's) that
degree 4 makes a very big difference.

I'd much rather you consider my endorsement (pm to Richard, Paul)
of one of Bob's earlier suggestions - 5,313- C210 difficulty 218.78. That's
maybe from 125*x^5 with root m = 5^62, and log[10]=218.777? Seems
to be the only c2xx from the first five holes with difficulty under 227
(for 6,292+ C225 and 7.269- C224), but with larger cofactor than the
first holes, base-5. For base-2, Peter's program lists 2,832+ as easier
than 2,772+ but neither is exactly easy (by current NFSNET standards?),
with difficulty above 230.

ECM testing to t50 on the last Cunningham under C211 will finish in a
few minutes (except for the last 14 c16x's, keeping the P3 cluster busy
on the last 500 curves, b1=44M). Checking first five holes shows maxmem
working well out to c246, no timing drop-off from c174, but there seems
to be a step1 break somewhere between 246 and 260 (on the positive
side, 800-bits is well under 246, somewhere in c240). The Opteron timing
jumps from 2801 sec (for 11,239- c246) to 3154 sec (for 12,241- c260)
in step1; and just a nudge up in step2, from 1033 sec to 1127 sec. So
450 sec total. Almost unchanged between c174 and c246 (with maxmem
850M to keep two cpu behaving excellently while sharing 2Gb/node).

By contrast (at the risk of drifting off topic), ntt drops from dF=131072,
k=12 at c260 to dF=65536, k=49 at c320, M1061; and step 2 jumps
to 3394 sec (above step 1 at 3282 sec). And, sadly, treefile crashes
just after "computing roots of F took". Looks like a 2nd pass on
c251-c366, raising t45 to 2*t45, would most likely be done with
b1=110M (p55-optimal), rather than continuing the current b1=260M
run (decidely sub-optimal for removing t4x's, but with an epsilon or two
better chance at a p6x; and the added feature that the curves carry
forward to t60 or t65 runs, presumably needed before sieving in this range).

Bruce (NFSNET sieving contributor)

[akruppa]

The increase in step 1 time is due to the larger number of limbs (64 bit words on Opteron) needed to store the residues. Numbers up to 250 decimals fit into 13 limbs, 250 up to approx 270 digits use 14 limbs. For such relatively small numers, GMP and GMP-ECM use grammer-school multiplication, so time should increase by approx. (14/13)^2-1 = 16%. Your timing figures show an increase by 12.6%, close enough to the estimate...

That -treefile crashes is bothersome. Can you run with "-v -v -v" and send me the output?

Thanks,
Alex

[R.D. Silverman]

Originally Posted by bdodson

I'd much rather you consider my endorsement (pm to Richard, Paul)
of one of Bob's earlier suggestions - 5,313- C210 difficulty 218.78. That's
maybe from 125*x^5 with root m = 5^62, and log[10]=218.777?

5x^6 -1 with root 5^52 would be better. The linear root is smaller by
5^10 ~ 10^7, and for most points the norm on the sextic will be less than
10^7 * norm on the quintic.

The linear algebra for 2,1454L will finish next Friday. 2,1462L is a bit more
than 50% sieved.

Sparcs and PA-RISCS both suck as sievers. I finally have a full Unix
(Solaris & HP-UX) version of my lattice siever running. The main problem
is their (**&^*&%&^ slow mults and div instructions! Just finding the siever
starting points on an Ultra SPARC III (Sun-Blade 2000) takes LONGER
(by more than 50%) than running an entire special Q on my laptop!
Sieving is also 2 to 3 times slower, but this is explained in the difference
in clock rates (1.2GHz for Sparc vs 3.2 for PC)

[hlaiho]

Originally Posted by R.D. Silverman

Before you suggest "easy" numbers to do, please be certain that the
numbers are indeed easy.

12,235- was a LARGE effort. 11,235- will be a LARGE effort.

Please explain why you think that just because 1586 is divisible by 13
that the number will be easy?? Ditto for 1606/11?????
AFAIK, doing NFS with 12th and 10th degree polynomials is currently
impractical. Your claims suggest that you know something that I don't.
Teach me.

I'm sorry for my stupid expectations about 2LM numbers.

However, I will ask, how big composite is too big with GNFS for NFSNET currently.
Are the numbers 2,1574L and 2,1586L, both c156, too big?
11,251+, c151 is smaller and 2,1658L, c147 is even smaller.

Is there any good candidate that NFSNET could do?

Heikki

[xilman]

Originally Posted by hlaiho

I'm sorry for my stupid expectations about 2LM numbers.

However, I will ask, how big composite is too big with GNFS for NFSNET currently.
Are the numbers 2,1574L and 2,1586L, both c156, too big?
11,251+, c151 is smaller and 2,1658L, c147 is even smaller.

Is there any good candidate that NFSNET could do?

Heikki

Roughly speaking, around 160 digits, though that would be rather hard.

Doubtless there are many candidates under 160 digits. Take a look at the Cunningham tables and see what's available.


Paul

[xilman]

Originally Posted by R.D. Silverman

Sure! 5,311-, 5,311+ , 5,313- and 5,313+ are ~730 bits and
are the 1st/2nd holes in the base 5 tables.

I've just started looking for sieving parameters for 5,311-.C173

The polynomials are quite obviously x^6-5 and x-(5^52). The difficulty is about the same as 2,736+ which we did a while back, so the prime bounds and sieving rectangle should be very similar too.

The same parameters, with an obvious modification, will serve for 5,311+. The polynomials for 5,313- will probably be x^6-5 and (5^52)x-1, which share a root 5^(-52). The reciprocal polynomial is usually slightly better in these cases. The sieving parameters will be closely similar to 2,736+ too.


Summary: a single parameter search will give us values suitable for four factorizations.


Paul

[xilman]

Originally Posted by xilman

I've just started looking for sieving parameters for 5,311-.C173

Summary: a single parameter search will give us values suitable for four factorizations.

Looking very much like approx 20M lines, each of length 54M (so the skewness is 27/20, close to the correct value of 1.337) will do it. The factorbases run to 50M on each side with LPB=500M on each side. Circa 43M relations will be needed.

The trial sieving with these parameters hasn't finished yet. The first run, with a rectangle twice the linear dimensions, produced 90M relations which is grossly more than what's needed. Examining its output leads me to believe the rectangle given above is about right.

Yes, Bob, I'm well aware that a simple rectangle is not optimal. I've read your paper several times now.

The computations reported are purely to set the scale of the sieving parameters. I'm sieving only 1/19997 lines and the estimates of the number of relations produced is usually good only to 5-10% or so. That's easily adequate for present purposes. The computations are also good enough to let us make sensible choices for longer lines at small values of b.


Paul