20181213, 17:27  #1 
Sep 2009
2,179 Posts 
Lucas and Fibonacci SNFS polynomials.
Hello,
How do you create SNFS polynomials for Lucas and Fibonacci numbers? And can you create one for something like (9061965*lucas(381)+13395)/569312895 (a lot of numbers like this have appeared in factordb)? Chris 
20181216, 16:50  #2 
Sep 2009
2179_{10} Posts 
After a bit more searching I thought to look at Lucas numbers factored by NFS@Home. The poly in the msieve output for L1117 is:
Code:
Wed Jan 16 20:56:40 2013 R0: 538522340430300790495419781092981030533 Wed Jan 16 20:56:40 2013 R1: 332825110087067562321196029789634457848 Wed Jan 16 20:56:40 2013 A0: 11 Wed Jan 16 20:56:40 2013 A1: 42 Wed Jan 16 20:56:40 2013 A2: 60 Wed Jan 16 20:56:40 2013 A3: 60 Wed Jan 16 20:56:40 2013 A4: 15 Wed Jan 16 20:56:40 2013 A5: 12 Wed Jan 16 20:56:40 2013 A6: 1 Wed Jan 16 20:56:40 2013 skew 1.00, size 1.179e11, alpha 2.227, combined = 7.157e13 rroots = 2 Chris 
20181216, 17:01  #3  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·4,787 Posts 
Quote:
if a and b are not very large, then you can try and multiply each A_{i} by a and then add b to A0. R1/R0 will be unchanged, c will not be helpful. Once a and b are 35 digits, this will likely be no better than a GNFS poly. 

20181216, 17:13  #4  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,787 Posts 
Quote:
One approach that you can do without checking out a lot of math, is to case 1: n is divisible by m=3 (5,7)... divide L(n/m) out and do lindep Code:
? F(n)=fibonacci(n) ? L(n)=F(n1)+F(n+1) ? N=L(381)/L(381/3); ? x=L(381\3); ? lindep([N,x^2,x,1]) [1, 1, 0, 3]~ \\ that's x^2 + 3. do similar attempts with different divisors Code:
? N=L(1117); ? x=F(1117\6+1); ? y=F(1117\6); ? lindep([N,x^6,x^5*y,x^4*y^2,x^3*y^3,x^2*y^4,x*y^5,y^6]) [1, 1, 12, 15, 60, 60, 42, 11]~ 

20181217, 13:14  #5  
Feb 2017
Nowhere
11616_{8} Posts 
Attaching PDF created from LaTex file in old post.
Quote:
:D snfspolys.pdf Last fiddled with by Dr Sardonicus on 20181217 at 13:14 

20181217, 18:01  #6  
Sep 2009
100010000011_{2} Posts 
Quote:
I've tried this, but I can't get it to work. Even in the simple case of lucas(1117)+1 with n: set to (lucas(1117)+1)/2 and the poly for lucas only changed by adding 1 to A0 it does not work. Looking at how factMsieve.pl checks polynomials: Code:
my $polyval = new Math::BigInt '0'; if ($denom && $numer) { my $subtotal = new Math::BigInt; for my $i (0..$DEGREE) { # Some perl versions throw an error if $COEFVALS{$i} does not exist. if ($COEFVALS{$i}) { $subtotal = $COEFVALS{$i} * $numer**$i * $denom**($DEGREE  $i); $polyval>badd($subtotal); } } I'm not going to chase this any further. It would be nice to be able to factor these numbers a bit faster, but not essential. Chris 

20181218, 11:26  #7  
(loop (#_fork))
Feb 2006
Cambridge, England
3×19×113 Posts 
Quote:
Code:
N=fibonacci(1116)+fibonacci(1118) u=fibonacci(1117\6) v=fibonacci(1+1117\6) lindep([N,u^6,u^5*v,u^4*v^2,u^3*v^3,u^2*v^4,u*v^5,v^6]) lindep([N+1,u^6,u^5*v,u^4*v^2,u^3*v^3,u^2*v^4,u*v^5,v^6]) Code:
? lindep([N,u^6,u^5*v,u^4*v^2,u^3*v^3,u^2*v^4,u*v^5,v^6]) %4 = [1, 11, 42, 60, 60, 15, 12, 1]~ ? lindep([N+1,u^6,u^5*v,u^4*v^2,u^3*v^3,u^2*v^4,u*v^5,v^6]) %5 = [1, 12, 39, 60, 65, 15, 9, 2]~ Last fiddled with by fivemack on 20181218 at 11:33 

20181218, 16:53  #8 
Sep 2009
2,179 Posts 
But would that be possible for something like (144*lucas(362)+10648)/40 where the value added varies? There are a lot of them so I'd need to be able to script up generating polys to gain much from it. And the multiplier might vary too.
I assume the sample code is for PARI/GP. Chris 
20181218, 17:26  #9  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
22546_{8} Posts 
Quote:
If you do factor these  more of the garbage will invariably appear in factordb. Similarly, this is how some streets are strategically broken in the middle. If the city council would open these  the traffic would get worse, not better. (London is also full of these.) 

20181219, 16:42  #10 
Sep 2009
2,179 Posts 
That's a counsel of despair. I'll keep trying to factor 7079 digit numbers in factordb.
Of course I won't complain if someone visits the spammer and "persuades" him to stop. Chris 
20181219, 17:40  #11  
(loop (#_fork))
Feb 2006
Cambridge, England
3·19·113 Posts 
Quote:
Code:
? u=fibonacci(90) %13 = 2880067194370816120 ? v=fibonacci(91) %14 = 4660046610375530309 ? lucas(a)=fibonacci(a1)+fibonacci(a+1) %15 = (a)>fibonacci(a1)+fibonacci(a+1) ? N=144*lucas(362)+10648 %16 = 648467571169220227569396863307334512167219106308005187376661919383210603806280 ? lindep([N/40,u^4,u^3*v,u^2*v^2,u*v^3,v^4]) %17 = [1, 277, 518, 223, 518, 277]~ 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Lucas and Fibonacci primes  Batalov  And now for something completely different  9  20170628 16:56 
SNFS for fibonacci(1345)  fivemack  Math  12  20141202 16:18 
Fibonacci and Lucas factors  Raman  Math  40  20100719 03:30 
SNFS polynomials for k*b^n+1  mdettweiler  Factoring  15  20100114 21:13 
Factoring Fibonacci/Lucas numbers  geoff  Factoring  13  20051223 01:59 