RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2022 Number 12, Pages 123–129 (Mi ivm9843)

This article is cited in 3 papers

Brief communications

On a conbined primality test

Sh. T. Ishmukhametov, N. A. Antonov, B. G. Mubarakov, G. G. Rubtsova

Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia

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)$.

Keywords: Lucas primality test, the Fermat test, probabilistic primality test, deterministic primality test.

UDC: 510.1

Received: 17.11.2022
Revised: 17.11.2022
Accepted: 21.12.2022

DOI: 10.26907/0021-3446-2022-12-123-129


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2022, 66:12, 112–117


© Steklov Math. Inst. of RAS, 2025