Extension of ntl-extra's polynomial algebra

[maelhos]

While working on algebraic cryptanalysis, I ended up coding a few potentially useful functions that could be useful as part of PML, here is a non-exhaustive list :

• Factorial Store :

  • Currently the zz_pX_shift_large_characteristic holds the precomputation of factorials and their inverses, but those are useful in many different algorithms, and the class structure does not allow sharing them. The factorial store is build like the zz_p::init as a global context and allows for an auto-resizable array of factorials with their inverses.

• Extension of bivariate polynomials zz_pXY

  • overloading of operator>> to load polynomials
  • the power function (following NTL's convention)
  • 2D Taylor Shift : computation of f(x + a, y + b) in a single bivariate multiplication
    (there might be a way to do it on the top part of the multiplication to utilize middle_product as for the implementation of 1D Taylor Shift)
  • Representation switch of X and Y (might be not that useful to a most users)

• Tri-variate polynomials zz_pXYZ with more or less the same conventions and overload as zz_pXY

• N-variate polynomials zz_pXi using recursive template (WARNING : still experimental, the representation is very fast but hard to use because of templates)

• Pretty print pp: overloaded function for multiple types from the base NTL and PML that converts a given polynomial into a "nice" mathematical representation, meaning x^2 + 2x + 1 instead of [1 2 1]

• When working on the NTL, one usually uses a custom patched NTL at least to increase max FFT size, because PML uses the system's NTL, one is then forced to install a patched NTL on his system (which then breaks sage build pipeline btw...), PML should have a way to specify the NTL's static lib path when running make

Some of these features might be too specific, so feel free to tell me which are appropriate and I will make a pull request. Also, don't hesitate to ask me for related features or clarifications !

[vneiger]

Thanks for the work and contribution! We could work with multiple PRs, going from the "simplest" ones to those which will require more thoughts? For example:

• pretty print, bivariate additions, trivariate should be easy to integrate (each of them with a single PR, to simplify reviewing)
• factorial store is interesting, it might need some discussion on the design (just to be careful with global things!) but I don't expect any issue
• n-variate polynomials: it depends on the level of "experimental-ness", so this could be kept as the last task.