Usage of Different MATHBACKEND

Library Questions
1

Hello,

Are there more descriptions/applications described on different MATHBACKEND? I read the overview description in bigintbackend.h and have the following questions.

  1. I learned that the default MATHBACKEND is using bigintfxd, does it mean that we have maximum bit length equal to 32/64 according to the processor? So for the MATHBACKEND using bigintntl, it means that it can support bit length larger than 32/64?

  2. For the MATHBACKEND using bigintdyn, I’m not sure what it is used for? Are there any reference that can point some directions to me?

  3. It seems that no matter which MATHBACKEND uses the bluestein NTT. (To my knowledge, it can support the non power of 2 point by extending it to power of 2, and for the modular reduction it will commonly use the barrett reduction and further optimize it when choosing the solinas/low hamming weight prime.) So I wonder how do we decide the NTT prime when given a non prime according to the security level? (ex. For 128-bit security level in TFHE, how can we get that Q=134215681(≈2^27) and do the NTT operation under it?)

Thanks for the reading and sorry for the basic math problem…

2

I suggest reading the following article in the OpenFHE documentation: Math Backends — OpenFHE documentation

NTT is used for power-of-two polynomials, i.e., polynomials Z_q(X)/(X^N+1), where N is a power of two. q has to be a prime congruent to 1 mod 2*N for NTT to work. Bluestein transform is used for non-power-of-two polynomials (under the hood it uses NTTs as a subroutine).