mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2018-12-13, 17:27   #1
chris2be8
 
chris2be8's Avatar
 
Sep 2009

36338 Posts
Default 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
chris2be8 is offline   Reply With Quote
Old 2018-12-16, 16:50   #2
chris2be8
 
chris2be8's Avatar
 
Sep 2009

3·11·59 Posts
Default

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.179e-11, alpha 2.227, combined = 7.157e-13 rroots = 2
Since both R0 and R1 are large numbers it's probably impossible to build a SNFS poly for a*lucas(n)+b (the case I was interested in).

Chris
chris2be8 is offline   Reply With Quote
Old 2018-12-16, 17:01   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217368 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
Since both R0 and R1 are large numbers it's probably impossible to build a SNFS poly for a*lucas(n)+b (the case I was interested in).
N = (a*lucas(n)+b)/c

if a and b are not very large, then you can try and multiply each Ai by a and then add b to A0. R1/R0 will be unchanged, c will not be helpful.
Once a and b are 3-5 digits, this will likely be no better than a GNFS poly.
Batalov is offline   Reply With Quote
Old 2018-12-16, 17:13   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts
Cool

Quote:
Originally Posted by chris2be8 View Post
How do you create SNFS polynomials for Lucas and Fibonacci numbers?
This can be found on the forum.
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(n-1)+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
case 2: n is prime (or composite with no small 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]~
Batalov is offline   Reply With Quote
Old 2018-12-17, 13:14   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

388710 Posts
Default

Attaching PDF created from LaTex file in old post.
Quote:
Originally Posted by sean View Post
Ah, finally found my proper notes regarding these numbers. I hope you can read LaTeX. I believe it has the answer you are looking for.
Date on first page is Dec 16, which was "today" as per file formatting. Two theorem numbers from "phantom references" did not resolve, but it's otherwise a lot easier to read than the LaTex file
:-D

snfspolys.pdf

Last fiddled with by Dr Sardonicus on 2018-12-17 at 13:14
Dr Sardonicus is offline   Reply With Quote
Old 2018-12-17, 18:01   #6
chris2be8
 
chris2be8's Avatar
 
Sep 2009

79B16 Posts
Default

Quote:
Originally Posted by Batalov View Post
N = (a*lucas(n)+b)/c

if a and b are not very large, then you can try and multiply each Ai by a and then add b to A0. R1/R0 will be unchanged, c will not be helpful.
Once a and b are 3-5 digits, this will likely be no better than a GNFS poly.
Hello,

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);
      }
    }
$denom and $numer are set to Y0 and Y1. Just adding 1 to A0 adds Y1^$DEGREE to the value so it won't match N.

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
chris2be8 is offline   Reply With Quote
Old 2018-12-18, 11:26   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23·797 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
Hello,

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.
Redo the lindep rather than editing the polynomial:

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])
gives

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]~
because the various Fibonacci identities turn out to mean that you can write 1 non-trivially as a homogeneous polynomial of even degree in powers of adjacent Fibonacci numbers.

Last fiddled with by fivemack on 2018-12-18 at 11:33
fivemack is offline   Reply With Quote
Old 2018-12-18, 16:53   #8
chris2be8
 
chris2be8's Avatar
 
Sep 2009

3×11×59 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2018-12-18, 17:26   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
But would that be possible for something like (144*lucas(362)+10648)/40 where the value added varies?
But why? Just because some spammer soiled factordb with these expressions?

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.)
Batalov is offline   Reply With Quote
Old 2018-12-19, 16:42   #10
chris2be8
 
chris2be8's Avatar
 
Sep 2009

79B16 Posts
Default

That's a counsel of despair. I'll keep trying to factor 70-79 digit numbers in factordb.

Of course I won't complain if someone visits the spammer and "persuades" him to stop.

Chris
chris2be8 is offline   Reply With Quote
Old 2018-12-19, 17:40   #11
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

23·797 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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
Yes, nicely:

Code:
? u=fibonacci(90)
%13 = 2880067194370816120
? v=fibonacci(91)
%14 = 4660046610375530309
? lucas(a)=fibonacci(a-1)+fibonacci(a+1)
%15 = (a)->fibonacci(a-1)+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]~
fivemack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas and Fibonacci primes Batalov And now for something completely different 9 2017-06-28 16:56
SNFS for fibonacci(1345) fivemack Math 12 2014-12-02 16:18
Fibonacci and Lucas factors Raman Math 40 2010-07-19 03:30
SNFS polynomials for k*b^n+-1 mdettweiler Factoring 15 2010-01-14 21:13
Factoring Fibonacci/Lucas numbers geoff Factoring 13 2005-12-23 01:59

All times are UTC. The time now is 23:22.

Wed Dec 2 23:22:42 UTC 2020 up 83 days, 20:33, 2 users, load averages: 2.20, 1.83, 1.71

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.