The Length Ceiling

The result has about $1.2 \cdot 10^7$ coefficients and needs transform length $2^{24}$, but $p - 1$ is divisible by only $2^{23}$, so no primitive $2^{24}$-th root of unity exists. Move to a prime with a bigger power of two, such as $1004535809 = 479 \cdot 2^{21} + 1$, or split the convolution.

The result has about $1.2 \cdot 10^7$ coefficients and needs transform length $2^{24}$, but $p - 1$ is divisible by only $2^{23}$, so no primitive $2^{24}$-th root of unity exists. Move to a prime with a bigger power of two, such as $469762049 = 7 \cdot 2^{26} + 1$, or split the convolution.

The result has about $1.2 \cdot 10^7$ coefficients and needs transform length $2^{24}$, and $p - 1$ is divisible by $2^{26}$, so a primitive $2^{24}$-th root of unity does exist. The transform length depends on the array lengths alone, never on the modulus.

The result has about $1.2 \cdot 10^7$ coefficients and needs transform length $2^{24}$, but the 64-bit butterfly product overflows at that length, so the roots of unity lose precision. Switch the accumulator to __int128, which restores the exact result at any transform length.