Faster modular reduction for Falcon signature verification

[Al-Kindi-0]

The Falcon signature verification algorithm relies heavily on modular arithmetic with respect to the prime $12289$. The current implementation rpo_falcon512::mod_12289 is very inefficient since it uses u64_div underneath. A more optimized implementation should, in addition to using non-determinism, take into account the fact that $12289$ is less than $2^{32} - 1$.

[bobbinth]

One other thing to consider: would it make sense to add a native instruction which can do a modular reduction in a single VM cycle. The instruction could work like this:

Inputs:  [v, p, ...]
Outputs: [r, p, ...]

Where:

• $v$ is the value to be reduced - could be any field element.
• $p$ is the modulus which must be a u32 value.
• $r = v % p$.

It probably doesn't make sense to add it solely for the purposes of Falcon signature, but if it could be used to speed up other things (e.g., ECDSA signature verification), then it might be worth it.

Also, I'm not sure how complex the constraints for this instruction would be - so, maybe not viable to begin with.

[Al-Kindi-0]

We have managed to improve the implementation of the Falcon signature verification by limiting the number of modular reductions in the first place in #1623 . So we can safely close this issue.