More MNT and pairing-friendly elliptic curves

Definitions and mathematical statement

Let $E/{\mathbb{F}}_q$ be an elliptic curve and let $r\nmid q$ be a large prime dividing its order. Write \[ \#E({\mathbb{F}}_q)=h r, \qquad k=\operatorname{ord}_r(q) =\min\{j\ge1:r\mid q^j-1\}. \] Here $h$ is the cofactor and $k$ the embedding degree for the chosen subgroup order $r$. The ratio $\rho=\log q/\log r$ is another usual efficiency parameter, but no target $\rho$ is stated in the source.

Lange's programme asks for additional MNT/MNT-like pairing-friendly constructions: more families, usable larger $k$, and smaller cofactors under the intended parameter tradeoffs. A family must produce actual finite fields and elliptic curves with the indicated order/divisibility and embedding-degree conditions. Polynomial parameter identities alone do not prove infinitely many simultaneous prime parameter values. Usability requires specified subgroup/field sizes and computational criteria; it is not a mathematical bound supplied by the word usable.

The classical strict MNT terminology is associated with prime-order constructions at $k=3,4,6$. In a prime-order setting $h=1$, already the smallest positive cofactor. Thus a request for larger degrees and smaller cofactors must either concern a broader MNT-like class or compare different non-prime-order constructions; the exact intended class/baseline is missing. No new degree threshold or universal cofactor optimum is invented.

The supplied research summary reports substantial families, mentioning MNT, BN at $k=12$, BLS, Freeman at $k=10$, and KSS. It describes the 2006 programme as largely achieved for many degrees, not as a complete classification or an optimum for every degree/size. Those reported successes do not supply exact guarantees for every named family.

Short English statement

Construct further pairing-friendly elliptic-curve families with explicitly controlled embedding degrees and cofactors. Clarify whether MNT is used strictly or for a broader class, since prime-order MNT curves already have cofactor one.

Sources

• Local UnsolvedMath registry, permanent ID $8800053$, exact source code catalogue entry, "More MNT and pairing-friendly elliptic curves." Proposer Tanja Lange.
• IPAM Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6239, recorded PDF page 41, printed slide 39; https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Recorded access 2026-07-29; pdf-and-legacy-ppt visual-audit extraction.
• Supplied PARTIAL-PROGRESS research summary names Miyaji--Nakabayashi--Takano (2001), Barreto--Naehrig (2005), Barreto--Lynn--Scott, Freeman, and KSS, without complete publication references or precise parameter/cost hypotheses.