Polynomials with degree MAX_POLY_DEGREE - 1 have MAX_POLY_DEGREE coefficients, because the coefficients have degrees 0, 1, ... , MAX_POLY_DEGREE - 1.
Having an even number of coefficients is a requirement for efficient Karatsuba implementations. Otherwise we have to pad the polynomial with the odd number of coefficients to the next power of two when we split them.
So currently we:
declare MAX_POLY_DEGREE = 2048
have a modulus with degree MAX_POLY_DEGREE = 2048 and 2049 coefficients
have polynomials with degree MAX_POLY_DEGREE - 1 = 2047 and 2048 coefficients (which is a performance requirement)
Tasks
MAX_POLY_DEGREE
Coeff
Yashe
configBackground
One approach is to replace
const
generic with a trait like this:And
FULL_RES_POLY_DEGREE
is replaced with:See https://github.com/Inversed-Tech/eyelid/pull/47#discussion_r1570509963
I think it would be better to use
MAX_POLY_DEGREE = 2047
and create aliases for maximal number of coefficients, and the degree of the modulus._Originally posted by @emmorais in https://github.com/Inversed-Tech/eyelid/pull/47#discussion_r1572468457_
Polynomials with degree
MAX_POLY_DEGREE - 1
haveMAX_POLY_DEGREE
coefficients, because the coefficients have degrees0, 1, ... , MAX_POLY_DEGREE - 1
.Having an even number of coefficients is a requirement for efficient Karatsuba implementations. Otherwise we have to pad the polynomial with the odd number of coefficients to the next power of two when we split them.
So currently we:
MAX_POLY_DEGREE = 2048
MAX_POLY_DEGREE = 2048
and 2049 coefficientsMAX_POLY_DEGREE - 1 = 2047
and 2048 coefficients (which is a performance requirement)This is slightly confusing, and could benefit from some renames and calculated constants. For example: https://github.com/Inversed-Tech/eyelid/pull/47/files/a6821dcd3aa5a11af24e57ce60b872babd3eeadc#r1571498268
Under the alternative scheme, we would:
MAX_POLY_DEGREE = 2047
MAX_POLY_DEGREE + 1 = 2048
and 2049 coefficientsMAX_POLY_DEGREE = 2047
and 2048 coefficientsThe underlying sizes wouldn't change, but this way of coding them seems to be more confusing, and could cause more off-by-one errors.
See the comment thread https://github.com/Inversed-Tech/eyelid/pull/47#discussion_r1570513537