4 ms·
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%2
by 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 agoExpensive 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.