 mersenneforum.org Lucas and Fibonacci SNFS polynomials.
 Register FAQ Search Today's Posts Mark Forums Read  2018-12-13, 17:27 #1 chris2be8   Sep 2009 36338 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   2018-12-16, 16:50 #2 chris2be8   Sep 2009 3·11·59 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.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   2018-12-16, 17:01   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217368 Posts Quote:
 Originally Posted by chris2be8 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.   2018-12-16, 17:13   #4
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·4,591 Posts Quote:
 Originally Posted by chris2be8 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]~   2018-12-17, 13:14   #5
Dr Sardonicus

Feb 2017
Nowhere

388710 Posts Attaching PDF created from LaTex file in old post.
Quote:
 Originally Posted by sean 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   2018-12-17, 18:01   #6
chris2be8

Sep 2009

79B16 Posts Quote:
 Originally Posted by Batalov 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   2018-12-18, 11:26   #7
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

23·797 Posts Quote:
 Originally Posted by chris2be8 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   2018-12-18, 16:53 #8 chris2be8   Sep 2009 3×11×59 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   2018-12-18, 17:26   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×4,591 Posts Quote:
 Originally Posted by chris2be8 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.)   2018-12-19, 16:42 #10 chris2be8   Sep 2009 79B16 Posts 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   2018-12-19, 17:40   #11
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

23·797 Posts Quote:
 Originally Posted by chris2be8 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]~   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 9 2017-06-28 16:56 fivemack Math 12 2014-12-02 16:18 Raman Math 40 2010-07-19 03:30 mdettweiler Factoring 15 2010-01-14 21:13 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