Factoring Fibonacci/Lucas numbers

[geoff]

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

[akruppa]

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

[sean]

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

[hbock]

These factors I've sent 3-5 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

[geoff]

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)^2-5Fn+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

[ewmayer]

Originally Posted by hbock

These factors I've sent 3-5 months ago :
[snip]

Did you use ecm or p-1 for these? I ask because they seem unusually p-1 smooth, taken as a group.

[sean]

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=1-a;
? A=X-b*Y;
? B=X-a*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=1-a;
? A=X-b*Y;
? B=X-a*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 degree-8 polynomial which is reducible over Z. It splits into two irreducible quartics representing A(5n) and B(5n).

You can derive the degree-8 polynomial as usual, by working in Q(sqrt(5)).

[akruppa]

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

[hbock]

Originally Posted by ewmayer

Did you use ecm or p-1 for these? I ask because they seem unusually p-1 smooth, taken as a group.

All obtained by p-1 with b1/2 set to 10M/10G or 100M/100G.

[geoff]

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.

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

---8<----

\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^2-x-1$. 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^5-5\beta^rYX^4+10\beta^{2r}Y^2X^3-10\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^5-5\alpha^rYX^4+10\alpha^{2r}Y^2X^3-10\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^5-10x^3+30x^2-40x+21$.
\item $r=-1$: $f(x)=x^5+10x^3+10x^2+10x+3$.
\item $r=1$: $f(x)=x^5+10x^3-10x^2+10x-3$.
\item $r=2$: $f(x)=x^5-10x^3+30x^2-40x+21$.
\end{itemize}

In each case the linear polynomial is $g(x)=F_kx-F_{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}^{p-1}\beta^{mi}\alpha^{(p-i-1)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 x-F_{k+1}$, we obtain the following polynomials

\begin{itemize}
\item $r=0$: $f(x)=x^6-9x^5+45x^4-75x^3+105x^2-63x+17$.
\item $r=1$: $f(x)=2x^6+9x^5+30x^4-25x^3+45x^2-21x+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^4-10x^3+20x^2-15x+5\\
g(x)&=&F_mx-F_{m+1}\\
\end{eqnarray*}

When $p=7$, a similar but more protracted expansion gives a sixth degree polynomial
\begin{eqnarray*}
f(x)&=&7x^6-21x^5+70x^4-105x^3+105x^2-56x+13\\
g(x)&=&F_mx-F_{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 multiple-angle formula $$F_{km}=\sum_{i=0}^{\lfloor k/2\rfloor}(-)^{in}{k\over k-i}{k-i\choose i}5^{\lfloor k/2\rfloor-i}F_m^{k-2i}$$ hence $$F_{km}/F_m=\sum_{i=0}^{\lfloor k/2\rfloor}(-)^{in}{k\over k-i}{k-i\choose i}5^{\lfloor k/2\rfloor-i}F_m^{k-2i-1}.$$

When $p=11$ and $m$ odd this is $$3125F_m^{10}-6875F_m^8+5500F_m^6-1925F_m^4+275F_m^2-11.$$

When $p=13$ and $m$ odd this is $$15625F_m^{12}-40625F_m^{10}+40625F_m^8-19500F_m^6+4550F_m^4-455F_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}^{p-1}(-1)^i\beta^{mi}\alpha^{(p-i-1)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^6-3x^5+45x^4-85x^3+105x^2-63x+19$,
\item $r=1$: $f(x)=4x^6+3x^5+30x^4-15x^3+45x^2-27x+6$,
\item $r=2$: $f(x)=6x^6+27x^5+45x^4+15x^3+30x^2-3x+4$.
\end{itemize}

\subsection*{Acknowledgements}

This material is based on private communications with Jens Franke, Joe Leherbauer, and Peter Montgomery.


\end{document}