search

NethermindEth / cairo-vm-go

A virtual machine for Cairo written in Go
MIT License
82 stars 49 forks source link

Sqrt implementation using modular arithmetic #338

Closed cicr99 closed 4 months ago

cicr99 commented 6 months ago

We discovered this issue while working on #322

The felt library we are using "github.com/consensys/gnark-crypto/ecc/stark-curve/fp" already has a Sqrt method but the output is not consistent with the one from the Python VM. The one from the BigInt library does not work with modular arithmetic, so we can not use that one.

We have to check if the one implemented for the uint256 library "github.com/holiman/uint256" works or we'd have to implement our own

jbmkahdeksan commented 4 months ago

Hi! I am interested in this one. Could you assign it to me?

TAdev0 commented 4 months ago

@cicr99 if my understanding is correct, "github.com/holiman/uint256" wont work as it operates on uint256 with standard arithmetic. I guess we can try to find other packages that implement sqrt method in the STARK field ?

TAdev0 commented 4 months ago

@cicr99 I think we can close the issue. sqrt method works well, simply we need to adapt its result to always get the smallest result of the square root, because this is what the python vm executes