I've been trying to write a test function for Fibonacci pseudo-primes with large $n$. Fibonacci pseudoprimes are composite numbers such that $V\_n(P,Q) \equiv P \mod n$ for $P>0$ and $Q =\pm 1$, with $V\_n$ Lucas sequence.


As such I need to compute Lucas sequence for large $n$. They are defined by:


$U\_n(P,Q)=\frac{a^n-b^n}{a-b}$ et $V\_n(P,Q)=a^n+b^n$ with $a,b=(P\pm \sqrt{P^2-4Q})/2$


Direct computation is not possible because I need to work with integers and $\sqrt{P^2-4Q}$ may not be one.


There are also binomial formulations of the form $U\_n(P,Q)=2^{1-n}\sum\_{k=0}^{\lfloor (n-1)/2 \rfloor}\binom{n}{2k+1}P^{n-2k-1}(P^2-4Q)^k$. But computing $U\_n$ that way seems to be $O(n^2)$ which is not acceptable for me.


Are there any ways to compute $U\_n$ and $V\_n$ in $O(1)$ or $O(\log n)$ which involve only integers and not floating point ?


Thanks in advance



Computing Lucas sequence for large n
Following Emil remark, I used other relations to obtain a $O(\log n)$ algorithm:


$\begin{cases}U\_{2n}=U\_nV\_n\\
V\_{2n}=V\_n^2-2Q^n\\
U\_{2n+1} = U\_{n+1}V\_n - Q^n\\
V\_{2n+1} = V\_{n+1}V\_n -PQ^n\end{cases}$


This concluded in the following python code:



```
def lucas_sequence(p, q, n):
    if n == 0:
        return (0, 2)
    if n == 1:
        return (1, p)
    if n == 2:
        return (p, p**2 - 2* q)
    ns2 = n // 2
    un, vn = lucas_sequence(p, q, ns2)
    if n % 2 == 0:
        return (un*vn, vn**2 - 2 * (q**ns2))
    else:
        unp1, vnp1 = lucas_sequence(p, q, ns2 + 1)
        return (unp1*vn - q**ns2, vnp1*vn - p * (q**ns2))

```

