__
TR98-054 | 26th August 1998 00:00
__

#### On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

**Abstract:**
Lower bounds are obtained on the degree and the number of monomials of

Boolean functions, considered as a polynomial over $GF(2)$,

which decide if a given $r$-bit integer is square-free.

Similar lower bounds are also obtained for polynomials

over the reals which provide a threshold representation

of the above Boolean functions. These results provide first non-trivial lower bounds on

the complexity of a number theoretic

problem which is closely related to the integer factorization problem.