Hi,
One can encrypt large integers using Chinese remainder theorem – as mentioned at: Operations | TFHE-rs
As mentioned in the post one has to find base b_i of coprime numbers such that all of them are max 4 bits. My question is how do we tackle numbers which has prime divisors (which will turn out to be basis) of size more than 4 bits?
Thanks very much.
Hello @bhavinmoriya58
There are two strategies in TFHE-rs
One is to choose parameters with a power of 2 modulus bigger than the prime b_i (and apply the modular reduction via a PBS)
The other one is to use a prime modulus equal to b_i and there is special code involved to manage that (called native_crt in the lib IIRC) I can ask for a reference as I did not personally work on that and I’m unsure of the specifics.
Cheers
Hello @IceTDrinker
Thank you very much for the information. In addition to native_crt, I would also love to read more about how to apply modular reduction via a PBS. In that regard, won’t we lose the CRT mechanism?
Cheers 
Hello @bhavinmoriya58
If you have a parameter sets to e.g. compute over 4 bits, then if we want to work modulo 5 (a prime) we need to ensure that we don’t go above the 4 bits limit, as is always the case for a 4 bits parameters set, and to apply the modulo then in the function we evaluate with the PBS we would do something like:
f(x) : x → x % 5
See the example in ServerKey in tfhe::shortint::server_key - Rust where there is a modulo applied.
So in this way you can apply the modulo you want on individual blocks of the CRT representation.
Cheers
hi, sorry to interrupt, do you always need a PBS for the modular reduction? I thought you were using something like \mod 2^p \times b_i .
The easiest way is a PBS, I think there are cases (notably with “native CRT”) where the modulus might be “free”