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]$)?

  • 2
    $\begingroup$ 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. $\endgroup$ – fgrieu Nov 5 '14 at 6:30

Thanks to the references provided by @fgrieu I found the relevant equation in "New Primality Criteria and Factorizations of2^m+-1" by Brillhart-Lehmer-Selfridge.

In there, Equation (14) says:

$2V_{r+s} = V_rV_s+DU_rU_s$

Which is trivial to demonstrate, given that $D=(\alpha - \beta)^2$.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.