About the problem
This problem asks for an improved algorithm to do the following: given a pair \((p, N)\), where \(p\) is a prime number and \(N\) is an integer in the Hasse bound: \(p + 1 -2\sqrt{p} \leq N \leq p + 1 + 2\sqrt{p},\) find an elliptic curve \(E/\mathbb{F}_p\) such that the total number of points \(\#E(\mathbb{F}_p)\) equals \(N\).
There is an existing algorithm to solve this problem, called the Complex Multiplication (CM) method, but the CM method is inefficient for large \(p\). More specifically, for \(t = p+1-N\) and \(D\) the squarefree part of \(t^2 - 4p\), then elliptic curves with \(N\) points can be constructed by finding roots modulo \(p\) of the Hilbert class polynomial \(H_D\). Unfortunately, the bit size of \(H_D\) is approximately \(\lvert D \rvert \log \lvert D \rvert\), so when \(p\) is of cryptographic size the method is usually impractical.
A solution to this problem would be interesting for a few reasons. First, it could lead to a faster certificate to show that a number is prime (see here). Second, there could be applications in cryptography, in zero-knowledge proof schemes and other cryptographic algorithms.
The verifier for this problem tests the algorithm on a finite set of pairs \((p, N)\) and checks that the algorithm returns the correct answer in a short amount of time. It is expected that new ideas are needed for a submitted algorithm to succeed at solving this problem quickly.
Prompt
# Elliptic curves with a prescribed point count
Given a prime $p$ and a target $N$ in the Hasse interval
($|N - (p+1)| < 2\sqrt{p}$), construct an elliptic curve $E/\mathbb{F}_p$ with
exactly $\#E(\mathbb{F}_p) = N$. The verifier deliberately chooses $(p, N)$ so that
the CM discriminant $D = (p+1-N)^2 - 4p$ has a large squarefree part.
## Submission format
You will submit a single Python file. It may use `sage`. When submitting, you may
also constrain the challenges your program will receive by specifying at most one
of the following (noting the "interestingness" criterion below):
| parameter | meaning |
|-----------|---------|
| `s` | $p$ chosen with $2^s < p < 2^{s+1}$; $s$ between 7 and 300 |
| `p` | you fix the prime $p$ (must be prime, $\ge 128$) |
| `N` | you fix the cardinality $N$ ($\ge 128$); the verifier picks a compatible $p$ |
If none is specified, each challenge is a random instance over the whole range.
## Protocol
The verifier repeatedly:
1. picks a challenge $(p, N)$ subject to your constraint;
2. runs your program in a fresh process with `p` and `N` in decimal as the two
command-line arguments, using the same Python interpreter that runs the verifier —
here `/opt/conda/bin/python your_submission.py <p> <N>`. That is Sage's Python,
which is *not* the `python` on your `PATH`, so test your submission with the full
path or `import sage` will fail;
3. reads the last non-empty line of your program's stdout as your answer: the
$a$-invariants of a curve $E/\mathbb{F}_p$ with $\#E = N$, either `a b` (for
$y^2 = x^3 + ax + b$) or `a b c d e` (general Weierstrass form), space-separated.
Earlier lines of stdout are ignored, so printing progress information is fine.
Each invocation of your program has its own time limit; if you want to reuse expensive
precomputation across challenges, cache it in a file.
## Scoring
A solution counts when the returned curve really has $N$ points. Only solves with
$p$ above the size threshold of $2^{80}$ are "interesting".
If there is sufficient time available, your program may be run on multiple challenges.
It will be considered correct if it answers an "interesting" challenge correctly within
the available time.
## Example submission format
```
import sys
from sage.all import ZZ
p, N = ZZ(sys.argv[1]), ZZ(sys.argv[2])
curve = find_curve(p, N) # you must implement this!
# Your answer: the a-invariants of the elliptic curve,
# either as a pair a,b for y^2 = x^3 + ax + b
# or a 5-tuple a,b,c,d,e for y^2 + axy + cy = x^3 + bx^2 + dx + e
print(" ".join(str(a) for a in curve))
```