A lower bound for primality

E. Allender; M. Saks; I. Shparlinski

doi:10.1006/jcss.2000.1725

A lower bound for primality

E. Allender^*, M. Saks, I. Shparlinski

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

13 Citations (Scopus)

Abstract

Recent work by Bernasconi, Damm, and Shparlinski showed that the set of square-free numbers is not in AC⁰ 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 AC⁰-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 AC⁰[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 language	English
Pages (from-to)	356-366
Number of pages	11
Journal	Journal of Computer and System Sciences
Volume	62
Issue number	2
DOIs	https://doi.org/10.1006/jcss.2000.1725
Publication status	Published - Mar 2001

Access to Document

10.1006/jcss.2000.1725

Cite this

@article{1b409e986a5243349d9f314abb94cad5,

title = "A lower bound for primality",

abstract = "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.",

author = "E. Allender and M. Saks and I. Shparlinski",

year = "2001",

month = mar,

doi = "10.1006/jcss.2000.1725",

language = "English",

volume = "62",

pages = "356--366",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - A lower bound for primality

AU - Allender, E.

AU - Saks, M.

AU - Shparlinski, I.

PY - 2001/3

Y1 - 2001/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0035276873&partnerID=8YFLogxK

U2 - 10.1006/jcss.2000.1725

DO - 10.1006/jcss.2000.1725

M3 - Article

AN - SCOPUS:0035276873

SN - 0022-0000

VL - 62

SP - 356

EP - 366

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

A lower bound for primality

Abstract

Access to Document

Other files and links

Fingerprint

Cite this