Primality Test and an Algorithm Employed with Lucas Sequences
Research Highlights in Mathematics and Computer Science Vol. 3,
14 December 2022
,
Page 8-22
https://doi.org/10.9734/bpi/rhmcs/v3/3678B
Abstract
Lucas sequences and their applications are critical in the investigation of primality tests in number theory. Several known tests for primality of positive integer \(N\) utilising Lucas sequences based on factorization of \((N \pm 1)\) [1][2] are available. In this chapter we give a primality test for odd positive integer \(N>1\) by using the set \(L(\Delta, N)\) where \(L(\Delta, N)\) is a set of \(S(N)\) distinct pair of Lucas sequences \(\left(V_n(a, 1), U_n(a, 1)\right)\), where \(S(N)\) for \(N=p_1^{e_1} \cdot p_2^{e_2} \ldots p_s^{e_s}\) is given as \(S(N)=\operatorname{LCM}\left[\left\{p_i^{e_i-1}\left(p_i-\left(\frac{\Delta}{p_i}\right)\right)\right\}_{i=1}^s\right]\) and \(\Delta=a^2-4\) for some fixed integer \(a\).
- Lucas sequences
- Lucas addition chains
- primality testing