|
This article is cited in 3 scientific papers (total 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.
Received: 17.11.2022 Revised: 17.11.2022 Accepted: 21.12.2022
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
Linking options:
https://www.mathnet.ru/eng/ivm9843 https://www.mathnet.ru/eng/ivm/y2022/i12/p123
|
Statistics & downloads: |
Abstract page: | 166 | Full-text PDF : | 43 | References: | 26 | First page: | 7 |
|