Expand integer math operations

[lognorman20]

What is the problem you want to solve and can not with the current version?
Currently, tfhe-rs supports basic operations on integers such as arithmetic, bitwise operations, comparisons, and min/max comparison. I propose this project to extend these existing primitives to more complicated integer operations in areas such as number theory. With this addition to tfhe-rs, users can abstract away functions they would have needed to implement themselves and focus on building meaningful projects. Further, this project aims to ensure its functions are high-speed and reliable.

Describe the solution you'd like
An extension of tfhe-rs with more functions similar to Rust's BigInt library.

Describe alternatives you've considered
Writing my own functions using already existing primitive operations (addition, multiplication, etc..)

Additional context
A few examples of functions to be added are the following:

• nth_root
• modinv
• modpow
• gcd
• lcm
• divides
• is_multiple_of
• is_even/odd
• next/prev_multiple_of
• median
• approx_log

These functions will leverage the already existing implementations of basic arithmetic. They would be added for both FheUint and FheInt.

Related links/References:
Python Math Library
Sage Integer Arithmetic
GNU Exponentiation and Logarithms
Rust num-bigint
ruint

I am happy to work on this project and discuss it further.

[IceTDrinker]

hey @lognorman20 thanks for following up here, we are in the process of streamlining contributions, thanks for your interest in TFHE-rs and wanting to expand it

We'll get back to you when we have more precise ways to contribute bigger chunks of code.

In the meantime, @tmontaigu if you can keep track of the proposals

[IceTDrinker]

@lognorman20 do you have a priority list on those operations ? And use cases corresponding to each ?

There are a few functions that look trivial to implement

[lognorman20]

@IceTDrinker The use cases will be for more general computational purposes in areas ranging from machine learning to data analysis, computer graphics, and compression algorithms. Some ideas off the top my head:

1. nth_root

   • Machine learning - scaling features and data normalization. For example, this project I've been working on that implements parts of Meta's LLaMa model using TFHE-rs
   • Physics and engineering
   • Computer graphics

2. modinv

   • Cryptography
   • Computer networking

3. modpow

   • Cryptography
   • Blockchain infrastructure

4. gcd

   • Data compression
   • Signal processing
   • Hardware design

5. lcm

   • Task scheduling and process management
   • Computer networking

6. median

   • Data analysis
   • Machine Learning - feature scaling and robust statistics for model training
   • Image Processing - median filtering for noise reduction in images

7. approx_log

   • Machine Learning - feature scaling and handling large-scale data
   • Data Analysis- modeling exponential growth and decay processes.

As for the priority list, I'd imagine those relating to machine learning operations would cater to a fair amount of users the most. I can come up with more functions relating to ML if you'd like. More useful functions can be added once support for floating point numbers is added as well.

I agree some functions are quite trivial, I just think it'd be nice to have an abstraction for the programmer. Another aspect is the optimization of these algorithms. The implementation of a trivial algorithm by a user who is unfamiliar with FHE concepts such as the costs of primitive operations (i.e. multiplication) could be quite slow and potentially unreliable. By implementing these functions for the user, the process of writing more complex programs based on standard operations such as sqrt becomes easier and more focused on the application. Further, several of these functions can feed into another project I've discussed in the Discord which is focused on implementing tensors/ndarrays in TFHE-rs.

[IceTDrinker]

@lognorman20 when I said trivial I meant that maybe those could be the first to be implemented to see what it would look like and start working on that with people external to Zama

[lognorman20]

@IceTDrinker ah okay, sure I can implement them externally

[IceTDrinker]

@lognorman20 unless you did not mean to contribute those 🙂 it's just that there have been discussions lately about external contributions, also as we have a lot of things to do external requests/ideas might not get prioritized as much as you'd expect

[lognorman20]

@IceTDrinker these operations don't seem too difficult to add and I was hoping to contribute them to this repo; however, I can write them on my own if other features are being prioritized

[IceTDrinker]

Yep, I understood you wanted to contribute, what I meant is that some of those are easier to implement and you could likely start with those, and that unless you did the implementation we would not have much time to do them ourselves

[lognorman20]

@IceTDrinker Thanks for clarifying, yes I'm okay with that

[lognorman20]

@IceTDrinker hey any updates on contributing? I'd love to get started on this or #1162 :)

[IceTDrinker]

Hey @lognorman20 we are in our release week so we’ll be busy, with that said you should take a look at the easier implementations for this issue, so that we iron out the contribution process we know some of the CI will need some improvements to work properly.

You should look at the is_even/is_odd implementation first as there is no critical design decisions to be made. You will want to add that to integer first (maybe shortint as well) at which point you can likely open a first PR so that you can familiarize yourself with the normal PR process and given the functionality is easy to understand we’ll look at making the CI work properly. In the meantime you will be able to look at how to expose that in the high level API for FheUint/FheInt and then the C API.

When you start working on other more complicated functions, could you ping us here so that we can discuss design ?