Pascal's OPN roadblock files

[lavalamp]

I was going to edit the wiki to put the case for degree 12 -> degree 6 coefficients as well, (and perhaps degree 16 -> degree 8 also), but I don't have an account.

For people that don't care about the method, or just need a quick reference for the coefficients that would be ideal.

Perhaps someone with an account could add them? *hint hint*

Also, that code is very slick axn, I would vote for adding that too.

[Dubslow]

In [4]: halve_degree([1,1,1,1,1,1,1], verbose=True)
[-19, 1, -14, 1, -5, 1, 0]
[-19, -9, -14, -4, -5, 0, 0]
[11, -9, 6, -4, 0, 0, 0]
[11, 3, 6, 0, 0, 0, 0]
[-1, 3, 0, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0]
Out[4]: [-1, 3, 6, -4, -5, 1, 1]

In [5]: halve_degree([1,1,1,1,1,1,1,1], verbose=True)
[1, -34, 1, -20, 1, -6, 1, 0]
[-19, -34, -14, -20, -5, -6, 0, 0]
[-19, 26, -14, 10, -5, 0, 0, 0]
[11, 26, 6, 10, 0, 0, 0, 0]
[11, -4, 6, 0, 0, 0, 0, 0]
[-1, -4, 0, 0, 0, 0, 0, 0]
[-1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0]
Out[5]: [-1, -4, 6, 10, -5, -6, 1, 1]

In [6]: halve_degree([1,1,1,1,1], verbose=True)
[-5, 1, -3, 1, 0]
[-5, -2, -3, 0, 0]
[1, -2, 0, 0, 0]
[1, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
Out[6]: [1, -2, -3, 1, 1]

IOW, sum through the 12th power can be halved into x^6 + x^5 - 5x^4 - 4x^3 + 6x^2 +3x - 1;

through the 14th power can be halved as x^7 + x^6 - 6x^5 -5x^4 + 10x^3 + 6x^2 - 4x - 1;

through the 8th power can be halved as x^4 + x^3 - 3x^2 - 2x + 1

and oh what the hell, here's how the (x^17-1)/(x-1) can be halved to degree 8:

halve_degree([1,1,1,1,1,1,1,1,1], verbose=True)
[-69, 1, -55, 1, -27, 1, -7, 1, 0]
[-69, -34, -55, -20, -27, -6, -7, 0, 0]
[71, -34, 50, -20, 15, -6, 0, 0, 0]
[71, 26, 50, 10, 15, 0, 0, 0, 0]
[-19, 26, -10, 10, 0, 0, 0, 0, 0]
[-19, -4, -10, 0, 0, 0, 0, 0, 0]
[1, -4, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0]
Out[7]: [1, -4, -10, 10, 15, -6, -7, 1, 1]

[lavalamp]

Originally Posted by Dubslow

through the 14th power can be halved as x^7 + x^6 - 6x^5 -5x^4 + 10x^3 + 6x^2 - 4x - 1;

through the 8th power can be halved as x^4 + x^3 - 3x^2 - 2x + 1;

But we only care about prime powers (or multiples of prime powers), as otherwise there are algebraic factors that can be taken out first.

Instead of taking (p^9-1)/(p-1) from a degree 8 to a degree 4. Notice that first it can be factorised further:



Now you have a lovely degree 6 poly for the largest factor, and you'll have to suck it up and run ECM and/or GNFS on the smaller factors. But that's fine since if the large factor is a tractable size for SNFS, even at 300 digits, then the smaller factors should only be 50 and 100 digits or so.

For the case of (p^15-1), right off the bat there are 4 algebraic factors:


The third factor has an obvious degree 4 polynomial, and the fourth factor ALSO has a degree 4 polynomial, as it is still a symmetric degree 8:


Possibly also this degree 5 poly would work for the fourth factor:


This seems like a good argument to include axn's code on the wiki, a very simple 2 liner that can allow users to easily find polynomials like this for some algebraic factors. I know that previously I was unaware of the substpol function, and I will definitely be using it in the future.

But I'd say the only polynomials worth listing the coefficients for are these:




And even then, use of the degree 8 should be strongly discouraged.

[RichD]

Originally Posted by Dubslow

through the 14th power can be halved as x^7 + x^6 - 6x^5 -5x^4 + 10x^3 + 6x^2 - 4x - 1;

through the 8th power can be halved as x^4 + x^3 - 3x^2 - 2x + 1

Those may be interesting calculations but is the resulting polynomial still reducible as mentioned here? Perhaps someone with Pari can answer that.

P.S. I don't mean to bash Bill, I want to add this and the reference to a knowledge base for everyone.

[Dubslow]

Originally Posted by lavalamp

But we only care about prime powers (or multiples of prime powers), as otherwise there are algebraic factors that can be taken out first.

Originally Posted by RichD

Those may be interesting calculations but is the resulting polynomial still reducible as mentioned here? Perhaps someone with Pari can answer that.

P.S. I don't mean to bash Bill, I want to add this and the reference to a knowledge base for everyone.

I think it's quite clear just how little thought went into my post. Obviously I have approximately zero experience with producing low-power SNFS polys.

[LaurV]

Now, I like how this discussion progressed! Thanks everybody.
I remember my math teacher explaining something similar to us in high school, but that was in the former century, it went into one ear and went out through the other ear... therefore, before reading it from the provided links, I was somehow confused about what you all are talking there...

The last pieces of code and explanations really made a lot of light (and sense).
(BTW, axn, very nice piece of code )

[hyramgraff]

I'm continuing my attempt to run ECM with B1=50e3 (25 digits) on all numbers in the t2100 file. With six cores devoted to this I'm still finding about ten factors per day. Today that included this full factorization:

C491 = P34 * PRP491 http://factordb.com/index.php?id=1100000000685455168


By the way, is there a good open source program for creating a certificate of primality? I know about Primo but I don't want to install it on my machine because it's not open source.

[wblipp]

Originally Posted by lavalamp

Suppose I wish to factor a number p^5-1, clearly there is the algebraic factor to take out, which leaves N = (p^5-1)/(p-1).

Now there is an easy degree 4 poly that can be used: , with root .

For large p though, such that N is in the 200+ digit range, a degree 6 polynomial is preferred.

I'm petty sure this is a lousy sixth degree polynomial:

It should be roughly like factoring p^6, with a largish coefficient "-p" in the polynomial. Anybody have ideas about remedying these faults?

[axn]

Originally Posted by wblipp

I'm petty sure this is a lousy sixth degree polynomial:

It should be roughly like factoring p^6, with a largish coefficient "-p" in the polynomial. Anybody have ideas about remedying these faults?

What would the rational side, the g(x), look like in this case? The whole point of increasing degree of algebraic side is to reduce coefficient on the rational side (so that the two sides become more balanced).

[henryzz]

Originally Posted by hyramgraff

I'm continuing my attempt to run ECM with B1=50e3 (25 digits) on all numbers in the t2100 file. With six cores devoted to this I'm still finding about ten factors per day. Today that included this full factorization:

C491 = P34 * PRP491 http://factordb.com/index.php?id=1100000000685455168


By the way, is there a good open source program for creating a certificate of primality? I know about Primo but I don't want to install it on my machine because it's not open source.

If factors/day is your aim then you should probably run curves at a higher level. It will take longer to complete 25 digits but you will find a lot more factors >25 digits and there will be less to do for 30 digits.

[lavalamp]

Originally Posted by axn

What would the rational side, the g(x), look like in this case? The whole point of increasing degree of algebraic side is to reduce coefficient on the rational side (so that the two sides become more balanced).

Well I suppose the easy way to get a degree 6 for a number of the form p^5-1 would be to multiply through by p: p^6 - p, then your polynomials become:
f(x) = x^6 - p
g(x) = x - p

Degree 6 polynomial as desired, but alas it drastically increases the difficulty. If (p5 - 1)/(p - 1) is ~200 digits, then p^6 - p is ~300 digits.

SNFS 200 is readily approachable while SNFS 300 is not, at least not for me.

This is why I was trying to get a degree 6 polynomial without increasing the difficulty, even if that might come at the expense of larger coefficients on the rational side.