THE GARDEN

Point Compression (Elliptic Curve X-Coordinate + Parity Bit)

Updated 13 Sep 2026

• •

  What it is

  • •

    For any valid $x$-coordinate on a curve $y^2=x^3+ax+b\pmod p$, there are at most two valid $y$ values — $y$ and $p-y$ (since $(-y)^2=y^2$) — so transmitting a full point $(x,y)$ sends one redundant bit of information: given $x$ alone, a receiver can recover $y$ up to that two-way ambiguity, and only needs one extra bit (which of the two roots) to pin it down exactly. This "point compression" roughly halves the data needed to transmit a public key. When $p \equiv 3 \pmod 4$, recovering a square root of $x^3+ax+b$ is especially cheap (the same Tonelli-Shanks shortcut used elsewhere: $y \equiv (x^3+ax+b)^{(p+1)/4} \pmod p$), no general square-root algorithm needed.

• •

  When to apply

  • •

    A protocol only sends an $x$-coordinate (plus, optionally, a sign/parity bit) instead of a full $(x,y)$ pair — recover the missing $y$ via a modular square root before proceeding with any point arithmetic.

• •

  Symbols and assumptions

  • •

    For $y^2=x^3+ax+b\pmod p$ with odd prime $p$, a compressed non-infinite point records $x$ plus one bit selecting a square root $y$.

• •

  Math — step by step

  • •
    1. Compute $r=x^3+ax+b\bmod p$. A point with that x-coordinate exists only if $r$ is a quadratic residue or zero.
  • •
    2. Find a root $y$ using the applicable modular square-root algorithm. The possible roots are $y$ and $p-y$; for nonzero $y$, one is even and the other odd because $p$ is odd.
  • •
    3. Pick the root whose integer representative in $[0,p-1]$ matches the encoded parity. Verify curve membership and protocol-specific validity after decoding. At $r=0$ there is only the root 0.
• •

  Worked example

  • •

    On $y^2=x^3+2x+2\pmod{17}$, decompress $x=5$ and an odd parity bit. Compute $r=137\bmod17=1$.

  • •

    The roots are 1 and 16 since both square to 1 modulo 17. The odd root is 1, so the point is $(5,1)$; the even choice would give $(5,16)=-P$.

• •

  Python

  • •

    def lift_x(x, a, b, p):
            rhs = (x**3 + a*x + b) % p
            y = pow(rhs, (p + 1) // 4, p)   # valid when p % 4 == 3
            assert (y * y) % p == rhs
            return y, p - y
    

• •

  SageMath

  • •

    E = EllipticCurve(GF(p), [a, b])
    P = E.lift_x(GF(p)(x))   # picks one of the two valid y values automatically
    

• •

  Related

  • •

    Elliptic Curves (Group Law Basics)

  • •

    Quadratic Residue

  • •

    Tonelli-Shanks Algorithm

• •

  Cards

  • •

    Why does sending only an x-coordinate (plus one bit) fully specify a curve point?

    • •

      Any valid x has at most two matching y values (y and p−y), so a single extra bit disambiguates between them completely.

  • •

    Why doesn't it matter, for a Diffie-Hellman-style shared secret, which of the two y roots gets chosen?

    • •

      Because only the x-coordinate of the final shared point is used to derive the key, and that x-coordinate comes out identical regardless of which y value was used in the intermediate scalar multiplication.

◌ Explore connections in Graph view