Primality test for numbers M with a large power of 5 dividing M^4-1.
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.
- A generalization of Lehmer's functions
- A Proof of the Lucas-Lehmer Test
- Cubic reciprocity and generalised Lucas-Lehmer tests for primality of 𝐴.3ⁿ±1
- Determination of the Primality of N by Using Factors of N 2 ± 1
- Effective primality tests for integers of the forms \(N=k3^ n+1\) and \(N=k2^ m3^ n+1\)
- Effective Primality Tests for Some Integers of the Forms A5 n - 1 and A7 n - 1
- scientific article; zbMATH DE number 3756556 (Why is no real title available?)
- scientific article; zbMATH DE number 44444 (Why is no real title available?)
- scientific article; zbMATH DE number 918133 (Why is no real title available?)
- Implementation of a new primality test
- On distinguishing prime numbers from composite numbers
- Primality Testing and Jacobi Sums
- Gaussian Mersenne and Eisenstein Mersenne primes
- Some Sufficient Conditions for Quintic Residuacity
- scientific article; zbMATH DE number 1512695 (Why is no real title available?)
- Primality test for numbers of the form \(A p^n + w_n\)
- Primality test for numbers of the form \((2p)^{2^n}+1\)
- Some primality tests that eluded Lucas
This page was built for publication: Primality test for numbers \(M\) with a large power of 5 dividing \(M^{4}-1\).
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401290)
