it can now be divided by 2. The numerator of is handled in the same way. (Adding n does not change the result modulo n.) Observe that, for each term that we compute in the U sequence, we compute the corresponding term in the V sequence. As we proceed, we also compute the same, corresponding powers of Q. At each stage, we reduce , , and the power of , mod n. We use the bits of the binary expansion of n to determine which terms in the U sequence to compute. 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: 12 = 1, 102 = 2, 1002 = 4, 1012 = 5, 10102 = 10, 10112 = 11, 101102 = 22, 1011002 = 44. Therefore, we compute U1, U2, U4, U5, U10, U11, U22, and U44. We also compute the same-numbered terms in the V sequence, along with Q1, Q2, Q4, Q5, Q10, Q11, Q22, and Q44. By the end of the calculation, we will have computed Un+1, Vn+1, and Qn+1, (mod n). We then check congruence () using our known value of Un+1. When D, P, and Q are chosen as described above, the first 10 Lucas pseudoprimes are (see page 1401 of ): 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, and 10877 The strong versions of the Lucas test can be implemented in a similar way. When D, P, and Q are chosen as described above, the first 10 strong Lucas pseudoprimes are: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519 To calculate a list of extra strong Lucas pseudoprimes, set . Then try P = 3, 4, 5, 6, ..., until a value of is found so that the Jacobi symbol . With this method for selecting D, P, and Q, the first 10 extra strong Lucas pseudoprimes are 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, and 72389 Checking additional congruence conditions If we have checked that congruence () is true, there are additional congruence conditions we can check that have almost no additional computational cost. If n happens to be composite, these additional conditions may help discover that fact. If n is an odd prime and , then we have the following (see equation 2 on page