Quote from: flipperfish on December 09, 2017, 10:58:38 AM

What is the meaning of the offset? Why is it needed? Other implementations seem to be fine without it.
What are the mathematical foundations? Why does x + offset still result in the same y (or does it?)?
When calculating y^2, why is the coefficent a multiplied by x^2 instead of just x, like in the basic elliptic curve equation?
Could this be a bug, that has not yet been discovered, because a is 0 in secp256k1?

Code:

def ECC_YfromX(x,curved=curve_secp256k1, odd=True):
   _p = curved.p()
   _a = curved.a()
   _b = curved.b()
   for offset in range(128):
   Mx = x + offset
   My2 = pow(Mx, 3, _p) + _a * pow(Mx, 2, _p) + _b % _p
   My = pow(My2, (_p+1)//4, _p )

   if curved.contains_point(Mx,My):
   if odd == bool(My&1):
   return [My,offset]
   return [_p-My,offset]
   raise Exception('ECC_YfromX: No Y found')

I'm glad for any help or pointers in the right direction...

Quite an interesting find.
You are right, it does seem to be a "bug" to have a*x² in there. It should be a*x, but would be even better if there were no "a" at all, because as you said a=0 in the curve bitcoin uses (y²=x³+7)

Also interesting to have _b % _p at the end. Why take a mod of curve parameter b? How could it ever be bigger than p? It is a curve parameter that never changes.

Maybe Electrum devs want to be prepared for bitcoin changing the curve it uses ?? (never going to happen)
It is not very efficient to do 128 times "_a * pow(Mx, 2, _p)" and "_b % _p" for no reason, when the numbers are as big as they are (256bit).

Also as you said. the offset is quite confusing. but both the "My" and offset are returned to the calling function and sent to Point() in the end, and Point() is an imported function (from ecdsa.ellipticcurve import Point) And I did not look what it does with the offset value.

One more thing that confuses me is the line:

Code:

My = pow(My2, (_p+1)//4, _p )

That is an interesting way to take a squareroot in finite field. I know sqrt is a heavy operation in finite field, but never seen it taken like that. Could that be what is behind the whole offset thing... an easier way to find a sqrt?