Primality testing with Gaussian periods. (English) Zbl 1429.11221

The paper provides a deterministic algorithm which decides the primality of a natural number \(n\) with complexity \((\log n)^6(2+\log\log n)^c\) bits, \(c\) a real number effectively computable. This improves a previous result due to M. Agrawal et al. [Ann. Math. (2) 160, No. 2, 781–793 (2004; Zbl 1071.11070)] with complexity that look similar, but with exponent \(21/2\) instead of \(6\). Both papers follow similar ideas using a mixture of algebraic and analytic number theory tools.
The proof needs a result from additive number theory due to D. Bleichenbacher [The continuous postage problem. Unpublished manuscript (2003)], (see Theorems 3 and 4 of the present paper) and it reasons in some ring extensions of \(\mathbb{Z}/n\mathbb{Z}\) (pseudofields, finite fields if \(n\) is a prime), extensions constructed following and improving the construction of finite fields of L. M. Adleman and H. W. Lenstra jun. [“Finding irreducible polynomials over finite fields”, in: Proceedings of the eighteenth annual ACM symposium on theory of computing, STOC 1986. New York, NY: Association for Computing Machinery (ACM), 350–355 (1986; doi:10.1145/12130.12166)], which adds to \(\mathbb{Z}/p\mathbb{Z}\) a set of Gaussian periods parametrized by a period system.
Section 1 enunciates the main result (Theorem 1) and the auxiliary results necessaries to prove it (Theorems 2 to 5) and Section 2 gives the definition of pseudofield and period system and states some properties of them whose proof is delayed to later. Then Section 3 gives the proof of Theorem 1 (see Algorithm 3.3) assuming the validity of the auxiliary results.
The rest of the paper deals with the auxiliary results. Section 4 provides the proof of Theorem 2 (which gives a method to construct finite fields) and Sections 5 to 8 the proof of the properties of pseudofields states in Section 2.
The following Sections are more analytic. Section 9 gives the proof of Theorem 3 (inspired by the result of Bleichenbacher) and Section 10 a stronger version of Theorem 4 (a number-theoretic application of Theorem 3). Sections 11 and 12 are devoted to the proof of Theorem 5 and finally Section 13 proves the existence of periodic systems.


11Y11 Primality
11N13 Primes in congruence classes
11P70 Inverse problems of additive number theory, including sumsets


Zbl 1071.11070
Full Text: DOI


[1] Adleman, L. M., Lenstra, H. W., Jr.: Finding irreducible polynomials over finite fields. In: Proc. 18th Annual ACM Symp. on Theory of Computing (STOC) (Berkeley, 1986), ACM, 350–355 (1986)
[2] Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. of Math. 160, 781–793 (2004) Zbl 1071.11070 MR 2123939 · Zbl 1071.11070
[3] Atiyah, M. F., Macdonald, I. G.: Introduction to Commutative Algebra. Addison-Wesley, Reading, MA (1969)Zbl 0175.03601 MR 0242802 · Zbl 0175.03601
[4] Avanzi, R. M., Mih˘ailescu, P.: Efficient “quasi”-deterministic primality test improving AKS. http://www.uni-math.gwdg.de/preda/mihailescu-papers/ouraks3.pdf
[5] Balog, A.: p + a without large prime factors. In: Seminar on Number Theory, 1983–1984 (Talence, 1983/1984), exp. 31, Univ. Bordeaux I, Talence, 5 pp. (1984)Zbl 0588.10052 MR 0784077
[6] Bernstein, D. J.: Proving primality in essentially quartic random time. Math. Comp. 76, 389– 403 (2007)Zbl 1144.11085 MR 2261028 · Zbl 1144.11085
[7] Bernstein, D. J.: Fast multiplication and its applications. In: J. P. Buhler and P. Stevenhagen (eds.), Algorithmic Number Theory, MSRI Publ. 44, Cambridge Univ. Press, New York, 325– 384 (2008)Zbl 1208.68239 MR 2467550 · Zbl 1208.68239
[8] Bernstein, D. J., Lenstra, H. W., Jr., Pila, J.: Detecting perfect powers by factoring into coprimes. Math. Comp. 76, 385–388 (2007)Zbl 1110.11038 MR 2261027 · Zbl 1110.11038
[9] Berrizbeitia, P.: Sharpening “ PRIMES is in P” for a large family of numbers. Math. Comp. 74, 2043–2059 (2005)Zbl 1071.11071 MR 2164112 · Zbl 1071.11071
[10] Bleichenbacher, D.: The continuous postage problem. Unpublished manuscript (2003)
[11] Bostan, A., Flajolet, P., Salvy, B., Schost, ´E.: Fast computation of special resultants. J. Symbolic Comput. 41, 1–29 (2006)Zbl 1121.13037 MR 2194883 · Zbl 1121.13037
[12] Brent, R. P.: Fast multiple-precision evaluation of elementary functions. J. Assoc. Comput. Mach. 23, 242–251 (1976)Zbl 0324.65018 MR 0395314 · Zbl 0324.65018
[13] de Bruijn, N. G.: The asymptotic behaviour of a function occurring in the theory of primes. J. Indian Math. Soc. (N.S.) 15, 25–32 (1951)MR 0043838 · Zbl 0043.06502
[14] Cassels, J. W. S.: An Introduction to the Geometry of Numbers. 2nd ed., Springer, Berlin (1971)Zbl 0209.34401 MR 0306130 · Zbl 0209.34401
[15] Davenport, H.: Multiplicative Number Theory. 2nd ed., Grad. Texts in Math. 74, Springer, New York (1980)Zbl 0453.10002 MR 0606931 · Zbl 0453.10002
[16] Deshouillers, J.-M., Iwaniec, H.: Kloosterman sums and Fourier coefficients of cusp forms. Invent. Math. 70, 219–288 (1982/83)Zbl 0502.10021 MR 0684172 · Zbl 0502.10021
[17] Deshouillers, J.-M., Iwaniec, H.: On the Brun–Titchmarsh theorem on average. In: Topics in Classical Number Theory (Budapest, 1981), G. Hal´asz (ed.), Vol. I, Colloq. Math. Soc. J´anos Bolyai 34, North-Holland, Amsterdam, 319–333 (1984)Zbl 0548.10026 MR 0781145 Primality testing with Gaussian periods1269 · Zbl 0548.10026
[18] Erd˝os, P.: On the normal number of prime factors of p − 1 and some related problems concerning Euler’s ϕ-function. Quart. J. Math. (Oxford Ser.) 6, 205–213 (1935)Zbl 0012.14905
[19] Farkas, J.: Theorie der einfachen Ungleichungen. J. Reine Angew. Math. 124, 1–27 (1902) JFM 32.0169.02 MR 1580578 · JFM 32.0169.02
[20] Friedlander, J. B.: Shifted primes without large prime factors. In: Number Theory and Applications, R. A. Mollin (ed.), Kluwer, Dordrecht, 393–401 (1989)Zbl 0686.10030 MR 1123085 · Zbl 0686.10030
[21] von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge Univ. Press, Cambridge (1999)Zbl 0936.11069 MR 1689167
[22] Granville, A., Koukoulopoulis, D., Matom¨aki, K.: When the sieve works. Duke Math. J. 164, 1935–1969 (2015)Zbl 1326.11055 MR 3369306
[23] Huxley, M. N.: On the difference between consecutive primes. Invent. Math. 15, 164–170 (1972)Zbl 0241.10026 MR 0292774 · Zbl 0241.10026
[24] Lang, S.: Algebra. 3rd ed., Springer, New York (2002)Zbl 0984.00001 MR 1878556 · Zbl 0984.00001
[25] Lev, V. F.: The continuous postage stamp problem. J. London Math. Soc. 73, 625–638 (2006) Zbl 1174.11012 MR 2241970 · Zbl 1174.11012
[26] Lidl,R.,Niederreiter,H.:FiniteFields.Addison-Wesley,Reading,MA(1983) Zbl 0554.12010 MR 0746963
[27] Montgomery, H. L., Vaughan, R. C.: The large sieve. Mathematika 20, 119–134 (1973) Zbl 0296.10023 MR 0374060 · Zbl 0296.10023
[28] Pomerance, C., Shparlinski, I. E.: Smooth orders and cryptographic applications. In: Algorithmic Number Theory (Sydney, 2002), Lecture Notes in Computer Sci. 2369, Springer, Berlin, 338–348 (2002)Zbl 1058.11059 MR 2041095 · Zbl 1058.11059
[29] Shoup, V.: Fast construction of irreducible polynomials over finite fields. J. Symbolic Comput. 17, 371–391 (1994)Zbl 0815.11059 MR 1289997 · Zbl 0815.11059
[30] Timofeev, N. M.: The Vinogradov–Bombieri theorem. Mat. Zametki 38, 801–809, 956 (1985) (in Russian)Zbl 0588.10043 MR 0823418 · Zbl 0588.10043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.