PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:medhard PREREQUISITES:fft, advanced maths PROBLEM:You are given a polynomial of degree $N$. You have to evaluate the polynomial at some $Q$ points modulo 786433. EXPLANATION:Look at the special modulo Let us learn some basics before proceeding towards FFT algorithm Let ${\mathbb{Z}/p}^{+}$ denote the group of nonzero elements $\{1, 2, \dots, p  1\}$, i.e.$\mathbb{Z}/p  \{0\}$. This group is a cyclic group. A group is called a cyclic group if it can be generated by a single element. In other words, $g, g^2, g^3, , g^(p  1)$ will cover all the elements of the group. Note that $g^p = g$. Such an element $g$ is called generator of the group. For example, in group ${\mathbb{Z}/5}^{+} = \{1, 2, 3, 4 \}$, $g = 2$ is a generator. We have $2^1 = 2 \mod 5$, $2^2 = 4 \mod 5$, $2^3 = 3 \mod 5$, $2^4 = 1 \mod 5$. Note that these cover {2, 4, 3, 1}, i.e. all the elements of the group. You can see that each element of this group can be written as powers of $g$. Also see that $3$ is also a generator of the group as $3^1 = 3 \mod 5$, $3^2 = 4 \mod 5$, $3^3 = 2 \mod 5$, $3^4 = 1 \mod 5$. However $g = 4$ is not a generator of the group as $4^1 = 4 \mod 5$, $4^2 = 1 \mod 5$, $4^3 = 4 mod 5$, $4^4 = 1 \mod 5$, which covers only the elements $1, 4$. You can find one such generator for the group ${\mathbb{Z}/p}^{+}$ (for $p$ = 786433) using a simple bruteforce. You can iterate over each number $g$ from 1 to $p1$ and check whether the $g^i$ spans all the elements of the group or not. Luckily for this modulo, you can afford to spend $\mathcal{O}(p \, log p)$ time for checking a number being generator or not, because you will soon hit a generator at $g = 10$. You can run this program offline on your computer in 1 or 2 minutes and find one such generator. In fact, there is a better algorithm than simple bruteforce for checking whether a number is generator or not. For a given $g$, you just have to check whether all the $g^d mod p$ where $d$ is a divisor of $p1$ are all distinct values or not. Towards the FFT algorithm **Let us take a small example Let us take an example to understand about FFT better. Suppose the polynomial be $x^3 + 3 * x^2 + 4 * x + 5$. We want to evaluate it at four points $\omega, {\omega}^2, {\omega}^3, {\omega}^4$, where $\omega$ is a primitive $4$th root of unity, i.e. $\omega^4 = 1$, and there does not exist any $i < 4$, such that $\omega^i = 1$. In other words, $\omega$ is a generator of the corresponding group. Let us divide the polynomial into two parts  the polynomial made of coefficients of even power of $x$ and other of odd powers of $x$. In our case, these polynomials will be $x^3 + 4 * x$ and $3 * x^2 + 5$, respectively. $$P(x) = $x^3 + 3 * x^2 + 4 * x + 5$$ $$P_{odd}(x) = $x^3 + 4 * x$$ $$P_{even}(x) = $3 * x^2 + 5$$ $$P(x) = x * P_{odd}(x^2) + P_{even}(x^2)$$ Note that now both the polynomials $P_{odd}(x)$ and $P_{even}(x)$ are having only even powers of $x$, i.e. they can even be considered polynomials in $x^2$. So, instead of evaluating them on $x$, let us evaluate them on $x^2$. $$P(x) = x * P_{odd}(x^2) + P_{even}(x^2), \text{where } P_{odd}(x) = x + 4$$ Let us see what happens with set of points $x$ where we want to evaluate the polynomail when we change $x$ to $x^2$. The set of elements of $x^2$ for the given $x$ will be ${\omega^2, {\omega}^4, {\omega}^6, {\omega}^8 }$. Note that we have $\omega^4 = 1$, so this set will be ${\omega^2, 1, {\omega}^2, 1 }$. You see that this set has only two distinct elements in it, $1$ and $\omega^2$. Now you can recursively evaluate the both the polynomials $P_{odd}(x)$ and $P_{even}(x)$ at these two points and combine their them to get an evaluation for each of the four original $x$ values. Regarding the time complexity, you can notice that in the recursion, both the sizes of the polynomial and that of number of points to evaluate become half in each iteration, which gives a time complexity of $\mathcal{O}(n log n)$ ($n = 4$ for our case). **Let's do FFT for general $n$** Let $P(x)$ be the polynomial we want to evaluate at $\omega, { \omega}^2, \dots, {\omega}^n$ points, where $\omega$ is a primitive $n$th root unity. Notice that the set $\omega, { \omega}^2, \dots, {\omega}^n$ contains all distinct elements. $$ S = {{ \omega}, { \omega}^2, \dots, {\omega}^{n  1}, {\omega}^{n} }$$ $$ S^2 = { {\omega}^2, { \omega}^4, \dots, {\omega}^{2 * n} }$$ $$ S^2 = { {\omega}^2, { \omega}^4, \dots { \omega}^{2 * (n / 2  1)}, { \omega}^n, { \omega}^{2 * (n / 2 + 1)}, \dots, {\omega}^{2 * n} }$$ Note that ${\omega}^n = 1$. $$ S^2 = {{\omega}^2, { \omega}^4, \dots, { \omega}^4, { \omega}^{2}, \dots, {\omega}^{n} }$$ $$ S^2 = { {\omega}^2, { \omega}^4, \dots, {\omega}^{n)} }$$ Note that $S^2$ has size $\frac{n}{2}$. Also notice that ${({\omega}^2)} ^ {\frac{n}{2}} = 1 \mod n \implies {({\omega}^2)} ^ {\frac{n}{2}} = 1 \mod n / 2$. Pseudo Code
Setter's and Tester's Solutions:
This question is marked "community wiki".
asked 19 Jul '16, 22:47

You call this simple? I think there must be a number to the relative hardness of the problem, based on number of attempts, the rating of coders who attempted it, those who got it right, those who couldn't, etc. 'Simple' is like too much! :P answered 20 Jul '16, 10:00

Since 786433=1+3∗2^18 and 786433 is a prime I used NTT by first dividing P(x) in three parts as P(x) = P0(x^3) + x*P1(x^3) + x^2P2(x^3) and then used NTT for polynomials P0, P1 and P2. In this way I computed values of P(x) at all x mod 786433 (except P(0) which is equal to coefficient a0). answered 20 Jul '16, 01:28

As always, the links to Setter's and tester's solution aren't working! Please look into it. Thank you answered 19 Jul '16, 23:34

Can anybody explain this part of the problem setter's solution:
answered 24 Jul '16, 20:23

Not able to access any solution.Please update the links. answered 19 Jul '16, 23:34

Just asking, was anybody able to solve this using general multipoint evaluation ?? Or is it even practically feasible for this problem ? answered 21 Jul '16, 20:04

Heading ##Can anyone explain stepbystep the functioning of fft function in setter's soln ??And also the importance of 786433 ?? Explanation with an example would be helpfull I am new at this answered 14 Aug '16, 10:20

Why is it needed to decompose in 3 polynomials ?? Can we concat 2^18 zeroes so that final polynomial becomes of 2^20 numbers which is perfect square and do NTT?? @n1t1n_153012 answered 17 Mar '17, 22:15
