New phi for homogeneous Cunningham numbers

[chris2be8]

I'm not worried about that particular number. I'm trying to write a script to automatically generate polys and hoped that having phi generate polys of degree 4, 5 and 6 and checking which was best would work for x^n+-1. But phi didn't generate a reasonable poly for any x^17-1 I called it with.

So is phi 0.1.3 the latest version? And have I found a bug or a feature?

Chris

[jyb]

Originally Posted by chris2be8

I'm not worried about that particular number. I'm trying to write a script to automatically generate polys and hoped that having phi generate polys of degree 4, 5 and 6 and checking which was best would work for x^n+-1. But phi didn't generate a reasonable poly for any x^17-1 I called it with.

So is phi 0.1.3 the latest version? And have I found a bug or a feature?

Chris

You've found a bug. Or rather, you've found what turns out to be a whole bunch of bugs.

When phi can't find any algebraic factors to divide out, it tries to optimize the polynomial by looking at the prime factorizations of a and b (where N = a^n - b^n), and seeing whether raising or lowering the exponents of each of these factors results in a better polynomial (according to some rather off-the-cuff metric which the comments describe as basically good enough). But in order to find these prime factorizations, it just does trial division up to a relatively low bound (10000, with no more than 15 distinct factors).

This explains why you wouldn't have run into this problem when using phi with relatively small bases. The bugs are mostly masked when the bases can be split into small(ish) factors. But in your case, a is 313616599, which is a prime much greater than 10000, so no splitting can be done. This causes phi to use a code path which has numerous bugs, most of which are basically just typos.

When I fix these bugs and try your number, I get this:

jyb% phi -deg4 17 313616599 1 52768558671518362205861309316257680653426149189122032710729071712003321614920605612513
n: 52768558671518362205861309316257680653426149189122032710729071712003321614920605612513
# 313616599^17-1^17, difficulty: 144.44, skewness: 0.01, alpha: 0.00
# cost: 6.87223e+14, est. time: 0.33 GHz days (not accurate yet!)
skew: 0.008
c4: 313616599
c0: -1
Y1: -1
Y0: 9673779037659330951530253934893601
m: 9673779037659330951530253934893601
type: snfs
jyb%

which seems to accord fairly well with your suggestion.

So how shall the fixed version be deployed? AFAIK there's no "official" repository for it, and I don't know if Alex has touched it in a long time. My own version contains some changes that I made some time ago to deal with a quirk of how phi handles certain algebraic factors (see this for details). Should I just post my copy here? Should I run it by Alex first? What should the new version be?

[chris2be8]

I suggest you PM Alex first. If he doesn't suggest another place then post it to the "Links to factoring programs" thread (that's sticky so easier to find than this thread).

Since it's just bug fixes call it 0.1.4 (or 0.2.0 if you prefer).

And big thanks for fixing the bugs.

Chris

[chris2be8]

Can you post a copy here so I can test it?

Chris

[jyb]

Originally Posted by chris2be8

Can you post a copy here so I can test it?

Chris

Yes, but before I do here's a question that hopefully someone here can answer: how is alpha calculated for SNFS polynomials? Phi prints out the alpha value for the polynomials it generates, but in the code they are just hard-coded values that differ depending on which case it's handling (e.g. alpha = 1.292 when generating a quartic for n a multiple of 6). Where do those values come from? I have added some cases for dealing with generating a sextic when n is a multiple of 3, but I don't know what values of alpha to use.

BTW, I PM'ed Alex the other day but haven't heard anything. I guess he's no longer active in the forum (or is perhaps away at the moment, I suppose).

[chris2be8]

I don't know how alpha is calculated, but msieve does. I think ./gnfs/poly/root_score.c is where msieve calculates it so a look at that should help (I don't know C so I'm just going by a comment saying "compute Murphy's 'alpha' value").

HTH

Chris

[wombatman]

I would also appreciate an updated version of phi whenever it is possible. I use it to calculate SNFS polynomials on occasion.

[jyb]

Originally Posted by chris2be8

I don't know how alpha is calculated, but msieve does. I think ./gnfs/poly/root_score.c is where msieve calculates it so a look at that should help (I don't know C so I'm just going by a comment saying "compute Murphy's 'alpha' value").

Chris

*Sigh* Well it doesn't appear that msieve's notion of alpha accords with phi's notion of alpha at all. For example, when the exponent is a multiple of 15, phi will produce a polynomial which it claims has an alpha of 1.684. When msieve is given this same polynomial, it says the alpha is 2.444.

So I'm just blowing off the whole question. The alpha value isn't actually used for anything within phi anyway; it's just printed for fun or something.

I'm attaching my version of phi.c, which I guess we can call 0.1.4 if you want to. As mentioned previously, it has two changes:

1) You can use -deg6 with exponents that are divisible by 3, and have it actually divide out the algebraic factor. This doesn't apply to exponents divisible by 15 or 21; those are handled separately.

2) There are multiple bug fixes having to do with optimizing the polynomial based on the factorizations of the base numbers when there are no algebraic factors.

phi.0.1.4.tar.gz

[wombatman]

Much appreciated!

[chris2be8]

Now I get a sensible poly for the case I posted:

phi -deg4 17 313616599 1 52768558671518362205861309316257680653426149189122032710729071712003321614920605612513 n: 52768558671518362205861309316257680653426149189122032710729071712003321614920605612513
# 313616599^17-1^17, difficulty: 144.44, skewness: 0.01, alpha: 0.00
# cost: 6.87223e+14, est. time: 0.33 GHz days (not accurate yet!) skew: 0.008
c4: 313616599
c0: -1
Y1: -1
Y0: 9673779037659330951530253934893601
m: 9673779037659330951530253934893601
type: snfs

Many thanks.

Chris

[wreck]

Could anybody do a favor of attaching this windows executable file here?
Thanks advance.