# the number of rational points of a curve modulo 2

Consider the language $L=\{f, q\}$ - the number of solutions of equations $f(x,y)=0$ in $\mathbb{F}_q^2$ is equal to zero modulo $2$, where $q = 2^m$. Does $L$ belong to $P$? to $NP$? ($f$ is written as $\sum a_{ij} x^i y^j.$)

• $\oplus P$. Can you explain your interest in the problem? Sep 16 '16 at 23:16
• @JoshuaGrochow I have proved that if $f$ is given in sparse representation than this problem is $\oplus$-complete - arxiv.org/abs/1608.07564 Sep 17 '16 at 7:22
• @JoshuaGrochow However I do not think that this is true if $f$ is given in Sparse representation. I know there are polynomial algortihms for some curves but I do not know about general one Sep 17 '16 at 7:25
• It's worth specifying in the question that you are interested in the case where $f$ is given by the dense representation, then. It is also worth including in the statement of the question that in the sparse representation it is $\oplus P$-complete, that you already know it's obviously in $\oplus P$ in the dense representation, and that you're looking for evidence that it's not $\oplus P$-complete in the dense representation. None of this was obvious from the question itself (and also, there could potentially be other evidence against $\oplus P$-completeness besides being in P or NP). Sep 18 '16 at 3:57

This language belongs to P. See Corollary 7.4 at "Algorithmic theory of zeta functions over finite fields" by Daqing Wan. (There $n$ is the number of variables of a hypersurface, $d$ is the total degree of it, and $q$ is the cardinality of the corresponding finite field.)