[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.