Some Remarks on Primality Testing Based on Lucas Sequences
by
Siguna Mueller
University of Klagenfurt, Austria

(Pseudo)-primality tests often rely on Lucas sequences, or, equivalently, on properties of the roots r of x²-Px+Q in Z_p², when p is an odd prime.

Let D=P²-4Q. If 2^s | p - (D/p), then the expressions r^e, where e=( p-(D/p) )/2^s for t <= s can be utilized for obtaining even more stringent primality testing conditions.

We give a formula for r^e mod p in terms of P and Q and discuss some applications.

Date received: March 8, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cadx-61.