cairo-lang
cairo-lang copied to clipboard
uint256_mod_inv standard function with a hint
It would be awesome if we could get this method included in the standard library and whitelisted for usage in starknet since it uses a hint and immediately checks it with this part of the code:
let (quotient_low, quotient_high, remainder) = uint256_mul_div_mod(a,res,div);
assert Uint256(low=1,high=0) = (remainder);
Modular inversion is one of the essential elliptic curve computations. And here we have a nice trick to calculate it in the hint and check if after the hint.
For comparison to the EVM: EVM has a precompiled expmod link but implementing expmod in cairo and starknet is another story because of the current state of sequencers on starknet(expmod is computationally heavy computation(~500k steps in cairo for an exponent of 256-bit). And if it is computed in the hint, I currently can't think of any way to check if it is correctly computed in the hint since that would require something like assert quotient*modulus + remainder = base^exponent
which is also very expensive for cairo and starknet.
But at least having uint256_mod_inv
makes sense