<jupyter_start><jupyter_text>A quick tourThe `formulas` module contains symbolic representations of elliptic curve formulas. These representations can be visualized as `sympy` expressions, but also know about their computational cost.We start with the classic Edwards addition formula. Here an Edwards curve is a curve of the form$$E(x^2 + y^2) = E + Dx^2y^2.$$Dividing both sides by $E$ gives the usual definition of Edwards curves.Here is the addition formulas in projective coordinates for this generlized Edwards curve.<jupyter_code>X, Y, Z = ed_add(Var('X1'), Var('Y1'), Var('Z1'),
                 Var('X2'), Var('Y2'), Var('Z2'),
                 Var('D'), Var('E'))
X, Y, Z<jupyter_output><empty_output><jupyter_text>The formulas know about their computational cost.<jupyter_code>cost(X, Y, Z)<jupyter_output><empty_output><jupyter_text>Note that the above function shares common subexpressions. If we compute the costs individually, we obtain a higher operation count.<jupyter_code>X.cost(), Y.cost(), Z.cost()<jupyter_output><empty_output><jupyter_text>We can have a better look at the formulas by using `sympy`<jupyter_code>[f.formula.simplify() for f in (X,Y,Z)]<jupyter_output><empty_output><jupyter_text>This might be a little hard to check, let's fix some variables, so that we obtain the classic affine formula<jupyter_code>X, Y, Z = ed_add(Var('X1'), Var('Y1'), Const(1),
                 Var('X2'), Var('Y2'), Const(1),
                 Var('d'), Const(1))
[f.formula.simplify() for f in (X,Y,Z)]<jupyter_output><empty_output><jupyter_text>We have the same for doubling (the formula does not depend on $D,E$).<jupyter_code>X, Y, Z = ed_double(Var('X'), Var('Y'), Var('Z'))
[f.formula.simplify() for f in (X,Y,Z)]<jupyter_output><empty_output><jupyter_text>IsogeniesLet's move to the interesting stuff. The isogeny formula from Section 4.3 of https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/edwardsisogenies.pdf, reads$$ψ(x,y) = \left(x\prod_{i=1}^s\frac{β_i^2 x^2 - α_i^2y^2}{β_i^2 - d^2α_i^2β_i^4x^2y^2},y\prod_{i=1}^s\frac{β_i^2 y^2 - α_i^2x^2}{β_i^2 - d^2α_i^2β_i^4x^2y^2}\right)$$where $(±α_i,β_i)$ are the coordinates of the kernel of $ψ$, and $d=D/E$.Here is a projective version (both for the point coordinates and the curve invariant) of the formula. We separate the computations that depend upon $x,y$ (the *isogeny evaluation*) from those that are independent (the *next curve*); the function returns- The invaraint of the image curve;- Costants independent of $x,y$ needed for the isogeny evaluation;- The evaluation formula.<jupyter_code>curve, consts, isog = edwards(3,
                              Var('D'), Var('E'),
                              Var('α'), Var('β'), Var('γ'),
                              Var('X'), Var('Y'), Var('Z'))
[c.formula for c in curve]
[[c.formula for c in cs] for cs in consts]
[f.formula.simplify() for f in isog]<jupyter_output><empty_output><jupyter_text>In the latter formula, $A_0, B_0, D_0$ represent the pre-computed values stored in `consts`.Let's substitute them and check that the formula is correct.<jupyter_code>isog2 = [f.formula.simplify().subs({
    'A0':consts[0][0].formula,
    'B0':consts[0][1].formula,
    'D0':consts[0][2].formula,
}) for f in isog]
isog2<jupyter_output><empty_output><jupyter_text>These formulas look correct, but to be even more convinced, let's substitute the curve equation$$X^2+Y^2-Z^2 = \frac{D X^2 Y^2}{E Z^2},$$divide all members by $Eγ^6Z^3$, and replace affine coordinates.<jupyter_code>X, Y, Z, a, b, c, D, E = sympy.symbols('X Y Z α β γ D E')
[(i.subs({X**2+Y**2-Z**2: D*X**2*Y**2/(E*Z**2)}) / (E*c**6*Z**3)).expand().subs({
    a/c: a,
    b/c: b,
    X/Z: X,
    Y/Z: Y,
    D/E: D,
}).simplify() for i in isog2]<jupyter_output><empty_output><jupyter_text>Let's now move to the costs. The *next curve* computation contains both the curve invariant and the pre-computed constants<jupyter_code>cost(*curve, *sum(consts, ()))<jupyter_output><empty_output><jupyter_text>While the *isogeny evaluation* only comprises the latter formulas<jupyter_code>cost(*isog)<jupyter_output><empty_output><jupyter_text>Obviously, these costs must be taken as upper bounds on the cost of isogeny evaluation. There are indeed (much) better formulas known for 3-isogenies of Edwards curves.Finally, let's find out how the costs increase with the degree.<jupyter_code>def get_costs(ell):
    E, c, I = edwards(ell)
    pre, consts, isog = cost(*E, *sum(c, ())), cost(*sum(c,())), cost(*I)
    return consts, pre-consts, isog

prev = [Cost()]*3
for ell in range(3, 20, 2):
    next = get_costs(ell)
    print([n-p for n, p in zip(next, prev)])
    prev = next<jupyter_output>[5S + 5M, 4S + 4M, 8A + 8M + 3S]
[9S + 15M + 7A, 2S + 2M + 0A, 6A + 8M + 0S]
[6S + 18M + 7A, 0S + 4M + 0A, 8M + 6A + 0S]
[6S + 18M + 7A, 2S + 0M + 0A, 8M + 6A + 0S]
[6S + 18M + 7A, 0S + 4M + 0A, 8M + 6A + 0S]
[6S + 18M + 7A, 0S + 2M + 0A, 8M + 6A + 0S]
[6S + 18M + 7A, 0S + 4M + 0A, 8M + 6A + 0S]
[6S + 18M + 7A, 2S + -2M + 0A, 8M + 6A + 0S]
[6S + 18M + 7A, 0S + 4M + 0A, 8M + 6A + 0S]
{'fraction_non_alphanumeric': 0.15634858044164038, 'fraction_numerical': 0.03391167192429022, 'mean_word_length': 4.35126582278481, 'pattern_counts': {'":': 0, '<': 48, '<?xml version=': 0, '>': 48, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '55147', 'license': 'MIT', 'n_tokens_mistral': 2066, 'n_tokens_neox': 1916, 'n_words': 568, 'path': 'isogenies.ipynb', 'repo_name': 'defeo/sidh-optimizer', 'size': '5072'}