Speed up NTT-based interpolation

[aszepieniec]

While benchmarking @AlexanderLemmens's modular reduction procedure I observed isolated cases where performance improved by switching from Montgomery representation and multiplication to canonical representation and Alexander reduction. Specifically, for large enough $N$, NTT-based interpolation seems to be faster. The following benchmark snippets are obtained after switching back from Alexander's method to Montgomery.

lagrange_interpolation/NTT-Based interpolation/4096                        
                        time:   [387.90 ms 388.46 ms 389.06 ms]
                        thrpt:  [10.528 Kelem/s 10.544 Kelem/s 10.559 Kelem/s]
                 change:
                        time:   [+1.3519% +2.9690% +4.3549%] (p = 0.00 < 0.05)
                        thrpt:  [-4.1731% -2.8834% -1.3339%]
                        Performance has regressed.

lagrange_interpolation/NTT-Based interpolation/16384                        
                        time:   [4.7962 s 4.8422 s 4.9162 s]
                        thrpt:  [3.3327 Kelem/s 3.3836 Kelem/s 3.4160 Kelem/s]
                 change:
                        time:   [+36.423% +38.074% +40.215%] (p = 0.00 < 0.05)
                        thrpt:  [-28.681% -27.575% -26.699%]
                        Performance has regressed.

All other benchmarks are green, implying that Montgomery is faster.

Focusing on these red ones, I would say it indicates some suboptimal processing. I estimate that there is some performance gain to be had here.

Note that this task has very low priority since NTT-based interpolation is not used anywhere. (We use INTT in Triton.)