Fast doubling for Lucas sequences

Lucas sequences satisfyThese identities follow from the root formulas for the Lucas U-sequence and Lucas V-sequence, or from their recurrence, so they are polynomial identities valid over a commutative ring. They compute terms with doubled indices from terms with about half the index.

A division-free algorithm carries $(U_n,U_{n+1})$. Put $a=U_n$, $b=U_{n+1}$, $c=a(2b-Pa)$ and $d=b^2-Q{a}^2$. For an even target return $(c,d)$; for an odd target return $(d,Pd-Qc)$. Starting from $(U_0,U_1)=(0,1)$ and following the binary digits of the target uses $O(\log n)$ ring operations. At $(P,Q)=(1,-1)$ this is the usual Fibonacci doubling method, and it also works in modular arithmetic.