...for zz_pX and ZZ_pX. Both algorithms require divisions by scalars up to the precision, so they cannot be used when the degree is larger than the characteristic, but they give significant speedups in large characteristic.
Example benchmark results for CharPolyMod() in zz_pX, where red is the current version of NTL and blue is this branch:
Characteristic $11$ (essentially unchanged):
(The outliers appear when the new algorithm cannot be used and the minimal and characteristic polynomials are not the same; in such a case the library falls back to a much slower algorithm.)
...for
zz_pXandZZ_pX. Both algorithms require divisions by scalars up to the precision, so they cannot be used when the degree is larger than the characteristic, but they give significant speedups in large characteristic.Example benchmark results for
CharPolyMod()inzz_pX, where red is the current version of NTL and blue is this branch:Characteristic $11$ (essentially unchanged):
(The outliers appear when the new algorithm cannot be used and the minimal and characteristic polynomials are not the same; in such a case the library falls back to a much slower algorithm.)
Characteristic $99999989 ≈ 2^{26.6}$ (much faster):
I've confirmed on millions of random instances that the code works correctly, for prime characteristics and degrees up to 100.