リュカ擬素数
P = 1 , Q = 1 − D 4 {\textstyle P=1,Q={\frac {1-D}{4}}} とする。nにPまたはQと共通の素因子がないことを確認せよ。D,P,Qを選択するこの方法は、ジョンセルフリッジによって提案された。
(nが平方の場合、このテストは成功しない。逆に、成功した場合、nが平方でないことを示しています。従って、最初の数回の検索段階が全て失敗するまで、平方性に対するnのテストを遅らせることで、時間を節約することができる。)
与えられたD,P,Qに対して、 O ( log 2  n ) {\textstyle O(\log _{2}n)} で U n + 1 {\textstyle U_{n+1}} 及び V n + 1 {\textstyle V_{n+1}} を素早く計算する漸化式がある(Lucas sequence § Other relationsを参照せよ)。
まず、
であり、漸化式を用いて、添え字をkから2kに2倍すると、
次に、反復を用いて添え字を1ずつ増やすと、
P ⋅ U 2 k + V 2 k {\textstyle P\cdot U_{2k}+V_{2k}} が奇数の場合は、これを
で置き換える。これは偶数であるから2で割ることができる。
V 2 k + 1 {\textstyle V_{2k+1}} の分子も同様の方法で処理する(nを足しても、nを法とする結果は変わらない)。
P = 3 , Q = − 1 , D = 13 {\textstyle P=3,Q=-1,D=13} の場合、Uの数列はOEIS: A006190: U 0 = 0 , U 1 = 1 , U 2 = 3 , . . . {\textstyle U_{0}=0,U_{1}=1,U_{2}=3,...} である。
まず、n=19とする。ルジャンドル記号は
であるから、 δ ( n ) = 20 {\textstyle \delta (n)=20} ,
である。従って、19はこの組(P,Q)=(3,-1)に対するリュカ確率的素数である。この場合、19は素数なので、リュカ擬素数ではない。