_fmpzi_poly_mulmid_SS, _fmpzi_poly_mulmid_SS_pair, _fmpzi_poly_mulmid_SS_single

In the coefficient ring \mathbb{Z}/(2^N+1) of the transform, s = 2^{N/2} is a square root of -1, and \mathbb{Z}[i]/(2^N+1) \cong \mathbb{Z}/(2^N+1) \times \mathbb{Z}/(2^N+1) via a + bi \mapsto (a + sb, a - sb). The pair method (_SS_pair) therefore computes the Gaussian product as two ordinary convolutions, of u = \operatorname{re} + s \operatorname{im} and v = \operatorname{re} - s \operatorname{im}, with a ring size covering the components of the result, and recovered as \operatorname{re} = (U + V)/2, \operatorname{im} = (V - U) s / 2; all conversions are shifts and additions. This uses six transforms and two pointwise products per point (four transforms for squaring). The single embedding (_SS_single) uses the homomorphism a + bi \mapsto a + sb alone: one convolution in a ring of twice the size gives T = \operatorname{re} + s \operatorname{im}, from whose two's complement representation both parts are read off, the ring being large enough that |T| < 2^{N-1}. The transform work and the memory are about the same as for the pair method, but the ring is rounded up to a multiple of the transform length once rather than twice, which favors it for small coefficients relative to the length; it also halves the number of pointwise products, which favors it for small rings, while for medium rings the pointwise products of the larger ring cost more than twice as much. The main function chooses between them by the rounded ring sizes, as measured on x86-64. The convolution length is chosen as by fft_convolution_choose_mid, so middle products use the cyclic (wraparound) transform when it is shorter. When an operand is real or purely imaginary, its nonzero part is transformed once and multiplied by both parts of the other operand (two convolutions sharing that transform, five transforms in all), or by the single nonzero part of the other operand (one convolution).