Small size fft/ntt

[hacatu]

What is the problem you want to solve and can not with the current version?
tfhe_ntt::prime32::Plan::try_new and friends are hardcoded to fail if you try to use a length < 32.

Describe the solution you'd like
These functions should let you set up very short transforms.

Describe alternatives you've considered
We can just zero pad up to 32, but this makes debugging code using ntt more difficult for no reason.

Additional context
I'm trying to do a multidimensional ntt on top of the 1D prime32 impl, but it is unnecessarily hard to debug because even in 2D, the minimum transform size now forces us to look at 1024 sized arrays instead of 16.

[IceTDrinker]

hello @hacatu

tfhe-ntt and tfhe-fft were built for performance and make heavy use of SIMD instructions which explains why the minimum size is 32, they are also geared towards the use made in LWE/GLWE cryptograhy which generally makes use of large polynomial sizes.

from the code

        // 32 = 16x2 = max_register_size * ntt_radix,
        // as SIMD registers can contain at most 16*u32
        // and the implementation assumes that SIMD registers are full

u64 ntts can be as small as 16, but of course the performance won't be the same.

We unfortunately don't currently have bandwidth to dedicate to this issue.

Having said that, we are open source, if there is a way to make it work while keeping the current performance for the existing cases we can take a look at contributions when we have some time available.

Regards