I am wondering something about the strong Lucas Pseudoprime test.
Wikipedia states:
(click for larger picture)
Does the normal test (i.e. the not strong one) still need to be done, where $U_{\delta(n)} \equiv 0 \pmod n$ must still be checked? Or are these conditions for the strong done instead of this?
Also, in the article it says one of the conditions must be met. Does that mean as soon as $U_d \equiv 0 \pmod n$ or any $V_{d2^r} \equiv 0 \pmod n$ then the strong part of the test doesn't need to be checked anymore? For example as soon as the congruence holds true for one value of $r$ in $0 \leq r \lt s$ then the rest for other values of r don't need to be checked?
How is $d2^r$ normally calculated? I can think of two ways: doing it in advanced by going through all values or checking each $v_i$ to see if $i$ is of the form $d2^r$
The article explains this, the strong Lucas test implies the normal one, thus you don't have to do the normal one.
This part is the strong test. And yes, as soon as either of those conditions are satisfied for any choice of $r$, you are done and can return that it is a strong pseudoprime.
You start at $d$ and compute $V_d$. Then you repeatedly double $d$ and use $V_x$ to compute $V_{2x}$, and check after each step. See this part of the article.
You compute $n = d 2^r$ by repeatedly dividing $n$ by two until it is no longer divisible by $2$, then you've found $d$.