gen/ec: code generation for efd formulae

[mmcloughlin]

Generate Go code to compute a given EFD formula.

Related #41 #29 #38 #55

[mmcloughlin]

Formulae required for P-256 #55. Note that operations with arrows <- will need special handling.

g1p/shortw/jacobian-3/addition/add-2007-bl:

    Z1Z1 = Z1^2
    Z2Z2 = Z2^2
    U1 = X1*Z2Z2
    U2 = X2*Z1Z1
    t0 = Z2*Z2Z2
    S1 = Y1*t0
    t1 = Z1*Z1Z1
    S2 = Y2*t1
    H = U2-U1
    t2 = 2*H
    I = t2^2
    J = H*I
    t3 = S2-S1
    r = 2*t3        <-
    V = U1*I
    t4 = r^2
    t5 = 2*V        <-
    t6 = t4-J
    X3 = t6-t5
    t7 = V-X3
    t8 = S1*J
    t9 = 2*t8       <-
    t10 = r*t7
    Y3 = t10-t9
    t11 = Z1+Z2
    t12 = t11^2
    t13 = t12-Z1Z1
    t14 = t13-Z2Z2
    Z3 = t14*H


g1p/shortw/jacobian-3/addition/add-1998-cmo:

    t0 = Z2^2
    U1 = X1*t0
    t1 = Z1^2
    U2 = X2*t1
    t2 = Z2^3       <-
    S1 = Y1*t2
    t3 = Z1^3       <-
    S2 = Y2*t3
    H = U2-U1
    r = S2-S1
    t4 = r^2
    t5 = H^3        <-
    t6 = H^2
    t7 = U1*t6
    t8 = 2*t7       <-
    t9 = t4-t5
    X3 = t9-t8
    t10 = H^2
    t11 = U1*t10
    t12 = t11-X3
    t13 = H^3       <-
    t14 = S1*t13
    t15 = r*t12
    Y3 = t15-t14
    t16 = Z2*H
    Z3 = Z1*t16

g1p/shortw/jacobian-3/addition/madd-2007-bl:

    Z1Z1 = Z1^2
    U2 = X2*Z1Z1
    t0 = Z1*Z1Z1
    S2 = Y2*t0
    H = U2-X1
    HH = H^2
    I = 4*HH        <-
    J = H*I
    t1 = S2-Y1
    r = 2*t1        <-
    V = X1*I
    t2 = r^2
    t3 = 2*V        <-
    t4 = t2-J
    X3 = t4-t3
    t5 = V-X3
    t6 = Y1*J
    t7 = 2*t6       <-
    t8 = r*t5
    Y3 = t8-t7
    t9 = Z1+H
    t10 = t9^2
    t11 = t10-Z1Z1
    Z3 = t11-HH

g1p/shortw/jacobian-3/doubling/dbl-2001-b:

    delta = Z1^2
    gamma = Y1^2
    beta = X1*gamma
    t0 = X1-delta
    t1 = X1+delta
    t2 = t0*t1
    alpha = 3*t2    <-
    t3 = alpha^2
    t4 = 8*beta     <-
    X3 = t3-t4
    t5 = Y1+Z1
    t6 = t5^2
    t7 = t6-gamma
    Z3 = t7-delta
    t8 = 4*beta
    t9 = t8-X3
    t10 = gamma^2
    t11 = 8*t10     <-
    t12 = alpha*t9
    Y3 = t12-t11

[mmcloughlin]

Summary of all the "non primitive" expressions:

 584 *2
 131 ^3
 124 *4
  71 *3
  69 *8
  47 ^4
   9 *6
   6 *16
   4 *12
   2 *64
   1 *9
   1 *32
   1 *256

In the general case, these reduce to addition chain problems. However in these simple cases the naive binary algorithms should be enough.

[mmcloughlin]

The current work-in-progress diff produces the following. Note:

• Huge number of temporaries efd/op3: temporaries allocation #58
• Add and Sub functions need to have a three-argument form fp: montgomery reduction #47 fp: crandall prime #24

// Code generated by ec3. DO NOT EDIT.

package p256

type Jacobian struct {
	X Elt
	Y Elt
	Z Elt
}

func (p *Jacobian) Add(q, r *Jacobian) {
	var (
		t1   Elt
		U2   Elt
		t6   Elt
		U1   Elt
		S1   Elt
		t4   Elt
		t5   Elt
		J    Elt
		t10  Elt
		t12  Elt
		t13  Elt
		t0   Elt
		I    Elt
		t14  Elt
		t8   Elt
		t3   Elt
		r    Elt
		t11  Elt
		Z1Z1 Elt
		S2   Elt
		Z2Z2 Elt
		t7   Elt
		t9   Elt
		H    Elt
		t2   Elt
		V    Elt
	)

	Sqr(&Z1Z1, &q.Z)
	Sqr(&Z2Z2, &r.Z)
	Mul(&U1, &q.X, &Z2Z2)
	Mul(&U2, &r.X, &Z1Z1)
	Mul(&t0, &r.Z, &Z2Z2)
	Mul(&S1, &q.Y, &t0)
	Mul(&t1, &q.Z, &Z1Z1)
	Mul(&S2, &r.Y, &t1)
	Sub(&H, &U2, &U1)
	Add(&t2, &H, &H)
	Sqr(&I, &t2)
	Mul(&J, &H, &I)
	Sub(&t3, &S2, &S1)
	Add(&r, &t3, &t3)
	Mul(&V, &U1, &I)
	Sqr(&t4, &r)
	Add(&t5, &V, &V)
	Sub(&t6, &t4, &J)
	Sub(&p.X, &t6, &t5)
	Sub(&t7, &V, &p.X)
	Mul(&t8, &S1, &J)
	Add(&t9, &t8, &t8)
	Mul(&t10, &r, &t7)
	Sub(&p.Y, &t10, &t9)
	Add(&t11, &q.Z, &r.Z)
	Sqr(&t12, &t11)
	Sub(&t13, &t12, &Z1Z1)
	Sub(&t14, &t13, &Z2Z2)
	Mul(&p.Z, &t14, &H)
}