1. a. The curve is Y^2 = X^3 - 2X + 4.
P = (x1, y1) = (0,2), Q = (x2, y2) = (3,-5).
To compute P + Q, first compute the line connecting P and Q.
The slope of the line is \lambda = -7/3.
The line itself is y = -7/3 x + 2.
P + Q = (x3, y3) where x3 = \lambda^2 - x1 - x2 = 49/9 - 0 - 3 = 22/9
y3 = 100/27.
P + Q = (22/9, 100/27).
To compute 2P, the slope of the tangent at P is
\lambda = (3x_1^2 + A)/2y_1 = -1/2
The tangent line is y = -1/2 x + 2.
2P = (x3, y3) where x3 = \lambda^2 - 2x_1 = 1/4 and y3 = -(-1/8 + 2) = - 15/8.
2P = (1/4, -15/8)
To compute 2Q, the slope of the tangent at Q is
\lambda = (3x_1^2 + A)/2y_1 = -5/2
The tangent line is y = -5/2 x + 5/2.
2Q = (x3, y3) where x3 = \lambda^2 - 2x_1 = 1/4 and y3 = -(-5/8 + 5/2) = -15/8.
2Q = (1/4, -15/8)
[ In all the above, a penalty of -1 point each for not inverting the sign of the y coordinate ]
[ Calculation mistakes get either -1 or -2 points, depending on how severe they are ]
1. b. y^2 = x^3 + 1 has p + 1 points.
The condition on p means that the mapping x -> x^3 mod p is a one-to-one mapping over Z_p.
Therefore, so is the mapping x -> x^3 + 1. In other words, every x maps to a distinct x^3 + 1.
Since half the numbers in Z_p* are squares, there are (p-1)/2 numbers x such that x^3 + 1 is a
square in Z_p*, say y^2. For each such x, there are two points on the curve, namely (x,y) and (x,-y).
There is an x such that x^3 + 1 = 0 mod p. This gives us another point (x,0). Finally, we have
the point at infinity \mathcal{O}.
Together, we have 2*(p-1)/2 + 1 + 1 = p + 1 points on the curve.
2. Let us try a solution for secret sharing with "weights". The intuition is that the profs and
TAs are not created equal. Whereas you need 3 profs to reconstruct, you only need 2 TAs! So, why
not give the profs and TAs different number of shares?
That is, we will do a t-out-of-N secret sharing of K, for some t and N. We will give
p shares to each of the profs and k shares to each of the TAs. We need:
3p + 2k = N
[ The total number of shares is N ]
3p >= t
[ 3 profs together can reconstruct ]
2k >= t
[ 2 TAs can reconstruct ]
p + k >= t
[ 1 TA + 1 prof can reconstruct ]
2p < t
[ 2 profs cannot reconstruct ]
k < t
[ a TA alone cannot reconstruct ]
What are some numbers that satisfy these constraints?
Let p = 1, k = 2, t = 3.
Check that this satisfies all the five inequalities above.
This gives us N = 7.
The solution then is this:
Do a 3-out-of-7 secret sharing. (For example, choose a random polynomial
F(x) = aX^2 + bX + K mod q and let the shares be F(1), F(2),..., F(7).)
Give F(1), F(2) and F(3) one each to the three profs.
Give F(4) and F(5) to the first TA, and F(6) and F(7) to the second TA.