ECCC-Report TR98-054https://eccc.weizmann.ac.il/report/1998/054Comments and Revisions published for TR98-054en-usSun, 06 Sep 1998 22:24:14 +0200
Paper TR98-054
| On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems |
Igor E. Shparlinski
https://eccc.weizmann.ac.il/report/1998/054
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.
Sun, 06 Sep 1998 22:24:14 +0200https://eccc.weizmann.ac.il/report/1998/054