Lucas sequence - how to know which terms to calculate when testing if a number is prime? To check if a number is a Lucas pseudoprime, a Lucas sequence is computed. The Lucas sequence is based on a recurrence relation, but there's a method involving inspecting the bits of the number being checked for primatliy to know which terms in the sequence to compute. How exactly does inspecting the bits work? 
Wikipedia gives the example

For example, if n+1 = 44 (= 101100 in binary), then, taking the bits
  one at a time from left to right, we obtain the sequence of indices to
  compute: $1_2$ = 1, $10_2$ = 2, $100_2$ = 4, $101_2$ = 5, $1010_2$ = 10, $1011_2$ = 11,
  $10110_2$ = 22, $101100_2$ = 44. Therefore, we compute U1, U2, U4, U5, U10,
  U11, U22, and U44

It says "taking the bits one at a time" but the example clearly is not doing that. Though the end result makes sense because the index each term is either double or one more from the previous, and we have formals to easily compute that. However in example code I've seen it appears one bit at a time is inspected. So how exactly are the bits used to decide which terms to compute? 
Are the terms known and advanced or determined while checking each individual bit? 
 A: Maybe the recursive solution to this problem is more straightforward. We have
$$
   (U_k, V_k) = \begin{cases}
       (U_{k/2} \cdot V_{k/2}, \frac12(V_{k/2}^2 + D U_{k/2}^2)) & \text{ if $k$ is even,} \\
       (\frac12(P \cdot U_{k-1} + V_{k-1}), \frac12 (D \cdot U_{k-1} + P \cdot V_{k-1}))  & \text{ if $k$ is odd.}
   \end{cases}
$$
This can be directly turned into code in the form of a recursive function.
Your ultimate goal is to computer $(U_{44}, V_{44})$; this recurrence will tell you that you need to know $(U_{22}, V_{22})$ first, and for that you need to know $(U_{11}, V_{11})$, and so forth.

This is, in disguise, exactly the logarithmic algorithm for computing the $k^{\text{th}}$ power of some kind of object $\alpha$:
$$
   \alpha^k = \begin{cases} (\alpha^{k/2})^2 & \text{ if $k$ is even,} \\ \alpha^{k-1} \cdot \alpha & \text{ if $k$ is odd.} \end{cases}
$$
We turn that into an algorithm for computing $(U_k, V_k)$ by using the relation $$\left(\frac{P + \sqrt D}{2}\right)^k = \frac{V_k + U_k \sqrt D}{2}.$$ 
Equivalently, this is a matrix power:
$$
   \begin{bmatrix}U_k \\ V_k\end{bmatrix} = \begin{bmatrix}P/2 & 1/2 \\ D/2 & P/2\end{bmatrix}^k \begin{bmatrix}1 \\ P\end{bmatrix}.
$$
Either way, we're taking the $k^{\text{th}}$ power of some fancy object, and what multiplying or squaring it does is exactly the thing in the original algorithm.
