Some Primality Tests Constructed from a Cubic Extension of the Lucas Functions
Eric L. F. Roettger, H. C. Williams · The Fibonacci Quarterly · 2021
The properties of a pair of integer valued sequences, similar to those of Lucas, are used to produce a sufficiency test for the primality of numbers N such that N2 + N + 1 is divisible by a large power of a prime p. The test will run in O((log N ) 3 ) time, provided that a small prime q (≡ 1 (mod p)) is given such that N is a cubic nonresidue of q. It is also shown how this test can be converted to one that is necessary and sufficient. A short table of prime values of such N is also provided.