Primality test for numbers \(M\) with a large power of 5 dividing \(M^{4}-1\). (Q1401290)

The paper uses quintic reciprocity to derive primality tests for numbers of the form \(A.5^n\pm\omega_n\), where \(0<A<5^n\), \(0<\omega_n<5^n/2\), \(\omega_n^4\equiv 1 \pmod {5^n}\). (In particular \(\omega_n=1\) satisfies the conditions.) A deterministic test is given which runs in polynomial time provided that a small prime \(p\), \(p\equiv 1\pmod 5\) can be found such that \(M\) is not a fifth power modulo \(p\). In practice such a prime is easily found by trial and error, but it is difficult to give a theoretical estimate for the worst-case complexity of finding \(p\), so the algorithm is not proven to be polynomial. As a partial remedy for this deficiency, a probabilistic algorithm which does not require \(p\) is given. This algorithm differs from the usual probabilistic algorithms, such as the Miller-Rabin-Monier algorithm in that, if it declares \(M\) prime then there is no probability of error, but there is a probability of \(1-5^{[\log A/2\log 5-n]}\) that a prime \(M\) will not be detected. The paper discusses the implementation of the tests, and notes an application to finding twin primes of the given form.