search

nucypher / HEAAN.jl

Implementation of HEAAN in Julia
https://nucypher.github.io/HEAAN.jl/
GNU General Public License v3.0
2 stars 2 forks source link

Speed up RNS multiplication #9

Open fjarri opened 4 years ago

fjarri commented 4 years ago

Two ways are possible:

  1. Store some of the values in Montgomery representation. Good candidates are the keys and perhaps bootstrap values? We can prevent mistakes by creating a RNSPolynomialTransformedM type in addition to RNSPolynomialTransformed, and making sure that only operators non-M + non-M = non-M, M + M = M, non-M * M = non-M and M * M = M are defined.

  2. If non-M * non-M is necessary somewhere after step 1, Barrett reduction can be used there.

  3. More convenient moduli can be chosen (close to 2^64, with small number of bits set). This will require support from DarkIntegers.

fjarri commented 4 years ago
  1. It may also help to store residuals already casted to RRElem (Julia should be able to optimize this, but who knows).