A lower bound for primality

Eric Allender, Michael Saks, Igor Shparlinski

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


Recent work by Bernasconi, Damm, and Shparlinski showed that the set of square-free numbers is not in AC0 and raised as an open question whether similar (or stronger) lower bounds could be proved for the set of prime numbers. We show that the Boolean majority function is AC0-Turing reducible to the set of prime numbers (represented in binary). From known lower bounds on Maj (due to Razborov and Smolensky) we conclude that primality cannot be tested in AC0[p] for any prime p. Similar results are obtained for the set of square-free numbers and for the problem of computing the greatest common divisor of two numbers.

Original languageEnglish (US)
Article number91725
Pages (from-to)356-366
Number of pages11
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - 2001

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Applied Mathematics
  • Computer Science(all)
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'A lower bound for primality'. Together they form a unique fingerprint.

Cite this