A lower bound for primality

Eric Allender*, Michael Saks, Igor Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

3 Citations (Scopus)


Recent work by Bernasconi, Damm and Shparlinski proved lower bounds on the circuit complexity of the square-free numbers, and raised as an open question if similar (or stronger) lower bounds could be proved for the set of prime numbers. In this short note, we answer this question affirmatively, by showing that the set of prime numbers (represented in the usual binary notation) is not contained in AC0[p] for any prime p. Similar lower bounds are presented for the set of square-free numbers, and for the problem of computing the greatest common divisor of two numbers.

Original languageEnglish
Title of host publicationProceedings of the Annual IEEE Conference on Computational Complexity
Place of PublicationPiscataway, N.J.
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages5
ISBN (Print)0769500757
Publication statusPublished - May 1999
Externally publishedYes
EventProceedings of the 1999 14th Annual IEEE Conference on Computational Complexity - Atlanta, GA, USA
Duration: 4 May 19996 May 1999


OtherProceedings of the 1999 14th Annual IEEE Conference on Computational Complexity
CityAtlanta, GA, USA


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

Cite this