[orlp]

That's a square root in real arithmetic. In finite fields you don't operate over the real numbers, but the numbers within the field.

An example of a finite field is the numbers modulo a prime, like p = 2^127 - 1.

Now, please find the square root of x = 113338949109682836687814795709948365013 mod 2^127 - 1. That is, find some number y such that y * y mod (2^127 - 1) = x.

[johndough]

What is "expensive" in this context? Wolfram Alpha can solve it in a fraction of a second. https://www.wolframalpha.com/input?i=solve+y%5E2+mod+%282%5E...

    >>> x = 113338949109682836687814795709948365013
    >>> n = 1
    >>> y = 80490928931346377909947075573303248723 + 170141183460469231731687303715884105727 * n
    >>> y**2 % (2**127 - 1) == x
    True

EDIT: Looks like we got lucky here since 2^127 - 1 happens to be prime.

[Ar-Curunir]

Expensive in finite field arithmetic means much more expensive than addition and multiplication. Anyway, the sqrt here is not in terms of a specific operation, but the asymptotic cost of a particular algorithm (as in, algorithm X takes sqrt N steps)

[johndough]

> Expensive in finite field arithmetic means much more expensive than addition and multiplication.

Thanks!

> Anyway, the sqrt here is not in terms of a specific operation, but the asymptotic cost of a particular algorithm (as in, algorithm X takes sqrt N steps)

Yes, I am aware. I wanted to understand the side-tracked question anyway.

[eapriv]

Even this is not in any way related to the asymptotic time bounds discussed in the article.

[dlubarov]

Right - in case it's not clear to all, the square root metric Vitalik mentions is about measuring both proof size and verifier complexity. Neither the prover nor the verifier is doing any square root computations.