snarkVM
snarkVM copied to clipboard
[Feature] Integer square root
This PR introduces:
- console and circuit implementations of integer square root.
Resource: https://en.wikipedia.org/wiki/Integer_square_root
TODO:
- [ ] Integrate into opcodes
- [ ] Guard by consensus version
- [ ] Soundness analysis
- [ ] Optimizations
(x + 1)^2 > y ==> x^2 + 2x + 1 > y ==> 2x + 1 > y - x^2 (checked subtraction)x^2 <= y ==> 0 <= y - x^2