1
$\begingroup$

Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that satisfy the equation

$$a^2 + b^3 = c^4 \mod n\,,$$

where $a,b,c \in\{0,1,....,n-1\}$ and $n$ is any natural number.

Does anybody have any idea how to do this? Obviously checking all values yields $O(n^2)$ time.

I am able to compute the triples for a given value of $c$ within the desired bound since you can build a BST in $O(n\log n)$ time where the keys are the particular modulo values in $b^3$ and the values are the number of instances they appear. Then by calculating $((c^4 \!\!\mod n) + n - (a^2 \!\!\mod n)) \!\!\mod n$ for every value of $a$ and doing a search for that key in $b$ we achieve the desired runtime.

How can I achieve the same result for every value of $c$ rather than a specific one though?

I presume the $O(n\log n)$ run-time comes from some form of binary search, sorting or binary search tree but I am not sure exactly how to achieve this for all the values of $c$ rather than a specific one. Any help is appreciated. Thank you.

$\endgroup$
1
$\begingroup$

Hint: Use FFT to multiply the polynomials $$ \sum_a x^{a^2 \pmod{n}}, \qquad \sum_b x^{b^3 \pmod{n}}. $$

$\endgroup$
  • $\begingroup$ I think I see it. The coeficients of each polynomial essentially count how many values of $a^2 \mod n$ and $b^3 \mod n$, e.g the constant terms of the polynomials will be how many values have a modulus of 0. Then by convolving them (i.e taking the FFT) you multiply the correct products (I am thinking of flip and slide) so the coefficients of the resulting polynomial are the final count. That is really smart! Thank you! $\endgroup$ – Four_FUN Nov 17 '14 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.