How to do Lucas Probabilistic Primality Test

Question

I am trying to follow the steps to the Lucas Probabilistic Primality test, given on 83 of The Federal Information Processing Standards Publication Series of the National Institute of Standards and Technology. I found this document by searching and would first like to confirm the test described in C.3.3 really is the Lucas probable prime test (also described in wikipeida)? Or is this something different? (Though the test seems common enough, I had trouble finding good reference material)

I do not understand these steps

$U_{temp} = U_{i+1}V_{i+1}mod C$

$V_{temp} = \frac{V_{i+1}^2+DU_{i+1}^2}{2} modC$

For more context:

I thought $U_{i+1}$ and $V_{i+1}$ represented 0s and 1s (binary). So what does it mean when they're written side by side like that? Somehow 'multiply' them? Or does $U_{temp}$ and $V_{temp}$ consist of two bits each? In the second line how does squaring make sense when applying it to bits?

What is meant by $K_rK_{r-1}...K_o$ is the binary expansion of $K$? Is $k_i \in$ [0, 1] or [0,1,2,3,4,5,6,7,8,9]?

Answer 1

All arithmetic is done $\!\bmod C$, so all integers $U_j$ and $V_j$ lie in be in the range $\,0\le n < C-1.\,$ Thus the expression $\,U_j V_j\bmod C\,$ means to multiply these integers then reduce the product modulo $C$.

The $K_i$ are indeed the binary digits of $C+1$. They are used analogously as in repeated squaring to decide whether to multiply or square, e.g. see the binary Horner polynomial viewpoint I describe here, and see this Wikipedia section.

Answer 2

These quantities are integers. So $U_{i+1}V_{i+1} \pmod C$ is a multiplication followed by a modular reduction.

Moreover, read the note at the end of section C.3 where it is explained how to interpret the division by 2, for implementors.

Steps 6.2, 6.3.1 and 6.3.2 contain expressions of the form A/2 mod C, where A is an integer, and C is an odd integer. If A/2 is not an integer (i.e., A is odd), then A/2 mod C may be calculated as (A+C)/2 mod C. Alternatively, A/2 mod C = A·(C+1)/2 mod C, for any integer A, without regard to A being odd or even.

This is further evidence of integer operations not bit operations. No primality test uses primitive bit operations, since prime factorization does not have a simple interpretation in terms of bits.