All elliptic curves can be written in Weierstrass form

y² = x³ + ax + b

with a few exceptions [1].

Montgomery elliptic curves have the form

B y² = x³ + A x² + x

and twisted Edwards curves have the form

a x² + y² = 1 + d x² y²

Every Montgomery curve has a twisted Edwards form, and vice versa, but not all curves have a Montgomery or twisted Edwards form.

Converting coefficients

Here is Python code for converting coefficients between the various forms. See [2].

def Montgomery_to_Twisted_Edwards(B, A, p):
    # By^2 = x^3 + Ax^2 + x
    a = ((A + 2)*pow(B, -1, p)) % p
    d = ((A - 2)*pow(B, -1, p)) % p          
    return a, d

def Twisted_Edwards_to_Montgomery(a, d, p):
    # ax^2 + y^2 = 1 + d x^2 y^2
    x = pow(a - d, -1, p)
    B = (4*x) % p
    A = (2*(a + d)*x) % p
    return B, A

def Montgomery_to_Weierstrass(B, A, p):
    # By^2 = x^3 + Ax^2 + x
    a = (B**2 * (1 - A**2*pow(3, -1, p))) % p
    b = (B**3 * (2*A**3 - 9*A) * pow(27, -1, p)) % p
    return a, b

Tiny Jubjub curve

The code below confirms that the forms of the Tiny Jubjub curve (TJJ) given in the previous post are consistent.

# Twisted Edwards definition
a, d, p = 3, 8, 13

B, A = Twisted_Edwards_to_Montgomery(a, d, p)
assert(B == 7)
assert(A == 6)

wa, b = Montgomery_to_Weierstrass(B, A)
assert(wa == 8)
assert(b == 8)

Baby Jubjub

I was looking up the Baby Jubjub curve and found incompatible definitions. All agreed that the field is integers modulo the prime

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

and that the Montgomery form of the curve is

y² = x³ + 168698 x² + x

But the sources differed in the twisted Edwards form of the curve. The code above shows that a correct twisted Edwards form is the one given in [2]:

168700 x² + y² = 1 + 168696 x² y²

Now it is possible to find multiple Edwards forms for a given Montgomery form, so an alternate form is not necessarily wrong. But when I converted both to Weierstrass form and computed the j-invariant, the results were different, and so the curves were not equivalent.

Related posts

• Curve25519 and Ed25519
• Monero’s elliptic curve
• Addition on Edwards curves

[1] All elliptic curves can be written in Weierstrass form as long as the underlying field does not have characteristic 2 or 3. Cryptography is primarily interest in fields whose characteristic is a gargantuan prime, not 2 or 3.

[2] Marta Bellés-Muñoz, Barry Whitehat, Jordi Baylina, Vanesa Daza, and Jose Luis Muñoz-Tapia. Twisted edwards elliptic curves for zero-knowledge circuits. Mathematics, 9(23), 2021.

Suppose you have an elliptic curve

y² = x³ + ax + b

over a finite field F_p for prime p. How many points are on the curve?

Brute force

You can count the number of points on the curve by brute force, as I did here. Loop through each of the p possibilities for x and for y and count how many satisfy the curve’s equation, then add one for the point at infinity. This is the most obvious but slowest approach, taking O(p²) time.

Here’s a slight variation on the code posted before. This time, instead of passing in the function defining the equation, we’ll assume the curve is in the form above (short Weierstrass form) and pass in the parameters a and b. This will work better when we refine the code below.

def order(a, b, p):
    c = 1 # The point at infinity
    for x in range(p):
        for y in range(p):
            if (y**2 - x**3 - a*x - b) % p == 0:
                c += 1
    return c

Better algorithm

A better approach would be to loop over the x values but not the y‘s. For each x, test determine whether

x³ + ax + b

is a square mod p by computing the Legendre symbol. This takes O(log³ p) time [1], and we have to do it for p different values of x, so the run time is O(p log³ p).

from sympy import legendre_symbol

def order2(a, b, p):
    c = 1 # The point at infinity
    for x in range(p):
        r = x**3 + a*x + b
        if r % p == 0:
            c += 1 # y == 0
        elif legendre_symbol(r, p) == 1:
            c += 2
    return c

Schoof’s algorithm

There’s a more efficient algorithm, Schoof’s algorithm. It has run time O(log^k p) but I’m not clear on the value of k. I’ve seen k = 8 and k = 5. I’ve also seen k left unspecified. In any case, for very large p Schoof’s algorithm will be faster than the one above. However, Schoof’s algorithm is much more complicated, and the algorithm above is fast enough if p isn’t too large.

Comparing times

Let’s take our log to be log base 2; all logs are proportional, so this doesn’t change the big-O analysis.

If p is on the order of a million, i.e. around 2²⁰, then the brute force algorithm will have run time on the order of 2⁴⁰ and the improved algorithm will have run time on the order of 2²⁰ × 20³ ≈ 2³³. If k = 8 in Schoof’s algorithm, its runtime will be on the order of 20⁸ ≈ 2³⁴, so roughly the same as the previous algorithm.

But if p is on the order of 2²⁵⁶, as it often is in cryptography, then the three algorithms have runtimes on the order of 2⁵¹², 2²⁷⁰, and 2⁶⁴. In this case Schoof’s algorithm is expensive to run, but the others are completely unfeasible.

[1] Note that log^k means (log q)^k, not log applied k times. It’s similar to the convention for sine and cosine.

The previous post gave two examples of pairs of elliptic curves in which

#(E / F_p) = q

and

#(E / F_q) = p.

That is, the curve E, when defined over integers mod p has q elements, and when defined over the integers mod q has p elements.

Pairs

Silverman and Stange [1] call this arrangement an amicable pair. They found a small pair of amicable elliptic curves:

y² = x³ + 2

with p and q equal to 13 and 19. They give many other examples, but this one is nice because it’s small enough for hand calculations, unlike the curves mentioned in the previous post that had on the order of 2²⁵⁴ elements.

Cycles

More generally, amicable curve pairs are amicable curve cycles with cycle length 3. Silverman and Stange give this example of a cycle of length 3:

y² = x³ − 25x − 8

with (p, q, r) = (83, 79, 73). That is, the curve over F₈₃ has 79 elements, the curve over F₇₉ has 73 elements, and the curve over F₇₃ has 83 elements.

The authors show that there exist cycles of every length m ≥ 2.

Application

Why does any of this matter? Cycles of elliptic curves are useful in cryptography, specifically in zero-knowledge proofs. I hope to go into this further in some future post.

Confirmation

The curves mentioned above are small enough that we can compute the orders of the curves quickly by brute force. The following Python code confirms the claimed orders above.

def order(eqn, p):
    c = 1 # The point at infinity
    for x in range(p):
        for y in range(p):
            if eqn(x, y) % p == 0:
                c += 1
    return c

eqn = lambda x, y: y**2 - x**3 - 2
assert( order( eqn, 13) == 19 )
assert( order( eqn, 19) == 13 )

eqn = lambda x, y: y**2 - x**3 + 25*x + 8
assert( order( eqn, 83) == 79 )
assert( order( eqn, 79) == 73 )
assert( order( eqn, 73) == 83 )

Related posts

• What is an elliptic curve?
• Elliptic curve used in Bitcoin and Ethereum
• Legendre and Ethereum

[1] Joseph H. Silverman and Katherine E. Stange. Amicable pairs and aliquot cycles for elliptic curves. Experimental Mathematics, 20(3):329–357, 2011.