5 ms·

> Square root is expensive https://reddit.com/r/math/comments/tc7lur/computing_square_roots_in_binary_by_hand_is/ https://reddit.com/r/math/comments/tc7lur/com

> Square root is expensive https://reddit.com/r/math/comments/tc7lur/computing_square_roots_in_binary_by_hand_is/ https://reddit.com/r/math/comments/tc7lur/computing_square_r...

eapriv 2y ago
This is not in any way related to the asymptotic time bounds discussed in the article.
deleted 2y ago
[deleted]
orlp 2y ago
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.
- eapriv 2y ago
  Even this is not in any way related to the asymptotic time bounds discussed in the article.
  - dlubarov 2y ago
    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.
- johndough 2y ago
  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%5E127+-+1%29+%3D+113338949109682836687814795709948365013+for+y 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 2y ago
    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 2y ago
      > 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.

> Square root is expensive https://reddit.com/r/math/comments/tc7lur/computing_square_roots_in_binary_by_hand_is/ https://reddit.com/r/math/comments/tc7lur/computing_square_r...

eapriv 2y ago

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

deleted 2y ago

[deleted]

orlp 2y ago

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.

eapriv 2y ago
Even this is not in any way related to the asymptotic time bounds discussed in the article.
- dlubarov 2y ago
  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.
johndough 2y ago
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%5E127+-+1%29+%3D+113338949109682836687814795709948365013+for+y 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 2y ago
  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 2y ago
    > 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.