One more full factorization:

C150 = P8 * P10 * P21 * P56 * P57 [url]http://factordb.com/index.php?id=1100000001085604962[/url]
(I only found the P10 and P21, factordb had the rest)

I'm really surprised that this number made it into the t2100 file while it still had a P8 factor. Could that be caused by this composite coming from a recently found P77?

Increasing SNFS polynomial degree
 

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: [TEX]f(x) = x^4 + x^3 + x^2 + x + 1[/TEX], with root [TEX]g(x) = x - p[/TEX].

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

Since f(x) is symmetric, we can therefore convert to a degree 2 poly: [TEX]f'(x) = x^2 + x - 1[/TEX], with root [TEX]g'(x) = x - M[/TEX] where [TEX]M = (p+1/p)\ mod\ N[/TEX].

Hurrah, now we have an even worse polynomial. However, is it possible to do the following?

[TEX]F(x) = x^6 + x^3 - 1\ \ G(x) = x - M[/TEX] where [TEX]M = [(p+1/p)^{(1/3)}\ mod\ N][/TEX]

A couple of minor issues:
* pari/gp is having a hard time performing the cube root, in so far as it's not, it flat out doesn't do it.
* Even if it did do it, I suspect that the root M would be close to N in size.

So I suppose I am asking 2 questions. Firstly is my reasoning so far correct with regard to turning a quartic into a sextic? Secondly can the issues be addressed, ie: is there a better root to use?

Edit: It seems pari doesn't like performing a cube root because N is not prime. This fails even for very simple cases, eg. it can tell me that Mod(2,8)^2 = Mod(4,8) no problem, but ask it sqrt(Mod(4,8)) and "sqrt: not a prime number in Fl_sqrt [modulus]: 8."

Edit 2: Is the issue that the sqrt isn't uniquely defined? As in: Mod(2,8)^2 = Mod(6,8)^2. If that is the case, then I believe ANY solution should work for the root. Assuming such solutions exist, then picking the smallest one might alleviate the issue with the root being too large. I would estimate the root should be around N^(1/3) in size, which in the case of known factors could reduce the size of the root to less than p.

Reserving [URL="http://www.factordb.com/index.php?query=%28241706781623458032550959757009339177%5E7-1%29%2F241706781623458032550959757009339176"]241706781623458032550959757009339177^7-1[/URL]

Given finding a modular square root modulo a composite is as hard as factoring I doubt a cube root will be any easier

Somewhat discouraging news. Perhaps then instead of performing a cube root mod N, is it possible to use a non-linear root for the rational side?

Might it be possible to get away with something like the following?
[TEX]G(x) = px^3 - (p^2+1)[/TEX]

I believe I've read about occasional factorisation attempts with non-linear roots, but I may be confuzzled. Regardless I don't know about the impact on sieving performance, and when I try to initiate such a factorisation I am told "could not find m" by the siever.

I didn't get that part about reducing to a second degree poly, can you elaborate? (possibly in another thread, or not).

[QUOTE=LaurV;478402]I didn't get that part about reducing to a second degree poly, can you elaborate? (possibly in another thread, or not).[/QUOTE]

You are familiar with the standard degree halving technique for cyclotomic polys?

No :redface:
But I can google, give me some time... (busy at job right now).

[QUOTE=LaurV;478402]I didn't get that part about reducing to a second degree poly, can you elaborate? (possibly in another thread, or not).[/QUOTE]

Take a look here: [URL="http://www.mersennewiki.org/index.php/SNFS_Polynomial_Selection"]SNFS Polynomial Selection[/URL], in section 4.

[QUOTE=lavalamp;478413]Take a look here: [URL="http://www.mersennewiki.org/index.php/SNFS_Polynomial_Selection"]SNFS Polynomial Selection[/URL], in section 4.[/QUOTE]

That explains it nicely, but the actual method demonstrated is painfully tedious. Instead:
[CODE]? (b^11-1)/(b-1)
%1 = b^10 + b^9 + b^8 + b^7 + b^6 + b^5 + b^4 + b^3 + b^2 + b + 1
? substpol( %/b^5, b+1/b, x)
%2 = x^5 + x^4 - 4*x^3 - 3*x^2 + 3*x + 1
[/CODE]

Or, if you're interested in the algorithm without the explanation, or don't immediately understand how the polynomial substitution done by axn works (I don't), here's the [URL="https://github.com/MersenneForum/MersenneForumAliquot/blob/4d461ab32678e783a84aaf6cef0ef0c9959a3c12/mfaliquot/numtheory.py#L863"]code[/URL] I wrote some time ago. I'm just happy it gives the same result:

[pastebin]fpavM8dE[/pastebin]

What I most like about it is that that code can print the partial results, so you can see how the subtraction-of-binomial-coefficients affects the polynomial "in real time".