mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-02-27, 00:42   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

5·31·41 Posts
Default A missing identity

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.
fivemack is offline   Reply With Quote
Old 2008-03-01, 10:22   #2
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

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".

Last fiddled with by maxal on 2008-03-01 at 10:25
maxal is offline   Reply With Quote
Old 2008-03-03, 01:46   #3
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Quote:
Originally Posted by fivemack View Post
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?
maxal is offline   Reply With Quote
Old 2008-03-03, 14:11   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

5·31·41 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2008-03-04, 05:04   #5
maxal
 
maxal's Avatar
 
Feb 2005

FC16 Posts
Default

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
maxal is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bi-curvious Identity jcrombie Miscellaneous Math 51 2013-09-09 18:51
Cpu Identity mismatch only_human Software 2 2012-05-11 13:43
I had my identity stolen by '24' ewmayer Lounge 12 2010-02-04 21:26
Useful Identity? grandpascorpion Math 2 2009-11-10 20:44
Number and identity of n-th roots of 1 mod p SPWorley Math 6 2009-08-28 18:02

All times are UTC. The time now is 17:18.

Fri Sep 18 17:18:38 UTC 2020 up 8 days, 14:29, 1 user, load averages: 1.21, 1.55, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.