リュカ擬素数
数列Uで計算する各記号について、数列Vで対応する記号を計算することに注意されたい。次の段階で、対応する同じQの冪乗も計算する。
各段階で、 U , V {\textstyle U,V} 及び Q {\textstyle Q} の冪を mod n {\textstyle \mod n} で計算し、小さくしておく。
nの2進展開のビットを用いて、計算する数列Uの項を決定する。例えば、n+1=44(=101100,2進数)のとき、左から右に1度に1つずつビットを取って、計算する添え字の数列を得る。
従って、 U 1 , U 2 , U 4 , U 5 , U 10 , U 11 , U 22 , U 44 {\textstyle U_{1},U_{2},U_{4},U_{5},U_{10},U_{11},U_{22},U_{44}} を計算すればよい。また、
Q 1 , Q 2 , Q 4 , Q 5 , Q 10 , Q 11 , Q 22 , Q 44 {\textstyle Q_{1},Q_{2},Q_{4},Q_{5},Q_{10},Q_{11},Q_{22},Q_{44}} と共に、数列V内の同じ番号の項を計算する。
計算の終わりまでに、 U n + 1 , V n + 1 , Q n + 1 mod n {\textstyle U_{n+1},V_{n+1},Q_{n+1}\mod n} を計算し、既知の U n + 1 {\textstyle U_{n+1}} の値を用いて、式(2)の合同性を確かめる。
ベイリーとワグスタッフは、リュカ擬素数を次のように定義している。
自然数Pと整数Qに対して、 D = P 2 − 4 Q {\textstyle D=P^{2}-4Q} とおき、 U k ( P , Q ) , V k ( P , Q ) {\textstyle U_{k}(P,Q),V_{k}(P,Q)} をそれぞれ対応するリュカ数列とする。
自然数nに対して、 ( D n ) {\textstyle \left({\frac {D}{n}}\right)} をルジャンドル記号とする。また、 δ ( n ) = n − ( D n ) {\textstyle \delta (n)=n-\left({\frac {D}{n}}\right)} とおく。
もし、nが gcd ( n , Q ) = 1 {\textstyle \gcd(n,Q)=1} なる素数である場合、次式が成り立つ。この式を(1)とする。
式(1)が成り立たないならば、nは素数でない。nが合成数ならば、式(1)は一般的には成り立たない。これらのことは、リュカ数列を素数性テストで有用にする重要な事実である。