A primality test for 4Kp^n-1 numbers
Classical Lucasian type primality tests provide primality criteria for an integer \(N\) written in a specific form and based on the use of a recursive sequence. The initial value, \(S_0\), of the recursion usually depends on the specific parameter values used to represent \(N\). Motivated by this dependence of \(S_0\) on the specific \(N\), the authors provide an alternative in which the necessity is dropped in order to obtain a laxer sufficient primality condition independent of any parameters of \(N\) in a given parametrised set of integers. The authors present in Corollary 1 a Lucasian type primality test for numbers written in the form \(N=4 K p^n - 1\), in which \(p\) is an odd prime, \(n\geq 1\) and \(K\) an odd integer with \(4K \leq p^n\). Moreover, in Corollary 2 and setting \(p=2\), a Gaussian analogue to the classical Lucas-Lehmer-Riesel test is presented. In Section 4 the computational complexity of their proposed algorithm is discussed. Finally, in Section 5 the algorithm is compared to other methods and the probability with which a prime is correctly certified by the algorithm is discussed as well. It is noted that similar results have been obtained by different authors [E. L. Roettger et al., Des. Codes Cryptography 77, No. 2-3, 515--539 (2015; Zbl 1364.11161)], but that the presentation of the results is novel and original.
- Testing numbers of the form for primality
- scientific article; zbMATH DE number 1995935
- Four primality testing algorithms
- A generalised Lucasian primality test
- Effective Primality Tests for Some Integers of the Forms A5 n - 1 and A7 n - 1
- A new probabilistic primality test
- scientific article; zbMATH DE number 4093551
- Primality testing: variations on a theme of Lucas
- Some primality conditions for N=2p^n -1
- scientific article; zbMATH DE number 1164034
- A note on primality tests for \(N=h\cdot 2^ n-1\)
- A primality test for \(Kp^{n}+1\) numbers
- Biquadratic reciprocity and a Lucasian primality test
- Cubic reciprocity and generalised Lucas-Lehmer tests for primality of 𝐴.3ⁿ±1
- Explicit primality criteria for (p-1)p^n-1
- Explicit primality criteria for h 2ⁿ 1
- Fast multiplication of large numbers
- Fermat test with Gaussian base and Gaussian pseudoprimes.
- scientific article; zbMATH DE number 1131675 (Why is no real title available?)
- scientific article; zbMATH DE number 2154273 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- Lucas's criterion for the primality of numbers of the form \(N = h2^ n - 1\)
- Lucasian Criteria for the Primality of = h ⋅2 n - 1
- Primality test for numbers of the form \(A p^n + w_n\)
- Primality tests for numbers of the form k 2ᵐ 1
- Some primality tests that eluded Lucas
- Some Prime Numbers of the Forms 2A3 n + 1 and 2A3 n - 1
- Testing numbers of the form N = 2kpm − 1 for primality
- The primality of certain integers of the form 2A r^n - 1
- Generalized Lucas-Lehmer tests using Pell conics
- Testing numbers of the form for primality
- scientific article; zbMATH DE number 1031006 (Why is no real title available?)
- scientific article; zbMATH DE number 1512695 (Why is no real title available?)
- scientific article; zbMATH DE number 7626419 (Why is no real title available?)
- Combinatorial primality test
- Testing numbers of the form N = 2kpm − 1 for primality
- A primality test for \(Kp^{n}+1\) numbers
This page was built for publication: A primality test for \(4Kp^n-1\) numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2287882)
