# NIST implementation of the Lucas primality test

The NIST standard FIPS 186-4 describes an implementation of the Lucas primality test in section C.3.3.

I can follow the algorithm but I am puzzled by step 6.2:

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

Where does this expression come from?

I do understand this is the step that computes $V_{2n}$ from $V_n$ and $U_n$. However, all relations I can find for Lucas sequences of any use in the binary expansion are in the form:

$V_{2n} = V_n^2 - 2Q^n$

Is there perhaps a way to go from this expression to the one used in the NIST implementation (with $Q = \frac{1-D}{2}$ and $D$ taken from the sequence $[5,-7,9,-11,\dots]$)?

• On these things FIPS 186-4 is inspired by ANSI X9.31. Therefore, I hope that Carl Pomerance, J.L. Selfridge and Samuel S. Wagstaff, Jr.'s The Pseudoprimes to $25\cdot10^9$ (in Mathematics of Computation, Volume 35, Number 151, July 1980, pages 1003-1026); and Robert Baillie and Samuel S. Wagstaff, Jr.'s Lucas Pseudoprimes (in Mathematics of Computation, Volume 35, Number 152, October 1980, pages 1391-1417) can help; they describe and give the list of pseudoprimes of the test ANSI X9.31 wanted. – fgrieu Nov 5 '14 at 6:30

$2V_{r+s} = V_rV_s+DU_rU_s$
Which is trivial to demonstrate, given that $D=(\alpha - \beta)^2$.