Primality test and primes enumeration using odd numbers indexation
DOI:
https://doi.org/10.14738/tmlai.82.8054Keywords:
odd number index, primality test, primes enumeration, Atkin sieve, composite odd numbers, wheel sieveAbstract
Odd numbers can be indexed by the map k(n)=(n-3)⁄2,n∈2N+3. We first propose a basic primality test using this index function that was first introduced in [8]. Input size of operations is reduced which improves computational time by a constant. We then apply similar techniques to Atkin’s prime-numbers sieve which uses modulus operations and finally to Pritchard’s wheel sieve, in both case yielding similar results.
References
(1) René SCHOOF (2008), Four primality testing algorithms. Algorithmic Number Theory, MSRI Publications, Volume 44. http://www.math.leidenuniv.nl/~psh/ANTproc/05rene.pdf.
(2) Manindra AGRAWAL, Neeraj KAYAL, Nitin SAXENA (2004), PRIMES is in P. Ann. of Math. (2) 160, No. 2, pp. 781-793. MR2123939 (2006a:11170). http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf.
(3) Paul PRITCHARD (1981), A sublinear additive sieve for finding prime numbers. Communications of the ACM 24(1), pp. 18-23. https://dl.acm.org/doi/pdf/10.1145/358527.358540?download=true.
(4) Paul PRITCHARD (1982), Explaining the Wheel Sieve. Acta Informatica 17, pp. 477-485. http://fuuu.be/polytech/INFOF404/Doc/Explaining%20the%20wheel%20sieve.pdf.
(5) Paul PRITCHARD (1994), Improved Incremental Prime Number Sieves. Algorithmic Number Theory Symposium. pp. 280–288. CiteSeerX 10.1.1.52.835. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.835&rep=rep1&type=pdf.
(6) Arthur ATKIN AND Daniel BERNSTEIN (2003), Prime sieves using binary quadratic forms. Mathematics of Computation Volume 73, Number 246, pp. 1023-1030. https://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf.
(7) Gabriel PAILLARD, Felipe FRANCA, Christian LAVAULT (2013), A distributed wheel sieve algorithm using Scheduling by Multiple Edge Reversal. HAL-00794389. https://hal.archives-ouvertes.fr/hal-00794389.
(8) Marc WOLF, François WOLF (2018), Representation theorem of composite odd numbers indices. SCIREA Journal of Mathematics, Vol. 3, pp. 106-117. http://article.scirea.org/pdf/11066.pdf.
(9) Marc WOLF, François WOLF, Corentin LE COZ (2018), Calculation of extended gcd by normalization. SCIREA Journal of Mathematics. Vol. 3, pp. 118-131. http://article.scirea.org/pdf/11067.pdf.
