Problem 922: Elliptic Curve Point Counting

Mathematical Foundation

Theorem 1 (Point Counting Formula). Let $E: y^2 = f(x) = x^3 + ax + b$ be an elliptic curve over $\mathbb{F}_p$ (with $p > 3$ and $4a^3 + 27b^2 \not\equiv 0 \pmod{p}$). Then

where $\left(\frac{\cdot}{p}\right)$ is the Legendre symbol.

Proof. The point at infinity $\mathcal{O}$ contributes 1. For each $x \in \mathbb{F}_p$, the equation $y^2 = f(x)$ has:

• 2 solutions if $f(x)$ is a nonzero quadratic residue (Legendre symbol $= +1$),
• 1 solution if $f(x) = 0$ (Legendre symbol $= 0$),
• 0 solutions if $f(x)$ is a quadratic non-residue (Legendre symbol $= -1$).

In all cases the count is $1 + \left(\frac{f(x)}{p}\right)$. Summing over all $x$:

Theorem 2 (Hasse Bound). For any elliptic curve $E$ over $\mathbb{F}_p$:

Proof. (Sketch.) The Frobenius endomorphism $\phi: (x,y) \mapsto (x^p, y^p)$ satisfies the characteristic equation $\phi^2 - a_p \phi + p = 0$ in $\mathrm{End}(E)$, where $a_p = p + 1 - |E(\mathbb{F}_p)|$ is the trace of Frobenius. The eigenvalues of $\phi$ are complex conjugates of absolute value $\sqrt{p}$ (by the Riemann Hypothesis for curves over finite fields, proved by Hasse for genus 1). Hence $|a_p| \leq 2\sqrt{p}$. $\square$

For $p = 1009$: $2\sqrt{1009} \approx 63.56$, so $|E(\mathbb{F}_p)| \in [947, 1073]$.

Lemma 1 (Non-singularity). The curve $E: y^2 = x^3 + x + 1$ over $\mathbb{F}_{1009}$ is non-singular.

Proof. The discriminant is $\Delta = -16(4a^3 + 27b^2) = -16(4 + 27) = -16 \cdot 31$. Since $\gcd(31, 1009) = 1$ and $\gcd(16, 1009) = 1$, we have $\Delta \not\equiv 0 \pmod{1009}$. $\square$

Theorem 3 (Euler’s Criterion). For an odd prime $p$ and $a \not\equiv 0 \pmod{p}$:

where the result is interpreted in $\{-1, 0, 1\}$ by mapping $p - 1 \mapsto -1$.

Proof. Since $\mathbb{F}_p^*$ is cyclic of order $p - 1$, write $a = g^k$ for a generator $g$. Then $a^{(p-1)/2} = g^{k(p-1)/2} = (\pm 1)$ depending on the parity of $k$. This is $+1$ exactly when $k$ is even, i.e., when $a$ is a quadratic residue. $\square$

Editorial

Count points on E: y^2 = x^3 + x + 1 over F_p, p = 1009. Key ideas:. We verify non-singularity. We then else. Finally, euler’s criterion.

Pseudocode

Verify non-singularity
else
Euler's criterion
else
Hasse bound verification

Complexity Analysis

• Time: $O(p \log p)$. The loop iterates $p$ times, each iteration performing one modular exponentiation in $O(\log p)$ via binary exponentiation.
• Space: $O(1)$ auxiliary space (only running accumulators).

For $p = 1009$, this is approximately $10^4$ operations — microseconds on modern hardware.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 922: Elliptic Curve Point Counting
 *
 * Count |E(F_p)| for E: y^2 = x^3 + x + 1, p = 1009.
 *
 * Formula: |E| = 1 + p + sum_{x=0}^{p-1} Legendre(f(x), p)
 *   where f(x) = x^3 + x + 1.
 *   Legendre(a, p) = a^{(p-1)/2} mod p, mapped to {-1, 0, 1}.
 *
 * Hasse's theorem: |p + 1 - |E|| <= 2*sqrt(p) ~ 63.6 for p=1009.
 * Non-singularity: 4*1 + 27*1 = 31 != 0 mod 1009.
 *
 * Also implements group law for verification.
 */

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int count_points(int a, int b, int p) {
    int count = 1; // point at infinity
    int half = (p - 1) / 2;
    for (int x = 0; x < p; x++) {
        long long rhs = ((long long)x * x % p * x % p + (long long)a * x % p + b) % p;
        if (rhs < 0) rhs += p;
        int leg;
        if (rhs == 0) {
            leg = 0;
        } else {
            leg = (int)power(rhs, half, p);
            if (leg == p - 1) leg = -1;
        }
        count += 1 + leg;
    }
    return count;
}

int main() {
    int p = 1009;
    int answer = count_points(1, 1, p);
    cout << answer << endl;

    // Verify Hasse bound
    int trace = p + 1 - answer;
    assert(abs(trace) <= 2 * (int)sqrt((double)p) + 1);

    // Verify non-singularity: 4a^3 + 27b^2 = 31 != 0 mod p
    assert((4 + 27) % p != 0);

    // Cross-check with brute force for p=23
    int p2 = 23;
    int leg_count = count_points(1, 1, p2);
    int brute = 1;
    for (int x = 0; x < p2; x++) {
        int rhs = (x * x % p2 * x % p2 + x + 1) % p2;
        if (rhs < 0) rhs += p2;
        for (int y = 0; y < p2; y++)
            if (y * y % p2 == rhs) brute++;
    }
    assert(leg_count == brute);

    return 0;
}

"""
Problem 922: Elliptic Curve Point Counting

Count points on E: y^2 = x^3 + x + 1 over F_p, p = 1009.

Key ideas:
    - |E(F_p)| = 1 + p + sum of Legendre symbols (f(x)/p).
    - Legendre symbol via Euler's criterion: a^{(p-1)/2} mod p.
    - Hasse bound: |p+1 - |E|| <= 2*sqrt(p) ~ 63.6.
    - Non-singularity: 4a^3 + 27b^2 = 31 != 0 mod 1009.

Methods:
    1. Legendre symbol summation (O(p log p))
    2. Brute-force (x,y) enumeration (O(p^2))
    3. Group law verification
"""

from math import isqrt

def count_points_legendre(a: int, b: int, p: int) -> int:
    """Count |E(F_p)| for y^2 = x^3 + ax + b via Legendre symbols."""
    count = 1  # point at infinity
    half = (p - 1) // 2
    for x in range(p):
        rhs = (pow(x, 3, p) + a * x + b) % p
        if rhs == 0:
            leg = 0
        else:
            leg = pow(rhs, half, p)
            if leg == p - 1:
                leg = -1
        count += 1 + leg
    return count

def count_points_brute(a: int, b: int, p: int) -> int:
    """Count by checking all (x,y) pairs."""
    count = 1  # point at infinity
    for x in range(p):
        rhs = (pow(x, 3, p) + a * x + b) % p
        for y in range(p):
            if (y * y) % p == rhs:
                count += 1
    return count

# Elliptic curve group operations
def ec_add(P, Q, a, p):
    """Add two points on y^2 = x^3 + ax + b over F_p."""
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return None  # P + (-P) = O
    if x1 == x2:
        lam = (3 * x1 * x1 + a) * pow(2 * y1, p - 2, p) % p
    else:
        lam = (y2 - y1) * pow(x2 - x1, p - 2, p) % p
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

# Solve
p = 1009
answer = count_points_legendre(1, 1, p)

# Verify non-singularity
assert (4 * 1 + 27 * 1) % p != 0

# Verify Hasse bound
trace = p + 1 - answer
assert abs(trace) <= 2 * isqrt(p) + 1

# Verify against brute force for small prime
p_small = 23
assert count_points_legendre(1, 1, p_small) == count_points_brute(1, 1, p_small)

print(answer)