sqrt!
Element-wise field square root, computed statically or constrained as a witness. Integer and field arithmetic
sqrt! v
Computes a square root in the field for every element of v. Of the two roots r and p - r the smaller canonical integer is returned, and the root of zero is zero.
For a static v the roots are computed at compile time. For a witness v each root is a new witness entry constrained by one row root * root = v. That row fixes the root only up to sign: a prover may supply either root, so constrain the sign (e.g. a range check) if your program depends on which one it gets.
Arguments
v- Static or witness vector of quadratic residues.
Returns
A vector of roots the length of v: static for a static input, witness otherwise. Expression form only.
Constraints
None for a static input. A witness input adds one row and one witness entry per element.
Example
(let v) sqrt! v
(let x) static r = sqrt! 25 x * r
Notes
A non-residue has no root and panics inside the compiler (legendre symbol is not 1), for witness inputs during witness computation. In the milli field half of the nonzero elements are non-residues, so only take roots of values known to be squares. For the integer square root of a static value use sqrt_ceil!.