Public key

Overview
Public key indicate to destination of funds.
The public key is private key encrypted with elliptic curve cryptography.

Public key example
0458e0d3f7cd6d54347a25523dee480199e59541d849abcd4223538397ded94
e30f4f10af03bb48a1af2051c529f4ff1a84042f59a266ba028916c54570766162b

※x04 (prefix)+ 64 digits(x-coordinate) + 64 digits(y-coordinate)

Jacobi coordinates
To present elliptic curves,use to projective coordinates system instead of the affine coordinate system.
By using projective coordinate system, division operation becomes unnecessary.
Also, use the jacobian coordinate system instead of the projective coordinate system (suitab for multiplication operating)

secp256k1 parameter
"secp256k1" is parameters of the ECDSA curve used in Bitcoin.

```P = 2**256 - 2**32 - 977
A = 0
B = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
G = (Gx, Gy)
```

Modular multiplicative inverse
Division of modular arithmetic calculate to use modular reciprocal.

```def inv(a, n):
if a == 0:
return 0
lm, hm = 1, 0
low, high = a % n, n
while low > 1:
r = high//low
nm, new = hm-lm*r, high-low*r
lm, low, hm, high = nm, new, lm, low
return lm % n
```

Jacobian coordinate
Define x, y, z as follows in elliptic curve of jacobian coordinate.

```def to_jacobian(p):
o = (p, p, 1)
return o
```

Multiplication formula
In jacobian coordinate system,scalar multiplication formula in multiplication point R(X3, Y3, Z3) of point P(X1, Y1, Z1) and point Q(X2, Y2, Z2) is as follows.

s = 4*X1*Y1^2
m = 3*X1^a*Z1^4
T = -2*s + m^2

X3 = T
Y3 = -8*Y1^4 + m(s - T)
Z3 = 2*Y1*Z1

```def jacobian_double(p):
if not p:
return (0, 0, 0)
ysq = (p ** 2) % P
S = (4 * p * ysq) % P
M = (3 * p ** 2 + A * p ** 4) % P
nx = (M**2 - 2 * S) % P
ny = (M * (S - nx) - 8 * ysq ** 2) % P
nz = (2 * p * p) % P
return (nx, ny, nz)
```

In jacobian coordinate system,addition formula in addition point R(X3, Y3, Z3) of point P(X1, Y1, Z1) and point Q(X2, Y2, Z2) is as follows.

U1 = X1*Z2^2
U2 = X2*Z1^2
S1 = Y1*Z2^3
S2 = Y2*Z1^3
H = U2 - U1
r = S2 - S1

X3 = -H^3 - 2*U1*H^2 + r^2
Y3 = -S1*H^3 + r*(U1*H^2 - X3)
Z3 = Z1*Z2*H

```def jacobian_add(p, q):
if not p:
return q
if not q:
return p
U1 = (p * q ** 2) % P
U2 = (q * p ** 2) % P
S1 = (p * q ** 3) % P
S2 = (q * p ** 3) % P
if U1 == U2:
if S1 != S2:
return (0, 0, 1)
return jacobian_double(p)
H = U2 - U1
R = S2 - S1
H2 = (H * H) % P
H3 = (H * H2) % P
U1H2 = (U1 * H2) % P
nx = (R ** 2 - H3 - 2 * U1H2) % P
ny = (R * (U1H2 - nx) - S1 * H3) % P
nz = (H * p * q) % P
return (nx, ny, nz)
```

About multiplication of elliptic curve,the most simple way to calculation method is repeated addition.
But this calculation method not realistic,because calculation amount increase exponential.

```def jacobian_multiply(a, n):
if a == 0 or n == 0:
return (0, 0, 1)
if n == 1:
return a
if n < 0 or n >= N:
return jacobian_multiply(a, n % N)
if (n % 2) == 0:
return jacobian_double(jacobian_multiply(a, n//2))
if (n % 2) == 1:
```

It's branch by remainder value obtained by dividing n to B,
「0」is executed "double(multiple)",「1」is execute "double" and "add".
Repeat until "n" became 0 or 1.

Elliptic curve coordinate of jacobian　coordinate system
Coordinate(x,y) defined as following in jacobian coordinate.
x = X / Z^2
y = Y / Z^3

```def from jacobian(p):
z = inv(p, P)
return ((p * z**2) % P, (p * Z**3) % P)
```

Get public key coordinate
Find coordinate(x, y) of public key, with argument "base point G" and "private key (decoded_private_key)".

```def fast_multiply(a, n):
return from_jacobian(jacobian_multiply(to_jacobian(a), n))
public_key = fast_multiply(G, decoded_private_key)
print(public_key)
```

Make public key
Add prefix"04" to coordinate(x, y) of public key,it's genuine " Public key".

```def encode_pubkey(pub):
return "04" + "%x"%public_key + "%x"%public_key
hex_encoded_public_key = encode_pubkey(public_key)
print (hex_encoded_public_key)
```