# Standard Montgomery curves over prime field

Is there some source of standard, vetted, efficient Montgomery elliptic curves over prime field?

I'm looking for curves $$B\,y^2\equiv x^3+A\,x^2+x\pmod p$$ engineered for efficient computation of scalar multiplication with $$X/Z$$ coordinates and Montgomery ladder, which if I'm not mistaken is faster with small* $$A_{24}=(A+2)/4$$, because there's a multiplication by $$A_{24}$$ in the point doubling formula.

Ideally I'm looking for a curve with cofactor 4 over some 256-bit prime field, which would give about one extra bit of security compared to Curve25519 (255-bit $$p$$, cofactor $$8$$, $$A_{24}=121665$$, which is not quite optimum for $$X/Z$$ computations).

* Incidentally: what's the lowest possible $$|A_{24}|$$ for a secure Montgomery curves over prime field when we can choose $$p$$ freely?

• Jan 29 at 15:21
• The sect283k1 and set239k1 curves are over a binary field, thus do not fit my need. Ed-255-mers and Ed-254-mont are Edwards curves (with respectively pseudo-Mersenne primes and Montgomery-friendly primes for the prime field), which I think are bi-rationally equivalent to Montgomery curves, but I believe are not optimized for Montgomery coordinates X/Z.
– fgrieu
Jan 29 at 18:05
• Just made a simple search to help you. Didn't dive a lot. Happy that you got answer. Jan 30 at 21:51

The Montgomery form of numsp256t1 matches those criteria, even if calling it "standard" is a bit of a stretch.

NUMS (Nothing Up My Sleeve) curves were curves proposed by Microsoft (Costello at al.) The curve generation algorithm and the resulting curves was proposed back in the days of the elliptic curve controversy against NIST.

They fit all known security requirements, and they were proposed in Short Weierstrass and Edwards form.

In particular numsp256t1 is defined over a 256-bit prime field (with $$p= 2^{256} - 189$$) an Edwards curve with cofactor=$$4$$. Using a 4-degree isogeny following proposition 2 of this paper it can be brought into Montgomery format, maintaining the security properties.

The resulting Montgomery curve has $$B=1$$, $$A=61370$$ (which gives $$A_{24}=15343$$). Its cardinality is $$4 * 28948022309329048855892746252171976963404671476872247083542990644359122995957$$ where $$28948022309329048855892746252171976963404671476872247083542990644359122995957$$ is a prime of bit-size $$255$$.

• Great references! I'm however less than perfectly happy with $A_{24}=15343$. By choosing a different prime, wouldn't it be possible to lower $A_{24}$ (which is used as multiplier at each point doubling)? I added an incidental question about how low $|A_{24}|$ can be.
– fgrieu
Jan 30 at 16:57
• Yes of course, BUT the difference choice of the prime $p=2^{256} -c$ will probably result in a larger $c$, that might effect you more in performances than a smaller $A_{24}$. Also, 15343 is smaller than Curve25519's 121665. Jan 31 at 9:59
• [updated] It's true that for low $|A_{24}|$ the prime $p$ would have to be tweaked more (in it's low-order bits, or it's high order bits is we optimize $p$ for Montgomery modular reduction). But I think any tweak that fits a limb/word costs the same as $189$ (in software). I think that $A_{24}=-2$ leads to interesting Montgomery curve, which would I think be faster than $A_{24}=15343$, in both hardware and software.
– fgrieu
Jan 31 at 14:26
• @fgrieu I am not sure I understand your point. I would say that "any $A_{24}$ that fits a limb/word costs the same as $-2$". What am I missing ? Jan 31 at 16:00
• $A_{24}$ is used in a field computation like $W:=A_{24}\,U+V$ (with reduction mod $p$ that can be deferred to some degree). When $A_{24}=-2$ it seems possible to use shift or addition instead of multiplication, which can be faster: mulx rax,rcx,rdx reportedly has 4 cycles latency. Subtraction is less nice than addition but I think I see how to get rid of it.
– fgrieu
Jan 31 at 17:02