The concept of complex numbers arises from the need to solve equations like \(x^2 + a = 0\) which have no solution in the set of real numbers. To address this, the imaginary unit 'i' is introduced, defined by \(i^2 = -1\). A complex number is then represented in the form \(a + bi\), where \(a\) and \(b\) are real numbers, and the set of all complex numbers is denoted by \(\mathbb{C}\).

1.1 Definitions and Representations

• Algebraic Form: \(z = a + bi\). Here, \(a\) is the real part (\(Re(z)\)) and \(b\) is the imaginary part (\(Im(z)\)).
• Trigonometric Form: \(z = r(\cos \theta + i \sin \theta)\), where \(r = |z|\) is the modulus and \(\theta = Arg(z)\) is the argument.
• Exponential Form: \(z = r e^{i \theta}\), derived from Euler's formula: \(e^{ix} = \cos x + i \sin x\).

Complex numbers partition into real numbers (when \(b=0\)), imaginary numbers (when \(b \neq 0\)), and pure imaginary numbers (when \(a=0\) and \(b \neq 0\)).

1.2 Geometric Interpretation and Operations

Complex numbers can be visualized on a 2D plane called the complex plane, where the horizontal axis represents real numbers and the vertical axis represents imaginary numbers. A complex number \(a + bi\) corresponds to the point \((a, b)\) or a vector from the origin to \((a, b)\).

• Addition/Subtraction: Performed component-wise: \((a + bi) \pm (c + di) = (a \pm c) + (b \pm d)i\). The set of complex numbers with addition forms an Abelian group.
• Multiplication: \((a + bi)(c + di) = (ac - bd) + (ad + bc)i\). Geometrically, multiplication involves multiplying moduli and adding arguments. The set of non-zero complex numbers with multiplication also forms an Abelian group.
• Division: Performed by multiplying the numerator and denominator by the conjugate of the denominator. Geometrically, it involves dividing moduli and subtracting arguments.

1.3 Conjugate, Argument, and Euler's Formula

• Complex Conjugate: For \(z = a + bi\), its conjugate is \(\bar{z} = a - bi\). Properties include \(z\bar{z} = |z|^2\) and \(\overline{z \pm w} = \bar{z} \pm \bar{w}\), \(\overline{zw} = \bar{z}\bar{w}\).
• Argument: The engle \(\theta\) in the trigonometric form. The principal argument (\(arg(z)\)) is typically in the range \((-\pi, \pi]\).
• Euler's Formula: \(e^{ix} = \cos x + i \sin x\). This fundamental formula connects exponantial and trigonometric functions and is crucial for understanding complex exponentials. A special case is \(e^{\pi i} = -1\).

1.4 Complex Exponential and Trigonometric Functions

• Complex Exponential: Defined as \(e^z = e^{x+iy} = e^x(\cos y + i \sin y)\). It satisfies \(e^{z_1+z_2} = e^{z_1}e^{z_2}\) and is periodic with period \(2\pi i\).
• Complex Trigonometric Functions: Defined using complex exponentials: \(\cos z = \frac{e^{iz} + e^{-iz}}{2}\) and \(\sin z = \frac{e^{iz} - e^{-iz}}{2i}\). Unlike their real counterparts, their range is the entire complex plane (excluding zero).

1.5 Roots of Unity

The \(n\)-th roots of unity are the solutions to \(x^n = 1\). These are given by \(w_n^k = e^{i \frac{2\pi k}{n}}\) for \(k = 0, 1, \ldots, n-1\). They possess properties like \(w_n^{a+b} = w_n^a w_n^b\), \(w_{ln}^{lk} = w_n^k\) (periodicity and reducibility), and \(\sum_{k=0}^{n-1} w_n^k = 0\).

1.6 C++ complex Class

C++ provides a standard complex<T> template class (where T can be float, double, or long double) for handling complex numbers. It supports initialization, arithmetic operations, and functions like real(), imag(), abs(), and arg().

2. Polynomials

---

2.1 Definitions

A polynomial is a sum of terms involving a variable raised to non-negative integer powers, each multiplied by a constant coefficient. \(f(x) = \sum_{i=0}^{n} a_i x^i\). The degree of a polynomial is the highest power of the variable with a non-zero coefficient.

2.2 Polynomial Representations

• Coefficient Representation: Storing the coefficients \(a_0, a_1, \ldots, a_n\). Operations like addition take \(O(n)\) time.
• Point-Value Representation: Storing \(n+1\) pairs \((x_i, f(x_i))\) for distinct \(x_i\). This representation is useful for polynomial multiplication. Converting between coefficient and point-value representations naively takes \(O(n^2)\) time (e.g., using Horner's method for evaluation and Lagrange interpolation for reconstruction).

2.3 Polynomial Addition

Adding polynomials in coefficient form involves adding corresponding coefficients: \( (a_i + b_i) \). In point-value form, it involves adding the functon values at the same points: \( (p_i, f(p_i) + g(p_i)) \). Both take \(O(n)\) time.

2.4 Polynomial Convolution (Multiplication)

The convolution of two polynomials \(f(x) = \sum a_i x^i\) and \(g(x) = \sum b_j x^j\) is a polynomial \(h(x) = f(x)g(x) = \sum c_k x^k\), where \(c_k = \sum_{i+j=k} a_i b_j\). The degree of \(h(x)\) is the sum of the degrees of \(f(x)\) and \(g(x)\).

• Naive Coefficient Multiplication: Calculating each \(c_k\) directly takes \(O(n^2)\) time.
• Point-Value Multiplication: If polynomials are represented by their values at the same set of points, multiplication becomes point-wise multiplication of values: \( (p_i, f(p_i)g(p_i)) \). This takes \(O(n)\) time, but the conversion between representations is the bottleneck.

3. Fast Fourier Transform (FFT)

---

FFT is an efficient algorithm for computing the Discrete Fourier Transform (DFT), which transforms a polynomial from its coefficient representation to its point-value representation. It leverages the properties of roots of unity and a divide-and-conquer approach.

3.1 Divide and Conquer Approach

A polynomial \(F(x)\) of degree \(n\) can be split into two polynomials \(G(x^2)\) and \(xH(x^2)\), where \(G\) and \(H\) have half the degree of \(F\). This recursive structure allows FFT to compute the values of \(F(x)\) at the \(n\)-th roots of unity in \(O(n \log n)\) time.

3.2 Butterfly Operation

The core of the FFT algorithm involves combining results from subproblems. The "butterfly" operation efficiently computes \(F(w_m^k)\) and \(F(w_m^{k + m/2})\) from \(G(w_{m/2}^k)\) and \(H(w_{m/2}^k)\) using the relations: \(F(w_m^k) = G(w_{m/2}^k) + w_m^k H(w_{m/2}^k)\) \(F(w_m^{k + m/2}) = G(w_{m/2}^k) - w_m^k H(w_{m/2}^k)\) This can be done in-place, avoiding extra space.

3.3 Bit-Reversal Permutation

The divide-and-conquer structure of FFT naturally leads to a reordering of the input array. The required permutation is a bit-reversal permutation, where the element at index \(i\) moves to the index obtained by reversing the binary representation of \(i\). This can be achieved efficiently in \(O(n)\) time using bit manipulation.

3.4 Inverse FFT (IFFT)

The IFFT is used to convert the point-value representation back to the coefficient representation. It is very similar to the FFT algorithm, typically involving computing the FFT with conjugated roots of unity and then scaling the result by \(1/n\).

4. Number Theoretic Transform (NTT)

---

NTT is an adaptation of FFT that operates over finite fields (specifically, fields modulo a prime \(P\)). It uses primitive roots of unity modulo \(P\) instead of complex roots of unity. NTT avoids floating-point precision issues and is particularly useful for computations involving large integers where results are required modulo a prime.

Key requirements for NTT include the existence of a primitive \(n\)-th root of unity modulo \(P\), which implies that \(n\) must divide \(P-1\). The properties of primitive roots in modular arithmetic are analogous to those of complex roots of unity.