Currently our Poly type is difficult to use, because we have to manually reduce the polynomial to the canonical representation, without any leading zero coefficients (if we don't, some code will panic).
As part of this we can:
[x] implement a transparent type wrapper (as a starting point) - #27
[x] reduce by the polynomial modulus on construction, conversion, mul, pow, any other operations that can increase the degree
[x] truncate leading zeroes using a method
[x] fix inserting terms above the current size of the internal vector, which should never panic
fix inserting terms at or above index MAX_POLY_DEGREE (which should reduce down strictly lower than MAX_POLY_DEGREE)
[x] add a Poly::xn() method that creates a polynomial with X^n
[x] replace zero_poly(...).degree(), so it doesn't panic
change the assertions in cyclotomic_mul() so they are modular reductions instead
[x] extract the canonicalisation in cyclotomic_mul() into a reusable method
[x] add tests as needed
[x] Creating optimal implementation for multiplication by a power of X, which is “just a right shift, filling with zeros”, this is more efficient than the naive algorithm. This is called twice per chunk, so it is used a lot.
Currently our
Poly
type is difficult to use, because we have to manually reduce the polynomial to the canonical representation, without any leading zero coefficients (if we don't, some code will panic).As part of this we can:
pow,any other operations that can increase the degreefix inserting terms at or above indexMAX_POLY_DEGREE
(which should reduce down strictly lower thanMAX_POLY_DEGREE
)Poly::xn()
method that creates a polynomial withX^n
zero_poly(...).degree()
, so it doesn't panicchange the assertions incyclotomic_mul()
so they are modular reductions insteadcyclotomic_mul()
into a reusable method