Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 19: Problem 12

Show that \(-P=(x,-y)\) is in fact the inverse of \(P=(x, y)\) with respect to the addition un an elliptic curve E.

Short Answer

Expert verified
Yes, -P = (x, -y) is an inverse of P = (x, y) on an elliptic curve.

Step by step solution

01

Understanding Elliptic Curve Addition

Elliptic curves have a special addition rule. The inverse of a point \( P = (x, y) \) on the elliptic curve \( E \) is another point \( -P \) such that the result of their addition is the identity element, usually denoted as the point at infinity \( O \). The addition rule states that for a point \( P \), its inverse is \( -P = (x, -y) \) on the curve.
02

Identity Element in Elliptic Curve

The identity element for addition on an elliptic curve \( E \) is the point at infinity. This point behaves similarly to the number zero in regular addition. For a point \( P \) to have an inverse \( -P \), their sum must equal this identity element: \( P + (-P) = O \).
03

Addition Rule Verification

To verify that \( -P = (x, -y) \) is the inverse, we compute the sum of \( P = (x, y) \) and \( -P = (x, -y) \). According to the elliptic curve's addition rules, when two points have the same x-coordinate but opposite y-coordinates, they sum to the identity element \( O \).
04

Mathematical Validation

When we add \( P = (x, y) \) to \( -P = (x, -y) \), the line through these two points is vertical since they share the same x-coordinate and have opposite y-values. A vertical line intersects the elliptic curve only at these points and at infinity, confirming that their addition results in the identity element \( O \). Thus, \( P + (-P) = O \).
05

Conclusion

From the previous steps, it is confirmed that \( -P = (x, -y) \) is indeed the inverse of \( P = (x, y) \) on the elliptic curve \( E \), as \( P + (-P) = O \) holds true.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

Inverse Point
In elliptic curve algebra, each point on the curve has an inverse point. For a given point \(P = (x, y)\), its inverse is denoted by \(-P = (x, -y)\). The inverse is crucial in maintaining the group structure of elliptic curves. When you add a point to its inverse, the result is the identity element of the group, which is a foundational concept in elliptic curve operations. The geometry of elliptic curves emphasizes this property, as the line drawn through the point \((x, y)\) and its inverse \((x, -y)\) is vertical and intersects the curve at the point at infinity.
Identity Element
In the context of elliptic curves, the identity element is akin to the number zero in standard arithmetic. It is often referred to as the 'point at infinity' and is denoted by \(O\). This special point acts as the additive identity in the elliptic curve's group structure. The significance of the identity element lies in its role in the addition operation: adding any point \(P\) on the curve to the identity element \(O\) yields \(P\) itself: \(P + O = P\). Similarly, for a point \(P\) and its inverse \(-P\), their sum is the identity element: \(P + (-P) = O\).
Point Addition
Point addition on elliptic curves is a unique operation defined geometrically. When adding two points \(P = (x_1, y_1)\) and \(Q = (x_2, y_2)\) on an elliptic curve, the result is a third point \(R = (x_3, y_3)\) on the curve. If \(P\) and \(Q\) are distinct, a line is drawn through them, intersecting the curve at a third point. Reflecting this third intersection point across the x-axis gives \(R\). If \(P\) and \(Q\) have identical x-coordinates but opposite y-coordinates, they add up to the identity element, because a vertical line represents them and intersects the curve only at those two points and at the point at infinity.
Elliptic Curve Equation
An elliptic curve is defined by a specific equation of the form \[y^2 = x^3 + ax + b\] where the coefficients \(a\) and \(b\) are constants that determine the shape and properties of the curve. This equation ensures that the curve is smooth and continuous without any cusps or intersections other than those defined explicitly by the equation itself. Elliptic curves are the backbone of many cryptographic protocols, thanks to their complex algebraic structure and the difficulty of solving the Discrete Logarithm Problem on these curves. The properties of elliptic curves, such as having a defined inverse and identity element, make them particularly viable for secure encryption methods.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Fuctor the integer \(N=23802996783967\) using Pollard's \(\rho\) method, and also with the Pollard and Strassen method.

(Lenstra 1990) Consider the following special polynomial factorization task: input is a prime \(p\) and \(f \in F_{p}|x|\) of degree \(n\) and dividing \(x^{p}-x_{1}\), so that all monic irreducible factors of \(f\) in \(\mathrm{F}_{p}|x|\) are linear and distinct. Adapt the Pollard and Strassen method to find a deterministic algorithm for factoring \(f\) with \(O^{*}(n \sqrt{p})\) operations in \(\mathrm{E}_{p}\) if \(p^{2}>n\).

Three integers \((x, y, z) \in \mathbb{N}^{3}\) form a Pythagorean triple if \(x^{2}+y^{2}=z^{2}\), and a primitive Py. thagorean triple if furthermore gcd \((x, y, z)=1\). (i) Show that any Pythagorean triple is of the form \((\lambda x, \lambda y, \lambda z)\) for a primitive Pythagorean triple \((x, y, z)\) and some \(\lambda \in \mathbb{N}\), (ii) Let \(s, t \in N\) be coprime with \(s>t\) and \(s t\) even. Show that \(\left(s^{2}-t^{2}, 2 s t, s^{2}+t^{2}\right)\) is a primitive Pythagorean triple, (iii) Let \((x, y, z)\) be a primitive Pythagorean triple. Show that \(z\) is odd and either \(x\) or \(y\) is odd, but not both. Hint: Calculate modulo 4. Assume that \(x\) is odd. Prove that \((z+x) / 2\) and \((z-x) / 2\) are coprime squares, not both odd, and conclude that \((x, y, z)\) is of the form as in (ii). (iv) Use (ii) and (iii) to generate all primitive Pythagorean triples \((x, y, z)\) with \(z \leq 100\).

Let \(E\) be an elliptic curve and \(P, Q \in E\). Explain why \(P+Q=S\), where \(S\) is the third intersection point of \(E\) with the line through \(P\) and \(Q\) (sec Figure 19.6), is not a group operation.

Check that the curve \(E=\left\\{(x, y) \in \mathbb{F}_{7}^{2}: y^{2}=x^{3}+x+3\right\\}\) over E7 is nonsingular. Compute all points on it, and verify that it is cyclic and generated by \((4.1)\).
See all solutions

Recommended explanations on Computer Science Textbooks

Data Structures

Read Explanation

Cloud Services

Read Explanation

Computer Programming

Read Explanation

Algorithms in Computer Science

Read Explanation

Fintech

Read Explanation

Computer Organisation and Architecture

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free