4.4 Quiz 3 ~ Solutions

Elliptic Curve Groups over F₂m

1.

Does the elliptic curve equation y² + xy = x³ + g⁵x² + g⁶ define a group over F₂3? 

Since the parameter b = 6 is not zero, the equation y² + xy = x³ + g⁵x² + g⁶ does define an elliptic curve group over F₂3.

2.

Do the points P(g³, g⁶) and Q(g⁵, g²) lie on the elliptic curve y² + xy = x³ + g²x² + g⁶ over F₂3? 

The point P(g³,g⁶) is on the elliptic curve y² + xy = x³ + g²x² + g⁶ over F₂3 since that equation holds true: 

(g⁶)² + (g³)(g⁶) = (g³)³+ g²(g³)² + g⁶

g⁵ + g² = g² + g + g⁶

(111) + (100) = (100) + (010) + (101) 

(011) = (011) 

g³ = g³

However, the point Q(g⁵)(g²) is not on the elliptic curve, since the equation disagrees: 

(g²)² + (g⁵)(g²) = (g⁵)³+ g²(g⁵)² + g⁶

g⁴ + 1 = g + g⁵ + g⁶

(110) + (001) = (001) + (111) + (101) 

(111) = (000) 

g⁵ = 0 which is false. 

3.

What are the negatives of the following elliptic curve points over F₂3? 

P(g³,g⁶) Q(g,0) R(0,g3) 

The negatives of the points are defined by (xP, xP + yP) 

-P = (g³, g³ + g⁶) = (g³, g⁴) 

-Q = (g, g + 0) = (g, g) 

-R = (0, 0 + g³) = (0, g³) 

4.

In the elliptic curve group defined by y² + xy = x³ + g²x² + g⁶ over F₂3, what is P + Q if P = (g²,g⁶) and Q = (g ⁵,g⁵)? 

P + Q = R where: 

s = (y^P - y^Q) / (x^P + x^Q) = (g⁶ + g⁵) / (g² + g⁵) = g / g³ = g-2 = g⁵ 

x^R = s² + s + x^P + x^Q + a = g³ + g⁵ +g² + g⁵ + g² = g³ 

y^R = s(x^P + x^R) + x^R + y^P = g⁵ * (g² + g³) + g⁵ + g⁶ = g⁵ * g⁵ + g³ + g⁶ = g³ + g³ + g⁶ = g⁶ 

Thus P + Q = (g³, g⁶) 

5.

In the elliptic curve group defined by y² + xy = x³ + g²x² + g⁶ over F₂3, what is 2P if P = (g³, g⁴)? 

2P = R where: 

s = x^P + y^P / 2x^P = g³ + g⁴ / g³ = g³ + g = 1 

x^R = s² + s + a = 1 + 1 + g² = g²

y^R = x^P + (s + 1) * x^R = g³ + 0 * g² = g³

Thus 2P = (g², g³) 

Next