20050702, 12:31  #1 
Mar 2003
New Zealand
2205_{8} Posts 
Factoring Fibonacci/Lucas numbers
I started working on some Fibonacci and Lucas numbers, but it appears that the web site is not being updated. Until updates resume, if anyone has new results please post them here. Hopefully some duplicate effort can be avoided.
I am especially interested to know if anyone has factors or ECM curves to report for L1061, which the web site shows as the first Lucas composite with no known factors. My recent results: F1195 C132 = 71804675494938804861279691076607136678568021.C88 F1195 C88 = 88366942612940379801999817561712385965665841.P45 L2275A C131 = 1531398564111044612177535160017110387493214245504001.P80 L3351 C460 = 7541319903937845537033112677376039.C426 L3910 C577 = 200328710415455824095619699655235959161.C538 
20050702, 12:47  #2 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
This is a mail I sent to Blair, the factors and curves are not added to his page yet.
I've done 400 curves at B1=250k on each Aurifeullian number in the composite7000 list. Here are the factors: 12168958745445725777270344604551 521278283136499011795307411 34052532660183613548623522600804401 6838931013939558425880757891 113754927958707014614445274301 15170787390257711320489441 40616718751715102757424561 41851074848734321428275605320251 38220943215419045167763881521451 402591810673117904297560267829968061 917951666255947214632683516712601 2913249607664617861540056984461 180816592591338147449016881 55189408587690825190311533311 7149919405714946493517019995121 40616718751715102757424561 2299232512070087395219751 573494854624509164794193283791 2299232512070087395219751 573494854624509164794193283791 1257326086151208268204621 324173452097518165606884892407721 617752496594962583023436681 899147141272715944328259191 238079825693412246486975061 20910310802189611238336810657621 I didn't bother to write down which number each factor belongs to as his scripts determine this automatically. Alex 
20050703, 20:34  #3 
Aug 2004
New Zealand
2·5·23 Posts 
A couple of old GNFS results of mine, that never made it into the
last update. L1377 C133= 76191122710424216753074115935972970159085722869519 * P82 by GNFS, 17 days F1195 C132 = 71804675494938804861279691076607136678568021 (p44) * 88366942612940379801999817561712385965665841 (p44) * 103908026603291796806239314172436931852069161 (p45) by GNFS 
20050704, 07:38  #4 
Feb 2003
163 Posts 
These factors I've sent 35 months ago :
C 680 L5076 : 35 digits: 12361981471954134831367044783080327 C 781 F5703 : 29 digits: 23326974674411264210520203509 C 892 L5194 : 31 digits: 1134339758191714772407088038129 C 602 L4270 : 32 digits: 34631725176810682754063646235681 C 636 F4863 : 35 digits: 19425905088680117099800261863011093 C 652 F4585 : 35 digits: 49890514508299451017018761524637461 C 660 L4510 : 31 digits: 1388721434772031415789474299681 C 939 L5071 : 31 digits: 1033707298872207590971392874361 C 957 L5558 : 36 digits: 693217238886702803281554840124683889 C 1044 L5372 : 40 digits: 1081461236555834567916212863405233649409 C 1133 L5732 : 29 digits: 84323532094695479525500138321 C 1158 F5623 : 32 digits: 16644818669598028998134211617161 C 1227 L5923 : 33 digits: 183189763126913783023991988818101 C 769 L7230 : 31 digits: 1910026566838541732969315911201 C 717 L8885A : 31 digits: 1087740649938380680349751232051 C 723 L6489 : 31 digits: 6679589179751433376090869310039 C 764 L6324 : 27 digits: 193367247083265994382775169 C 783 L6732 : 29 digits: 28819022097286255255397729281 Last fiddled with by hbock on 20050704 at 07:38 
20050704, 19:39  #5 
Mar 2003
New Zealand
13×89 Posts 
Website updated
The website was just updated, thank you Blair.
Is there a guide to the SNFS polynomials that can be used for these numbers? I have only mananged to work out these ones so far: L15nA/(5(Fn)^25Fn+1) = 25x^4  25x^3  10x^2 + 10x + 1, x = Fn, n odd L15nB/(5(Fn)^2+5Fn+1) = 25x^4 + 25x^3  10x^2  10x + 1, x = Fn, n odd F9n/F3n = 125x^6  150x^4 + 45x^2  3, x = Fn, n odd L9n/L3n = x^6 + 6x^4 + 9x^2 + 3, x = Ln, n odd L9n/L3n = x^6  6x^4 + 9x^2  3, x = Ln, n even L6n/L2n = x^4 + 4x^2 + 1, x = Ln, n odd L6n/L2n = x^4  4x^2 + 1, x = Ln, n even Last fiddled with by geoff on 20050704 at 19:43 
20050704, 19:43  #6  
∂^{2}ω=0
Sep 2002
República de California
2^{2}×2,939 Posts 
Quote:


20050704, 20:39  #7 
Aug 2004
New Zealand
2×5×23 Posts 
The following information was sent to me by Joe Leherbauer back when I was doing SNFS on these numbers. It includes some more examples of generating polynomials for these numbers.
8< Taking into account that F(1041) = F(3n) a,b = (1+sqrt(5))/2 n = 347 = 3k+2 k = 115 N = F(3n)/F(n) = a^(2n) + a^n * b^n + b^(2n) = a^(6k+4) + a^(3k+2) * b^(3k+2) + b^(6k+4) X = F(k+1) Y = F(k) A = a^k = X  b*Y analogous to your analysis B = b^k = X  a*Y N = a^4*A^6 + a^2*A^3*b^2*B^3 + b^4*B^6 I use GP/Pari to evaluate this in Q(sqrt(5)): ? a=quadgen(5); ? b=1a; ? A=Xb*Y; ? B=Xa*Y; ? F=a^4*A^6 + a^2*A^3*b^2*B^3 + b^4*B^6 %5 = 8*X^6 + 21*Y*X^5 + 45*Y^2*X^4 + 25*Y^3*X^3 + 30*Y^4*X^2  9*Y^5*X + 2*Y^6 f(X) = 8*X^6 + 21*X^5 + 45*X^4 + 25*X^3 + 30*X^2  9*X + 2 g(X) = F(k)*X  F(k+1) m = F(k+1)/F(k) (mod N)  Lucas numbers can just as well be expressed by F(k+1), F(k): n = 3k+2 N = L(3n)/L(n) = a^(2n)  a^n * b^n + b^(2n) = a^(6k+4)  a^(3k+2) * b^(3k+2) + b^(6k+4) ? a=quadgen(5); ? b=1a; ? A=Xb*Y; ? B=Xa*Y; ? a^4*A^6  a^2*A^3*b^2*B^3 + b^4*B^6 %5 = 6*X^6 + 27*Y*X^5 + 45*Y^2*X^4 + 15*Y^3*X^3 + 30*Y^4*X^2  3*Y^5*X + 4*Y^6 f(X) = 6*X^6 + 27*X^5 + 45*X^4 + 15*X^3 + 30*X^2  3*X + 4 g(X) = F(k)*X  F(k+1) m = F(k+1)/F(k) (mod N)  Lucas A,B with index < 2000 are also relatively easy SNFS targets. n is odd, i.e. n = 2k+1 L(5n) = L(n) * A(5n) * B(5n) A(5n) = 5*F(n)^2  5*F(n) + 1 B(5n) = 5*F(n)^2 + 5*F(n) + 1 L(5n)/L(n) = A(5n)*B(5n) can be expressed by F(k+1) and F(k). The result is a degree8 polynomial which is reducible over Z. It splits into two irreducible quartics representing A(5n) and B(5n). You can derive the degree8 polynomial as usual, by working in Q(sqrt(5)). 
20050704, 20:47  #8 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Nice. Polys for Fibonacci/Lucas numbers is something I looked at just the other day, in an old mail Joe sent me. Looks like something that could go in phi.c.
Alex 
20050704, 22:24  #9  
Feb 2003
163 Posts 
Quote:


20050802, 03:53  #10 
Mar 2003
New Zealand
2205_{8} Posts 
Can anyone help me find a SNFS polynomial for the nth Lucas or Fibonacci number where n=3k and k=1(mod 3)? From Sean's post I have the k=2(mod 3) case, and my earlier post gives the k=0(mod 3) case.
For example F1191: 1191=3*397, 397=3*132+1. Thanks. 
20050802, 21:17  #11 
Aug 2004
New Zealand
2·5·23 Posts 
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.
8< Code:
\documentclass{article} \usepackage{a4} \title{SNFS Poly} \author{Sean A. Irvine} \date{\today} \newtheorem{theorem}{Theorem} \def\mod{\mathop{\rm mod}\nolimits} \begin{document} \maketitle The number field sieve (NFS) requires two distinct irreducible polynomials, $f$ and $g$, and an integer $m$ such that $f(m)=g(m)=0(\mod N)$ where $N$ is the number to be factored. For sieving to be efficient the coefficients of $f$ and $g$ should be small and they should both have low degree. For certain numbers it is possible to use algebraic methods to select the polynomials. In what follows, methods for selecting polynomials suitable for factorization of Fibonacci and Lucas numbers are presented. \begin{theorem}\label{fab} Let $\alpha={1\over2}(1+\sqrt{5})$ and $\beta={1\over2}(1\sqrt{5})$ be the roots of $x^2x1$. Then the $n$th Fibonacci number can be expressed $$F_n={\alpha^n\beta^n\over\alpha\beta}.$$ \end{theorem} If $n$ is even, then $F_n$ easily splits as $F_{2m}=F_mL_m$ where $L_m$ is the $m$th Lucas number. Thus, in factoring Fibonacci numbers only odd $n$ need be considered. It is possible to generate the required sieving polynomials from Theorem~\ref{fab}. We commence with a construction which works for any odd $n$ not divisible by 5 but for which the resulting polynomial is not always the best choice. Later, we will exhibit better polynomials for the case where $n$ has a small prime divisor. Let $n\ge3$ and $n=5k+r$ where $r\in\{\pm1,\pm2\}$. By Theorem~\ref{fab} \begin{eqnarray*} \alpha^k\beta^k&=&F_k(\alpha\beta),\\ \alpha^r\alpha^k\beta^r\beta^k&=&F_{k+r}(\alpha\beta).\\ \end{eqnarray*} Solving for $\alpha^k$ and $\beta^k$ gives \begin{eqnarray*} \alpha^k&=&{\alpha\beta\over\alpha^r\beta^r}(F_{k+r}\beta^rF_k)\\ \beta^k&=&{\alpha\beta\over\alpha^r\beta^r}(F_{k+r}\alpha^rF_k)\\ \end{eqnarray*} Let $X=F_{k+r}$ and $Y=F_k$. Then, since $\alpha^n=\alpha^r(\alpha^k)^5$, $$\alpha^n={\alpha^r(\alpha\beta)^5\over(\alpha^r\beta^r)^5}(X^55\beta^rYX^4+10\beta^{2r}Y^2X^310\beta^{3r}Y^3X^2+5\beta^{4r}Y^4X\beta^{5r}Y^5)$$ Similarly, $$\beta^n={\beta^r(\alpha\beta)^5\over(\alpha^r\beta^r)^5}(X^55\alpha^rYX^4+10\alpha^{2r}Y^2X^310\alpha^{3r}Y^3X^2+5\alpha^{4r}Y^4X\alpha^{5r}Y^5)$$ Fixing $r$ yields the following sieving polynomials: \begin{itemize} \item $r=2$: $f(x)=x^510x^3+30x^240x+21$. \item $r=1$: $f(x)=x^5+10x^3+10x^2+10x+3$. \item $r=1$: $f(x)=x^5+10x^310x^2+10x3$. \item $r=2$: $f(x)=x^510x^3+30x^240x+21$. \end{itemize} In each case the linear polynomial is $g(x)=F_kxF_{k+r}$ and the common root is $m=F_{k+r}F_k^{1}(\mod N)$ where $N$ is the number to be factored (that is, $N=F_n/M$ where $M$ is a product of known factors of $F_n$). When $n$ has a small prime factor it is possible to get better polynomials. Suppose $n=pm$ where $p\in\{3,5,7,11,13\}$ and consider $F_{pm}/F_m$: \begin{eqnarray*} M&=&F_{pm}/F_m\\ &=&{\alpha^{pm}\beta^{pm}\over\alpha\beta}\big/{\alpha^m\beta^m\over\alpha\beta}\\ &=&{\alpha^{pm}\beta^{pm}\over\alpha^m\beta^m}\\ &=&\sum_{i=0}^{p1}\beta^{mi}\alpha^{(pi1)m}\\ \end{eqnarray*} When $p=3$ this gives $M=\alpha^{2m}+\beta^m\alpha^m+\beta^{2m}$. Writing $m=3k+r$ where $r\in\{0,1,2\}$ gives \begin{eqnarray*} M&=&\alpha^{6k+2r}+\alpha^{3k+r}\beta^{3k+r}+\beta^{6k+2r}\\ &=&\alpha^{2r}(F_{k+1}\beta F_k)^6+\alpha^r\beta^r(F_{k+1}\beta F_k)^3(F_{k+1}\alpha F_k)^3+\beta^{2r}(F_{k+1}\alpha F_k)^6\\ \end{eqnarray*} where we have used $\alpha^k=F_{k+1}\beta F_k$ and $\beta^k=F_{k+1}\alpha F_k$ from which (after some tedious expansions) the following sieving polynomial emerges $$(\alpha^{2r}+\beta^{2r}+(1)^r)F_{k+1}^6$$ $$3(2\beta\alpha^{2r}+2\alpha\beta^{2r}+(1)^r)F_{k+1}^5F_k$$ $$+15(\beta^2\alpha^{2r}+\alpha^2\beta^{2r})F_{k+1}^4F_k^2$$ $$5(4\beta^3\alpha^{2r}+4\alpha^3\beta^{2r}(1)^r)F_{k+1}^3F_k^3$$ $$+15(\beta^4\alpha^{2r}+2\alpha^4\beta^{2r}+(1)^r)F_{k+1}^2F_k^4$$ $$3(2\beta^5\alpha^{2r}+2\alpha^5\beta^{2r}+(1)^r)F_{k+1}F_k^5$$ $$+(\beta^6\alpha^{2r}+\alpha^6\beta^{2r}(1)^r)F_k^6.$$ Taking the linear polynomial as $g(x)=F_k xF_{k+1}$, we obtain the following polynomials \begin{itemize} \item $r=0$: $f(x)=x^69x^5+45x^475x^3+105x^263x+17$. \item $r=1$: $f(x)=2x^6+9x^5+30x^425x^3+45x^221x+8$. \item $r=2$: $f(x)=8x^6+21x^5+45x^4+25x^3+30x^2+9x+2$. \end{itemize} When $p=5$, $$M=\alpha^{4m}+\alpha^{3m}\beta^m+\alpha^{2m}\beta^{2m}+\alpha^m\beta^{3m}+\beta^{4m}$$ which noting $\alpha^m=F_{m+1}\beta F_m$ and $\beta^m=F_{m+1}\alpha F_m$ yields the homogeneous polynomial $$5F_{m+1}^4+10F_{m+1}^3F_m+20F_{m+1}^2F_m^2+15F_{m+1}F_m^3+5F_m^3,$$ yielding the sieving polynomials \begin{eqnarray*} f(x)&=&5x^410x^3+20x^215x+5\\ g(x)&=&F_mxF_{m+1}\\ \end{eqnarray*} When $p=7$, a similar but more protracted expansion gives a sixth degree polynomial \begin{eqnarray*} f(x)&=&7x^621x^5+70x^4105x^3+105x^256x+13\\ g(x)&=&F_mxF_{m+1}\\ \end{eqnarray*} When $p=11$ or $p=13$ a slightly different approach is used to express $F_{pm}/F_m$ as a polynomial in $F_m^2$. This is achieved by using the multipleangle formula $$F_{km}=\sum_{i=0}^{\lfloor k/2\rfloor}()^{in}{k\over ki}{ki\choose i}5^{\lfloor k/2\rfloori}F_m^{k2i}$$ hence $$F_{km}/F_m=\sum_{i=0}^{\lfloor k/2\rfloor}()^{in}{k\over ki}{ki\choose i}5^{\lfloor k/2\rfloori}F_m^{k2i1}.$$ When $p=11$ and $m$ odd this is $$3125F_m^{10}6875F_m^8+5500F_m^61925F_m^4+275F_m^211.$$ When $p=13$ and $m$ odd this is $$15625F_m^{12}40625F_m^{10}+40625F_m^819500F_m^6+4550F_m^4455F_m^2+13.$$ [what should the linear polys be?] Polynomials for Lucas numbers divisible by small primes are found obtained using the same techniques used for Fibonacci numbers. Suppose $n=pm$ where $p\in\{3,5,7,11,13\}$, then \begin{eqnarray*} M&=&L_{pm}/L_m\\ &=&{\alpha^{pm}+\beta^{pm}\over\alpha^m+\beta^m}\\ &=&\sum_{i=0}^{p1}(1)^i\beta^{mi}\alpha^{(pi1)m}\\ \end{eqnarray*} When $p=3$ this gives $M=\alpha^{2m}\alpha^m\beta^m+\beta^{2m}$. Writing $m=3k+r$, where $r\in\{0,1,2\}$ gives \begin{eqnarray*} M&=&\alpha^{6k+2r}\alpha^{3k+r}\beta^{3k+r}+\beta^{6k+2r}\\ &=&\alpha^{2r}(F_{k+1}\beta F_k)^6\alpha^r\beta^r(F_{k+1}\beta F_k)^3(F_{k+1}\alpha F_k)^3+\beta^{2r}(F_{k+1}\alpha F_k)^6\\ \end{eqnarray*} Fixing $r$ gives the following polynomials \begin{itemize} \item $r=0$: $f(x)=x^63x^5+45x^485x^3+105x^263x+19$, \item $r=1$: $f(x)=4x^6+3x^5+30x^415x^3+45x^227x+6$, \item $r=2$: $f(x)=6x^6+27x^5+45x^4+15x^3+30x^23x+4$. \end{itemize} \subsection*{Acknowledgements} This material is based on private communications with Jens Franke, Joe Leherbauer, and Peter Montgomery. \end{document} 
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 
Fibonacci and Lucas factors  Raman  Math  40  20100719 03:30 
Fibonacci numbers  Citrix  Math  27  20061120 17:18 
Another puzzle about Fibonacci numbers  c00ler  Puzzles  27  20060417 20:27 
Fibonacci Numbers  Vijay  Programming  26  20050415 19:11 