Discussion on Cunningham tables: Requests etc.

[xilman]

Originally Posted by R.D. Silverman

There are also some good candidates under 150 digits for GNFS. 11,218+ is
a first hole....

I'm tempted ...

Paul

[tcadigan]

Originally Posted by akruppa

I'm reworking it this weekend anyway, I'll try to add Aurifeullian factors and Fibonacci/Lucas numbers.

so did it get worked out AND get new features? I'd love to try out a new compiled version of phi

[akruppa]

Originally Posted by tcadigan

so did it get worked out AND get new features? I'd love to try out a new compiled version of phi

Nope, didn't get around to it yet. I'm still trying to make CWI's block-Lanczos work with OpenMP on quad-Opterons, but that's new terrain for me and most of what I tried didn't work.

I tried to figure out Aurifeullian factors as well (using the Cunningham book as reference) but the general form still eludes me. It'll take a few more days, but it'll get done.

Alex

[R.D. Silverman]

Originally Posted by akruppa

Nope, didn't get around to it yet. I'm still trying to make CWI's block-Lanczos work with OpenMP on quad-Opterons, but that's new terrain for me and most of what I tried didn't work.

I tried to figure out Aurifeullian factors as well (using the Cunningham book as reference) but the general form still eludes me. It'll take a few more days, but it'll get done.

Alex

I don't have the reference handy, but Richard Brent wrote a very nice
paper giving the general form and a nice algorithm for computing the
coefficients. I am certain you can find it on his web site.

Also, it isn't widely known, but the Aurefeullian factorizations also
apply to A^n +/- B^n as well.

BTW, Jens Franke just finished 6,263-.

[trilliwig]

RP Brent's paper is On computing factors of cyclotomic polynomials, Mathematics of Computation 61 (1993).

Andrey Kulsha of the XYYX project also has precomputed the Aurifeuillian coefficients for all squarefree k < 50, which should be more than enough for your purposes. is shorthand for the symmetric polynomial in a and b with the given coefficients. Obviously we require k*a*b to be a square to have the required difference of two squares.

NB: the coefficients for k=7 should be .

[akruppa]

Bob and Sam,

I started reading "Computing Aurifeullian Factors" last night and will get "On computing factors of cyclotomic polynomials" next. It certainly looks like these are exactly what I was looking for, complete with ready-to-go algorithm to compute the coefficients! Thank you very much for the references.

Alex

[alpertron]

I also used that reference to compute Aurifeuillian factorizations in my factorization applet.

[R.D. Silverman]

Originally Posted by akruppa

7400 curves at B1=44M on 3,452+. Adds 0.965715 to p50 and 0.147614 to p55.

Alex

It's nice to have a lot of horsepower.......

Might I request that you apply such an effort to the first 5 holes in each table?


I am nearly done with 2,1366M. (Another day and a half) and will then do
2,1378M (already started on 1 machine), 2,1382M and 2,1402L.

[akruppa]

Originally Posted by R.D. Silverman

It's nice to have a lot of horsepower.......

Sure is!

Originally Posted by R.D. Silverman

Might I request that you apply such an effort to the first 5 holes in each table?


I am nearly done with 2,1366M. (Another day and a half) and will then do
2,1378M (already started on 1 machine), 2,1382M and 2,1402L.

I'd like to clean out the base 3 tables to exponent 500. I've done a lot of work on these before so I'm partial to this base. I think I'll do a good round of ECM on the remaining base 3 composites as well. After that, lets see... I'm not quite sure for how long I'll be able to use the cluster. I hope to graduate next semester so if I'm not staying at the TU München after that, I'll almost certainly lose access. I probably won't be able to squeeze jobs into idle slots as much when I start studying for the remaining exams, either. But Cunningham numbers are definitely on top of the list as far as factoring candidates go, so I'll try to get some work done on these while I have access to this beast.

Alex

[xilman]

Originally Posted by R.D. Silverman

It's nice to have a lot of horsepower.......

Might I request that you apply such an effort to the first 5 holes in each table?


I am nearly done with 2,1366M. (Another day and a half) and will then do
2,1378M (already started on 1 machine), 2,1382M and 2,1402L.

Not a bad suggestion, but perhaps a better approach would be similar to that taken by NFSNET. That is, concentrate on problem of difficulty appropriate to the resources available.

We never take on very easy tasks, as those are better done by people who can manage them but can't manage much harder tasks. At the moment, that means NFSNET factor numbers with SNFS difficulty around 220 -230 digits. When/if we get a better siever (how's your lattice siever progressing BTW?) or more contributors we'll move upwards.

Only once (M811) have we taken on a task at the limits of our abilities because there are a good number of factorizations which we can do without superhuman efforts but which many other groups (such as yourself, for instance) can't reasonably do by themselves.

By ensuring that a wide range of people/collaborations can take part, the overall throughput is improved. If the people with seriously heavy metal remove everything the little guys can do, the latter lose interest and the community loses their contributions.


Paul

[R.D. Silverman]

Originally Posted by xilman

Not a bad suggestion, but perhaps a better approach would be similar to that taken by NFSNET. That is, concentrate on problem of difficulty appropriate to the resources available.

We never take on very easy tasks, as those are better done by people who can manage them but can't manage much harder tasks. At the moment, that means NFSNET factor numbers with SNFS difficulty around 220 -230 digits. When/if we get a better siever (how's your lattice siever progressing BTW?) or more contributors we'll move upwards.

Only once (M811) have we taken on a task at the limits of our abilities because there are a good number of factorizations which we can do without superhuman efforts but which many other groups (such as yourself, for instance) can't reasonably do by themselves.

By ensuring that a wide range of people/collaborations can take part, the overall throughput is improved. If the people with seriously heavy metal remove everything the little guys can do, the latter lose interest and the community loses their contributions.


Paul

My lattice siever is ready for you anytime you want it, but I want to
make one additional modification. It currently uses special-q from
inside the factor base. However, I estimate this will not be enough of them
for b^n > 2^700, so need to add code to use special-q that are outside
the factor base. This isn't a lot of code, but I am swamped with *real*
work at the moment (putting in 11 hour days)

I am limited by the machines I have available. This is about 10 full time
PC's. And sometimes machines are down for a whole weekend for
maintenance etc.

BTW, at one time NFSNET showed over 200 active processors. Now it
is about 90. What happened? Perhaps you can solicit more?