-snip-
I'm confuse with this part : c = 3*P.x*Px*invert(2*P.y) % modulo
How get invert(2*P.y) = 0xb7e31a064ed74d314de79011c5f0a46ac155602353dc3d340fbeaeec9767a6a6 ??
-snip-
As was explained above, the inverse for
k by modulo is such value
mwhere (m*k) by modulo is equal to 1.
The best way for python is to use library
gmpy2 and its function
gmpy2.invert(k,p) which returns the inverse value to k by modulo = p. This function is the best for python and approx. 50 times faster than any other self made calculations.
For ubuntu for example you can easily install it:
sudo apt update
sudo apt install python3-gmpy2
If it is not in repository, you can download gmpy2 from here (pls, check the correct python version):
https://www.lfd.uci.edu/~gohlke/pythonlibs/#gmpyand install it in this way (example for python ver 3.7):
python -m pip install gmpy2-2.0.8-cp37-cp37m-win_amd64.whl
If you do not want to use the gmpy2 libriary (however it is the best way), you can also use this self made inversion function:
def egcd (a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
def inversion (m, n):
while m < 0:
m += n
g, x, _ = egcd (m, n)
if g == 1:
return x % n
else: print (' no inverse exist')
The function
inversion requires 2 parameters: m and n, where n is the modulo and m is the number for which you would like to calculate the inverse.