Status

[frmky]

The CWI suite produced a slightly smaller but denser matrix:

Matrix has 4368656 rows and 4386633 columns.
Remaining matrix weight is 326654668, density 0.0017%.
Average prime weight 74.77, average relation-set weight 74.47.

The BL was in progress, but I believe was expected to take about 6 weeks on Richard's 32-bit machine.

Greg

[bdodson]

Originally Posted by jasonp

I must say, this announcement has just made my evening. ...

Mine too! Even with the benefit of a heads-up from Richard; a
real solid improvement in the matrix step (and filtering, even).
Congratulations Greg and Jason.

With the backlog cleared, we ought to be able to go on to finish
the last of Bob's 768-bit list. Although, if I read the replies to
King's poll correctly, Bob himself was voting in favor of harder
Most Wanted base-2's. I gather that there was an intended
follow-up poll; and append the candidates below. I'd like to
see them all done; any order is good. More sieving contributors
for NFSNET would move things along more quickly.

Of course (as Greg has pointed out), someone to fill the missing
Stat's position would also help. For that matter, no reason for
NFSNET to monopolize these candidates, if someone else is
interested in steping up ...

-Bruce

You could start a new ballot ... Keep the options as
7,263-
6,284+
2,787-
2,776+
7,268+

Rest of the 768-bit list is 6,292+ 7,269- and 7,271-
presumably for after the above ones from bases 6 and 7.
The other Most wanted base-2's seem to be 2,779+
and 2,787+ with 2,776+ (above) More wanted.

[bdodson]

Originally Posted by bdodson

...I gather that there was an intended
follow-up poll; and append the candidates [above]
...
Rest of the 768-bit list is 6,292+ 7,269- and 7,271-
presumably for after the above ones from bases 6 and 7.
The other Most wanted base-2's seem to be 2,779+
and 2,787+ with 2,776+ (above) More wanted.

That was quick; 6, 284+ wins. (Unless ECMNET gets
a factor within the week.) Suppose 6,292+ would serve
as a replacement for a poll. If that one wins next, the
768-bit list would be down to four last base-7's. -bd

[R.D. Silverman]

Originally Posted by bdodson

Mine too! Even with the benefit of a heads-up from Richard; a
real solid improvement in the matrix step (and filtering, even).
Congratulations Greg and Jason.

With the backlog cleared, we ought to be able to go on to finish
the last of Bob's 768-bit list. Although, if I read the replies to
King's poll correctly, Bob himself was voting in favor of harder
Most Wanted base-2's.

The only reason for my preference was that I had promised Dick Lehmer that
I would push to finish the base 2 tables that were incomplete from the
1st edition of the book. They have been around for a long time; the
others are relative newcomers. Some time ago, NFSNET had asked for
suggestions for some "easier" numbers. I had suggested the 768-bit list as
an alternative to the harder base 2 numbers.

In fact, if NFSNET wants to make a effort to finish the base 2 tables
through 800 bits, I will put aside my work and help with the sieving.
My siever is a good deal faster than the one used by NFSNET.

There are two numbers left from 2- (one is supposedly "in progress", but
I won't hold my breath), Three from the 2+, two from the 2,4K+ and
6 from the 2LM table (one of which will finish in about 2.5 days).

[bdodson]

Originally Posted by R.D. Silverman

There are two numbers left from 2- (one is supposedly "in progress", but
I won't hold my breath), Three from the 2+, two from the 2,4K+ and
6 from the 2LM table (one of which will finish in about 2.5 days).

Substantial progress since the last time we looked; finishing 2,1582L c162
will move 2,1598M C160 up into a fifth hole; with the 12 remaining all readily
visible on Sam's page. Base-2's are fine with me; the only concern
being that if there aren't enough sievers we'd drift up towards six months
of sieving, which is a long time to wait for someone just considering
joining. -bd

[R.D. Silverman]

Originally Posted by bdodson

Substantial progress since the last time we looked; finishing 2,1582L c162
will move 2,1598M C160 up into a fifth hole; with the 12 remaining all readily
visible on Sam's page. Base-2's are fine with me; the only concern
being that if there aren't enough sievers we'd drift up towards six months
of sieving, which is a long time to wait for someone just considering
joining. -bd

Here is 2,1582L. 2,1962M is filtering. 2,1630M is sieving.
2,1630M requires a quartic. It will be quite slow.

2,1582L c162 = p70.p92

p70 = 4785290367491952770979444950472742768748481440405231269246278905154317
p92 = 94732691570793956856759198414911779734119524415635396799864941098330965560269355785101434237

[fivemack]

How do you use the additional factor p of an Aurifeuillian factor?

Taking out a factor p from x^p+1 involves the factorisation x^p+1 = (x+1)(x^{p-1}-x^{p+2}...\pm 1); the Aurifeuillian factors are from 4x^4+1=(2x^2+1)^2-(2x)^2 = (2x^2-2x+1) (2x^2+2x+1); but I don't see how those forms fit together so you can do both.

What was the polynomial for 2,1582L or 2,1962M?

[fivemack]

Ah, I've figured this out.

Say x=28M+14.

factor(2^14*x^28+1) is

[2*x^2 - 2*x + 1 1]
[2*x^2 + 2*x + 1 1]
[64*x^12 - 64*x^11 + 32*x^10 - 16*x^8 + 16*x^7 - 8*x^6 + 8*x^5 - 4*x^4 + 2*x^2 - 2*x + 1 1]
[64*x^12 + 64*x^11 + 32*x^10 - 16*x^8 - 16*x^7 - 8*x^6 - 8*x^5 - 4*x^4 + 2*x^2 + 2*x + 1 1]

now put u=2x+1/x; x^6*(u^6+2*u^5-10*u^4-20*u^3+16*u^2+32*u+8) is one factor and
x^6*(u^6-2*u^5-10*u^4+20*u^3+16*u^2-32*u+8) the other.

So it was just a matter of picking the right substitution, as I suppose SNFS polynomial generation always is.

12k+6 gives you a quartic [4 -4 2 -2 1] natively, or you can do the substitution to turn it into a quadratic and then change X and scale to get a sextic (which must be better than a quartic at >180 digits); 20k+10 gives you an octic which turns into a quartic and is annoying at >180 digits.

Have I missed anything out?

[R.D. Silverman]

Originally Posted by fivemack

How do you use the additional factor p of an Aurifeuillian factor?

Taking out a factor p from x^p+1 involves the factorisation x^p+1 = (x+1)(x^{p-1}-x^{p+2}...\pm 1); the Aurifeuillian factors are from 4x^4+1=(2x^2+1)^2-(2x)^2 = (2x^2-2x+1) (2x^2+2x+1); but I don't see how those forms fit together so you can do both.

What was the polynomial for 2,1582L or 2,1962M?

For 1582L: x^6 + 2x^5 - 10x^4 - 20x^3 + 16x^2 + 32x + 8

For 1962M: x^6 - 12x^4 + 4x^3 + 36x^2 - 24x - 8

[R.D. Silverman]

Originally Posted by fivemack

Ah, I've figured this out.

Say x=28M+14.

factor(2^14*x^28+1) is

[2*x^2 - 2*x + 1 1]
[2*x^2 + 2*x + 1 1]
[64*x^12 - 64*x^11 + 32*x^10 - 16*x^8 + 16*x^7 - 8*x^6 + 8*x^5 - 4*x^4 + 2*x^2 - 2*x + 1 1]
[64*x^12 + 64*x^11 + 32*x^10 - 16*x^8 - 16*x^7 - 8*x^6 - 8*x^5 - 4*x^4 + 2*x^2 + 2*x + 1 1]

now put u=2x+1/x; x^6*(u^6+2*u^5-10*u^4-20*u^3+16*u^2+32*u+8) is one factor and
x^6*(u^6-2*u^5-10*u^4+20*u^3+16*u^2-32*u+8) the other.

So it was just a matter of picking the right substitution, as I suppose SNFS polynomial generation always is.

12k+6 gives you a quartic [4 -4 2 -2 1] natively, or you can do the substitution to turn it into a quadratic and then change X and scale to get a sextic (which must be better than a quartic at >180 digits); 20k+10 gives you an octic which turns into a quartic and is annoying at >180 digits.

Have I missed anything out?

You got it.

[R.D. Silverman]

Originally Posted by fivemack

Ah, I've figured this out.

Say x=28M+14.

factor(2^14*x^28+1) is

[2*x^2 - 2*x + 1 1]
[2*x^2 + 2*x + 1 1]
[64*x^12 - 64*x^11 + 32*x^10 - 16*x^8 + 16*x^7 - 8*x^6 + 8*x^5 - 4*x^4 + 2*x^2 - 2*x + 1 1]
[64*x^12 + 64*x^11 + 32*x^10 - 16*x^8 - 16*x^7 - 8*x^6 - 8*x^5 - 4*x^4 + 2*x^2 + 2*x + 1 1]

now put u=2x+1/x; x^6*(u^6+2*u^5-10*u^4-20*u^3+16*u^2+32*u+8) is one factor and
x^6*(u^6-2*u^5-10*u^4+20*u^3+16*u^2-32*u+8) the other.

So it was just a matter of picking the right substitution, as I suppose SNFS polynomial generation always is.

12k+6 gives you a quartic [4 -4 2 -2 1] natively, or you can do the substitution to turn it into a quadratic and then change X and scale to get a sextic (which must be better than a quartic at >180 digits); 20k+10 gives you an octic which turns into a quartic and is annoying at >180 digits.

Have I missed anything out?

I may have missed something. For example, for 2,1914M we get a
quartic: [4,4,2,2,1] with root 2^159 . This becomes a quadratic
x^2 + 2x - 2 with root 2^160 + 2^-159. To turn this into a sextic
we make the substitution z^6 = x^2 giving z^6 + 2z^3 - 2, but
the root is now z=(2^160 + 2^-159)^1/3. Computing a cube root
mod N is as hard as factoring N itself. How do you suggest computing this
cube root?