Abstract:
In this paper we consider a hybrid primality test consisting of checking the relation 2n−1≡1(modn) and the Lucas primality test. Let call this procedure as L2-test. Composite integers passing L2-test are called L2-pseudoprime. In this paper we develop an effective algorithm for searching L2-pseudoprimes of form n≡±2(mod5). Using it we prove that there are no L2-pseudoprimes of the mentioned form below B=1023 (it is the currently reached boarder and it continues to increase).
Thus, L2-test is a deterministic test at the current interval up to B=1023 allowing the researchers to check an odd n≡±2(mod5) for primality using a polynomial two-round procedure of rate O(ln3n).
Keywords:
Lucas primality test, the Fermat test, probabilistic primality test, deterministic primality test.
Citation:
Sh. T. Ishmukhametov, N. A. Antonov, B. G. Mubarakov, G. G. Rubtsova, “On a conbined primality test”, Izv. Vyssh. Uchebn. Zaved. Mat., 2022, no. 12, 123–129; Russian Math. (Iz. VUZ), 66:12 (2022), 112–117