Open Al-Kindi-0 opened 11 months ago
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:
u32
value.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.
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 usesu64_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$.