Abstract:
In this paper we consider a hybrid primality test consisting of checking the relation $2^{n-1}\equiv 1 (\bmod\ n)$ and the Lucas primality test. Let call this procedure as $\mathrm{L}2$-test. Composite integers passing $\mathrm{L}2$-test are called $\mathrm{L}2$-pseudoprime. In this paper we develop an effective algorithm for searching $\mathrm{L}2$-pseudoprimes of form $n\equiv\pm 2(\bmod 5)$. Using it we prove that there are no $\mathrm{L}2$-pseudoprimes of the mentioned form below $B=10^{23}$ (it is the currently reached boarder and it continues to increase).
Thus, $\mathrm{L}2$-test is a deterministic test at the current interval up to $B=10^{23}$ allowing the researchers to check an odd $n\equiv\pm 2(\bmod 5)$ for primality using a polynomial two-round procedure of rate $O(\ln^3 n)$.