TY - GEN

T1 - Lower bound for primality

AU - Allender, Eric

AU - Saks, Michael

AU - Shparlinski, Igor

PY - 1999

Y1 - 1999

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:0032670029

SN - 0769500757

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 10

EP - 14

BT - Proceedings of the Annual IEEE Conference on Computational Complexity

PB - IEEE Comp Soc

T2 - Proceedings of the 1999 14th Annual IEEE Conference on Computational Complexity

Y2 - 4 May 1999 through 6 May 1999

ER -