---
# System prepended metadata

title: 'Implement Montgomery reduction, use it to optimize FFT'

---

# Implement Montgomery reduction, use it to optimize FFT

- Implement partial Montgomery reduction subroutines for [ff crate](https://github.com/matter-labs/ff) as a trait.
- Use the outcome of this task along with additional research to improve FFT operation in [`plonk` branch of `bellman` crate](https://github.com/matter-labs/bellman/tree/plonk). Example of one of FFT approaches can be found [here](https://github.com/matter-labs/bellman/blob/plonk/src/plonk/fft/cooley_tukey_ntt/mod.rs). Unsafe code is allowed. FFT implementation may be not "in-place"
- Use outcomes of the previous work to also speed-up LDE operation - evaluation of the polynomial of degree n-1 on the domain of size 16 * n. Example of how it can be [done](https://github.com/matter-labs/bellman/blob/4f01fbd6ec3264c500796bd01ef8831a22dafefa/src/plonk/polynomials/mod.rs#L620)

The code should have some form of the trivial validity checks and benchmarks versus already implemented routines.

Guidance and assistance will be provided, but we expect independent research.
