A missing identity

[fivemack]

I feel that L2185A, an Aurifeullian factor of lucas(2185) which equals 5*fib(437)^2 - 5*fib(437) + 1, ought to be an SNFS-number.

But I can't work out how to attack it. There are any number of identities writing one Fibonacci number in terms of others, but they're almost all homogeneous in terms of some pair of Fibonacci numbers - for example, fib(437) = A^3 + 3AB^2 + B^3 where A=fib(145), B=fib(146) - and so no use if I want to expand an expression containing both fib(437) and fib(437)^2.

fib(3n) = 5*fib(n)^3 + 3*fib(n), but 437 isn't a multiple of 3, and a bit of lattice reduction fails to find any expressions for fib(437) in terms of powers of fib(145) or fib(146) alone with reasonable coefficients.

[maxal]

why not simply to represent the number N=fib(437) as whatever best polynomial of degree 2 or 3 (not even referring to fibonaccity of N) and substitute it into 5*N^2 - 5*N + 1 to get its representation as a polynomial of degree 4 or 6 ?

If that does not work, please explain why and, in particular, what are the "reasonable coefficients".

[maxal]

Originally Posted by fivemack

any expressions for fib(437) in terms of powers of fib(145) or fib(146) alone with reasonable coefficients.

There is an expression in terms of powers of L(145) and L(146) (Lucas numbers):

5 * F(437)^2 = L(874) + 2 = (3*L(876) + L(870))/8 + 2
= (L(146)^6 - 6*L(146)^4 + 9*L(146)^2 - 2)*3/8
+ (L(145)^6 + 6*L(145)^4 + 9*L(145)^2 + 2)*1/8 + 2

5 * F(437) = (3*L(3*146) - L(3*145)) / 2
= (L(146)^3 - 3*L(146))*3/2 - (L(145)^3 + 3*L(145))/2

Therefore:

5*F(437)^2 - 5*F(437) + 1 = [ (3*L(146)^6 - 18*L(146)^4 - 12*L(146)^3 + 27*L(146)^2 + 36*L(146)) + (L(145)^6 + 6*L(145)^4 + 4*L(145) + 9*L(145)^2 + 12*L(145)) + 20 ] / 8

Does that work for you?

[fivemack]

The problem is that SNFS requires a homogeneous polynomial as input; so you can use a decomposition of Fib(x) as a normal polynomial in Fib(y) and use A=Fib(y), B=1, or you can decompose it as a homogeneous polynomial in A=Fib(y) and B=Fib(z).

What you can't use is a non-homogeneous polynomial in Fib(y) and Fib(z).

'reasonable coefficients' means two or three digits; constructions giving polynomials with coefficients some power of the input have most of the drawbacks of GNFS.

[maxal]

OK.
Here is a homogeneous polynomial of the degree 4 of x=L(219) and y=L(218):

5*F(437)^2 - 5*F(437) + 1
= ( y^4 - 3*x*y^3 + 9*x^2*y^2 - 7*x^3*y + 11*x^4 ) / 25

Similarly, this is a homogeneous polynomial of the degree 8 of x=L(110) and y=L(109):

5*F(437)^2 - 5*F(437) + 1
= ( 11*y^8 - 76*x*y^7 + 222*x^2*y^6 - 308*x^3*y^5 + 170*x^4*y^4 + 38*x^5*y^3 + 37*x^6*y^2 + 6*x^7*y + x^8 ) / 625