A new probabilistic primality test (Q2202823)

In this paper, a new efficient general probabilistic primality test is presented. The main idea is as follows. Let \(n > 1\) be an odd positive integer. First, it is checked whether \(n\) can be represented as \(n = a^b\), where \(a\) and \(b\) are integers \(\ge 2\). Since \(b \le \log_2 n-1\), for every \(b\in[2, \log_2 n-1]\), it is sufficient to verify whether \(n\) is the \(b\)-th power of a positive integer. For every \(b\), such a test can be efficiently carried out. Suppose that it is not the case. Then, it is randomly chosen a nonzero residue \(r\pmod n)\) and, if \(r\) and \(n\) are not coprime, then a partial decomposition of \(n\) is obtained, and the test is completed. Note that the test can be improved for the numbers of the form \(n = 2^sr + 1\), where \(r\) is a sufficiently large odd number.