cairo-lang icon indicating copy to clipboard operation
cairo-lang copied to clipboard

uint256_mod_inv standard function with a hint

Open dragan2234 opened this issue 2 years ago • 0 comments

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


This change is Reviewable

dragan2234 avatar Jan 26 '23 00:01 dragan2234