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]?
Best Answer
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.