Page Contents
Goal: Support choosing, at run-time, which math backend to use.
Currently: Compile-time choice of which backend to use
Note
All implementations for Big/Native Integer/Vector are based on
integer.h (integer.h)
- By selecting a particular
MATHBACKEND
, we are choosing a default implementation for:BigInteger
BigVector
Poly
andciphertext modulus
used inDCRTPoly
- For native arithmetic,
NativeInteger
andNativeVector
is available.
You can either:
- Add a flag during the
CMAKE
process:cmake -DMATHBACKEND=4 ..
- Uncomment the appropriate line in
src/core/math/hal/bigintbackend.h
(and comment out the rest)
- Max size of
BigInteger
will beBitIntegerBitLength
(defined in`backend.h
) which has a default of 3000 bits. - It is advisable to select a value for
BigIntegerBitLength
larger than double thebitwidth
of the largest (ciphertext) modulus. - This parameter can be decreased for runtime/space optimization when the largest modulus is under 1500 bits.
- Note: The underlying implementation is fixed-size array of native
ints.
- Native integer used is defined by the
typedef
usingintegral_dtype
and MUST beuint32_t
; using other types is an open work item
- Native integer used is defined by the
- No Explicit max size of
BigInteger
- Size grows dynamically and is only constrained by memory
- The implementation requires that
UBINT_32
is defined as is inubintdyn.h
Note
Setting UBINT_64
is not supported. It is however a open
work item.
- Integration of
NTL
library withOpenFHE
- Only available when
NTL
orGMP
is enabled usingCMAKE
This is an integration of the NTL library with OpenFHE, and is only available when NTL/GMP is enabled using CMAKE.
We use the following naming conventions:
ModMul(b, mod)
- Naive modular multiplication that uses % operator for modular reduction
- usually slow.
ModMul(b, mod, mu)
- Barrett modular multiplication.
mu
for Barrett modulo can be precomputed bymod.ComputeMu()
.
- Barrett modular multiplication.
ModMulFast(b, mod)
- Naive modular multiplication w/ operands < mod
ModMulFast(b, mod, mu)
- Barrett modular multiplication w/ operands < mod
ModMulFastConst(b, mod, bPrecomp)
- modular multiplication using precomputed information on b, w/ operands < mod.
bPrecomp
can be precomputed byb.PrepModMulConst(mod)
.- This method is currently implemented only for NativeInteger class.
- The fastest method.
Variant | Naive | Barrett | Fast Naive | Fast Barrett | Fast Const |
---|---|---|---|---|---|
Mod | Mod(mod) | Mod(mod, mu) | |||
ModAdd | ModAdd(b, mod) | ModAdd(b, mod, mu) | ModAddFast(b, mod) | ||
ModSub | ModSub(b, mod) | ModSub(b, mod, mu) | ModSubFast(b, mod) | ||
ModMul | ModMul(b, mod) | ModMul(b, mod, mu) | ModMulFast(b, mod) | ModMulFast(b, mod, mu) | ModMulFastConst(b, mod, bPrecomp) |