The Jacobian form of the projective coordinates (as any other form) is not unique - for every value of Z
(other than 0) you get other X
and Y
without the actual point changing.
Thus, if you have a point in affine coordinates (X', Y')
, the pair (X', Y', 1)
is a projective representative of this point, as well as (4·X', 8·Y', 2)
, (9·X', 27·Y', 3)
, etc. The one with 1 is the easiest to create, so usually you would use this one.
While one can define (and study) elliptic curves over any field, and many mathematicians study curves defined over the complex numbers, for cryptographic uses, the coordinates are elements of some finite field. In the simplest case, we have a prime field (i.e. integers modulo a prime number), and you'll have to do addition, subtraction, multiplication and division (and probably exponentiation) in this field.
As long as Z
is not zero, you should be able to divide by Z²
- this is equivalent to multiplying by the inverse of Z², and such an element exists, and can be calculated efficiently using the extended euclidean algorithm.
This is easiest if your programming language comes with some big number library which has the necessary operations predefined, like Java's BigInteger
class (with its mod
, modPow
and modInverse
methods).
The field in question (i.e. the modulus) is part of the definition of the elliptic curve, and operations over one field give totally different results than operations in another one. So make sure you are using the right field.
You have to test all points that fulfill the equation y^2 = x^3 +x + 1 (mod 17)
. Since it is a finite field, you cannot simply take the square root on the right side.
This is how I would go about it:
a=0:16 %all points of your finite field
left_side = mod(a.^2,17) %left side of the equation
right_side = mod(a.^3+a+1,17) %right side of the equation
points = [];
%testing if left and right side are the same
%(you could probably do something nicer here)
for i = 1:length(right_side)
I = find(left_side == right_side(i));
for j=1:length(I)
points = [points;a(i),a(I(j))];
end
end
plot(points(:,1),points(:,2),'ro')
set(gca,'XTick',0:1:16)
set(gca,'YTick',0:1:16)
grid on;
Best Answer
There are a couple of issues here. First is that you have the wrong formulas: those are the formulas for the negation of the sum, or equivalently the third point of the curve that lies on the line through P and Q. Compare with the formula you linked to on Wikipedia, and you'll see that what you have for
Z.y
is the negation of the value they have.A second issue is that your formulas don't take the origin into account: if P is the inverse of Q in the group law, then P + Q will be the origin, which doesn't lie on the affine part of the curve and so can't be described as a pair of
(x, y)
coordinates. So you'll need some way to specify the origin.Let's write some code. First we need a representation for the points on the curve. We use the string
'Origin'
to represent the origin, and a simple named tuple for the points on the affine part of the elliptic curve.For demonstration purposes, we choose a particular elliptic curve and prime. The prime should be greater than
3
for the addition formulas to be valid. We also write a function that we can use to check that a particular point is a valid representation of a point on the curve. This will be useful in checking that we didn't make any mistakes in implementing the addition formulas.To do divisions modulo
p
you'll need some way to compute inverses modulop
. A simple and reasonably efficient trick here is to use Python's three-argument variant of thepow
function: by Fermat's Little Theorem,pow(a, p-2, p)
will give an inverse ofa
modulop
(provided of course that that inverse exists - that is, thata
is not divisible byp
).And finally, here are the two functions to compute negation and addition on the elliptic curve. The addition function is based directly on the formulas you gave (after correcting the sign of
Z.y
), makes use ofinv_mod_p
to perform the divisions modulop
, and does a final reduction modulop
for the computedx
andy
coordinates.We can check the code above by creating a handful of points on the curve and checking that they obey the expected arithmetic laws.