version3/go/ECP8.go

/*
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements.  See the NOTICE file
distributed with this work for additional information
regarding copyright ownership.  The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License.  You may obtain a copy of the License at

  http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied.  See the License for the
specific language governing permissions and limitations
under the License.
*/

/* MiotCL Weierstrass elliptic curve functions over FP2 */

package XXX

//import "fmt"

type ECP8 struct {
	x *FP8
	y *FP8
	z *FP8
//	INF bool
}

func NewECP8() *ECP8 {
	E:=new(ECP8)
	E.x=NewFP8int(0)
	E.y=NewFP8int(1)
	E.z=NewFP8int(0)
//	E.INF=true
	return E
}

/* Test this=O? */
func (E *ECP8) Is_infinity() bool {
//	if E.INF {return true}
	E.x.reduce(); E.y.reduce(); E.z.reduce()
	return E.x.iszilch() && E.z.iszilch()
}

/* copy this=P */
func (E *ECP8) Copy(P *ECP8) {
	E.x.copy(P.x)
	E.y.copy(P.y)
	E.z.copy(P.z)
//	E.INF=P.INF
}
/* set this=O */
func (E *ECP8) inf() {
//	E.INF=true
	E.x.zero()
	E.y.one()
	E.z.zero()
}

/* set this=-this */
func (E *ECP8) neg() {
	E.y.norm(); E.y.neg(); E.y.norm()
}

/* Conditional move of Q to P dependant on d */
func (E *ECP8) cmove(Q *ECP8,d int) {
	E.x.cmove(Q.x,d)
	E.y.cmove(Q.y,d)
	E.z.cmove(Q.z,d)
/*
	var bd bool
	if (d==0) {
		bd=false
	} else {bd=true}
	E.INF=(E.INF!=((E.INF!=Q.INF)&&bd))
*/
}

/* Constant time select from pre-computed table */
func (E *ECP8) selector(W []*ECP8,b int32) {
	MP:=NewECP8() 
	m:=b>>31
	babs:=(b^m)-m

	babs=(babs-1)/2

	E.cmove(W[0],teq(babs,0))  // conditional move
	E.cmove(W[1],teq(babs,1))
	E.cmove(W[2],teq(babs,2))
	E.cmove(W[3],teq(babs,3))
	E.cmove(W[4],teq(babs,4))
	E.cmove(W[5],teq(babs,5))
	E.cmove(W[6],teq(babs,6))
	E.cmove(W[7],teq(babs,7))
 
	MP.Copy(E)
	MP.neg()
	E.cmove(MP,int(m&1))
}

/* Test if P == Q */
func (E *ECP8) Equals(Q *ECP8) bool {
//	if E.Is_infinity() && Q.Is_infinity() {return true}
//	if E.Is_infinity() || Q.Is_infinity() {return false}

	a:=NewFP8copy(E.x)
	b:=NewFP8copy(Q.x)
	a.mul(Q.z); b.mul(E.z)

	if !a.Equals(b) {return false}
	a.copy(E.y); b.copy(Q.y)
	a.mul(Q.z); b.mul(E.z);
	if !a.Equals(b) {return false}

	return true
}

/* set to Affine - (x,y,z) to (x,y) */
func (E *ECP8) Affine() {
	if E.Is_infinity() {return}
	one:=NewFP8int(1)
	if E.z.Equals(one) {E.x.reduce(); E.y.reduce(); return}
	E.z.inverse()

	E.x.mul(E.z); E.x.reduce()
	E.y.mul(E.z); E.y.reduce()
	E.z.copy(one)
}

/* extract affine x as FP2 */
func (E *ECP8) GetX() *FP8 {
	W:=NewECP8(); W.Copy(E)
	W.Affine()
	return W.x
}
/* extract affine y as FP2 */
func (E *ECP8) GetY() *FP8 {
	W:=NewECP8(); W.Copy(E)
	W.Affine()
	return W.y;
}

/* extract projective x */
func (E *ECP8) getx() *FP8 {
	return E.x
}
/* extract projective y */
func (E *ECP8) gety() *FP8 {
	return E.y
}
/* extract projective z */
func (E *ECP8) getz() *FP8 {
	return E.z
}

/* convert to byte array */
func (E *ECP8) ToBytes(b []byte) {
	var t [int(MODBYTES)]byte
	MB:=int(MODBYTES)

	W:=NewECP8(); W.Copy(E);
	W.Affine()

	W.x.geta().geta().GetA().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i]=t[i]}
	W.x.geta().geta().GetB().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+MB]=t[i]}
	W.x.geta().getb().GetA().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+2*MB]=t[i]}
	W.x.geta().getb().GetB().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+3*MB]=t[i]}

	W.x.getb().geta().GetA().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+4*MB]=t[i]}
	W.x.getb().geta().GetB().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+5*MB]=t[i]}
	W.x.getb().getb().GetA().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+6*MB]=t[i]}
	W.x.getb().getb().GetB().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+7*MB]=t[i]}



	W.y.geta().geta().GetA().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+8*MB]=t[i]}
	W.y.geta().geta().GetB().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+9*MB]=t[i]}
	W.y.geta().getb().GetA().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+10*MB]=t[i]}
	W.y.geta().getb().GetB().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+11*MB]=t[i]}

	W.y.getb().geta().GetA().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+12*MB]=t[i]}
	W.y.getb().geta().GetB().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+13*MB]=t[i]}
	W.y.getb().getb().GetA().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+14*MB]=t[i]}
	W.y.getb().getb().GetB().ToBytes(t[:])
	for i:=0;i<MB;i++ { b[i+15*MB]=t[i]}
}

/* convert from byte array to point */
func ECP8_fromBytes(b []byte) *ECP8 {
	var t [int(MODBYTES)]byte
	MB:=int(MODBYTES)

	for i:=0;i<MB;i++ {t[i]=b[i]}
	ra:=FromBytes(t[:])
	for i:=0;i<MB;i++ {t[i]=b[i+MB]}
	rb:=FromBytes(t[:])

	ra4:=NewFP2bigs(ra,rb)

	for i:=0;i<MB;i++ {t[i]=b[i+2*MB]}
	ra=FromBytes(t[:])
	for i:=0;i<MB;i++ {t[i]=b[i+3*MB]}
	rb=FromBytes(t[:])

	rb4:=NewFP2bigs(ra,rb)

	ra8:=NewFP4fp2s(ra4,rb4)

	for i:=0;i<MB;i++ {t[i]=b[i+4*MB]}
	ra=FromBytes(t[:])
	for i:=0;i<MB;i++ {t[i]=b[i+5*MB]}
	rb=FromBytes(t[:])

	ra4=NewFP2bigs(ra,rb)

	for i:=0;i<MB;i++ {t[i]=b[i+6*MB]}
	ra=FromBytes(t[:])
	for i:=0;i<MB;i++ {t[i]=b[i+7*MB]}
	rb=FromBytes(t[:])

	rb4=NewFP2bigs(ra,rb)

	rb8:=NewFP4fp2s(ra4,rb4)

	rx:=NewFP8fp4s(ra8,rb8)

	for i:=0;i<MB;i++ {t[i]=b[i+8*MB]}
	ra=FromBytes(t[:])
	for i:=0;i<MB;i++ {t[i]=b[i+9*MB]}
	rb=FromBytes(t[:])

	ra4=NewFP2bigs(ra,rb)

	for i:=0;i<MB;i++ {t[i]=b[i+10*MB]}
	ra=FromBytes(t[:])
	for i:=0;i<MB;i++ {t[i]=b[i+11*MB]}
	rb=FromBytes(t[:])

	rb4=NewFP2bigs(ra,rb)

	ra8=NewFP4fp2s(ra4,rb4);

	for i:=0;i<MB;i++ {t[i]=b[i+12*MB]}
	ra=FromBytes(t[:])
	for i:=0;i<MB;i++ {t[i]=b[i+13*MB]}
	rb=FromBytes(t[:])

	ra4=NewFP2bigs(ra,rb)

	for i:=0;i<MB;i++ {t[i]=b[i+14*MB]}
	ra=FromBytes(t[:])
	for i:=0;i<MB;i++ {t[i]=b[i+15*MB]}
	rb=FromBytes(t[:])

	rb4=NewFP2bigs(ra,rb)

	rb8=NewFP4fp2s(ra4,rb4)

	ry:=NewFP8fp4s(ra8,rb8)

	return NewECP8fp8s(rx,ry)
}

/* convert this to hex string */
func (E *ECP8) ToString() string {
	W:=NewECP8(); W.Copy(E);
	W.Affine()
	if W.Is_infinity() {return "infinity"}
	return "("+W.x.toString()+","+W.y.toString()+")"
}

/* Calculate RHS of twisted curve equation x^3+B/i */
func RHS4(x *FP8) *FP8 {
	//x.norm()
	r:=NewFP8copy(x)
	r.sqr()
	b2:=NewFP2big(NewBIGints(CURVE_B))
	b4:=NewFP4fp2(b2)
	b:=NewFP8fp4(b4)

	if SEXTIC_TWIST == D_TYPE {
		b.div_i()
	}
	if SEXTIC_TWIST == M_TYPE {
		b.times_i()
	}	
	r.mul(x)
	r.add(b)

	r.reduce()
	return r
}

/* construct this from (x,y) - but set to O if not on curve */
func NewECP8fp8s(ix *FP8,iy *FP8) *ECP8 {
	E:=new(ECP8)
	E.x=NewFP8copy(ix)
	E.y=NewFP8copy(iy)
	E.z=NewFP8int(1)
	E.x.norm()
	rhs:=RHS4(E.x)
	y2:=NewFP8copy(E.y)
	y2.sqr()
	if !y2.Equals(rhs) {
		E.inf()
	} 
	return E
}

/* construct this from x - but set to O if not on curve */
func NewECP8fp8(ix *FP8) *ECP8 {	
	E:=new(ECP8)
	E.x=NewFP8copy(ix)
	E.y=NewFP8int(1)
	E.z=NewFP8int(1)
	E.x.norm()
	rhs:=RHS4(E.x)
	if rhs.sqrt() {
			E.y.copy(rhs)
			//E.INF=false;
	} else {E.inf()}
	return E
}

/* this+=this */
func (E *ECP8) dbl() int {
//	if E.INF {return -1}

	iy:=NewFP8copy(E.y)
	if SEXTIC_TWIST == D_TYPE {
		iy.times_i(); //iy.norm()
	}

	t0:=NewFP8copy(E.y)                  //***** Change 
	t0.sqr();  
	if SEXTIC_TWIST == D_TYPE {	
		t0.times_i()   
	}
	t1:=NewFP8copy(iy)  
	t1.mul(E.z)
	t2:=NewFP8copy(E.z)
	t2.sqr()

	E.z.copy(t0)
	E.z.add(t0); E.z.norm() 
	E.z.add(E.z)
	E.z.add(E.z) 
	E.z.norm()  

	t2.imul(3*CURVE_B_I) 
	if SEXTIC_TWIST == M_TYPE {
		t2.times_i()
		//t2.norm()
	}
	x3:=NewFP8copy(t2)
	x3.mul(E.z) 

	y3:=NewFP8copy(t0)   

	y3.add(t2); y3.norm()
	E.z.mul(t1)
	t1.copy(t2); t1.add(t2); t2.add(t1); t2.norm()  
	t0.sub(t2); t0.norm()                           //y^2-9bz^2
	y3.mul(t0); y3.add(x3)                          //(y^2+3z*2)(y^2-9z^2)+3b.z^2.8y^2
	t1.copy(E.x); t1.mul(iy)						//
	E.x.copy(t0); E.x.norm(); E.x.mul(t1); E.x.add(E.x)       //(y^2-9bz^2)xy2

	E.x.norm()
	E.y.copy(y3); E.y.norm()

	return 1
}

/* this+=Q - return 0 for add, 1 for double, -1 for O */
func (E *ECP8) Add(Q *ECP8) int {
/*	if E.INF {
		E.Copy(Q)
		return -1
	}
	if Q.INF {return -1}
*/
	b:=3*CURVE_B_I
	t0:=NewFP8copy(E.x)
	t0.mul(Q.x)         // x.Q.x
	t1:=NewFP8copy(E.y)
	t1.mul(Q.y)		 // y.Q.y

	t2:=NewFP8copy(E.z)
	t2.mul(Q.z)
	t3:=NewFP8copy(E.x)
	t3.add(E.y); t3.norm()          //t3=X1+Y1
	t4:=NewFP8copy(Q.x)            
	t4.add(Q.y); t4.norm()			//t4=X2+Y2
	t3.mul(t4)						//t3=(X1+Y1)(X2+Y2)
	t4.copy(t0); t4.add(t1)		//t4=X1.X2+Y1.Y2

	t3.sub(t4); t3.norm(); 
	if SEXTIC_TWIST == D_TYPE {
		t3.times_i();  //t3.norm()         //t3=(X1+Y1)(X2+Y2)-(X1.X2+Y1.Y2) = X1.Y2+X2.Y1
	}
	t4.copy(E.y);                    
	t4.add(E.z); t4.norm()			//t4=Y1+Z1
	x3:=NewFP8copy(Q.y)
	x3.add(Q.z); x3.norm()			//x3=Y2+Z2

	t4.mul(x3)						//t4=(Y1+Z1)(Y2+Z2)
	x3.copy(t1)					//
	x3.add(t2)						//X3=Y1.Y2+Z1.Z2
	
	t4.sub(x3); t4.norm();
	if SEXTIC_TWIST == D_TYPE {	
		t4.times_i(); //t4.norm()          //t4=(Y1+Z1)(Y2+Z2) - (Y1.Y2+Z1.Z2) = Y1.Z2+Y2.Z1
	}
	x3.copy(E.x); x3.add(E.z); x3.norm()	// x3=X1+Z1
	y3:=NewFP8copy(Q.x)				
	y3.add(Q.z); y3.norm()				// y3=X2+Z2
	x3.mul(y3)							// x3=(X1+Z1)(X2+Z2)
	y3.copy(t0)
	y3.add(t2)							// y3=X1.X2+Z1+Z2
	y3.rsub(x3); y3.norm()				// y3=(X1+Z1)(X2+Z2) - (X1.X2+Z1.Z2) = X1.Z2+X2.Z1

	if SEXTIC_TWIST == D_TYPE {
		t0.times_i(); //t0.norm() // x.Q.x
		t1.times_i(); //t1.norm() // y.Q.y
	}
	x3.copy(t0); x3.add(t0) 
	t0.add(x3); t0.norm()
	t2.imul(b) 	
	if SEXTIC_TWIST == M_TYPE {
		t2.times_i()
	}
	z3:=NewFP8copy(t1); z3.add(t2); z3.norm()
	t1.sub(t2); t1.norm()
	y3.imul(b) 
	if SEXTIC_TWIST == M_TYPE {
		y3.times_i()
		//y3.norm()
	}
	x3.copy(y3); x3.mul(t4); t2.copy(t3); t2.mul(t1); x3.rsub(t2)
	y3.mul(t0); t1.mul(z3); y3.add(t1)
	t0.mul(t3); z3.mul(t4); z3.add(t0)

	E.x.copy(x3); E.x.norm() 
	E.y.copy(y3); E.y.norm()
	E.z.copy(z3); E.z.norm()

	return 0
}

/* set this-=Q */
func (E *ECP8) Sub(Q *ECP8) int {
	NQ:=NewECP8(); NQ.Copy(Q)
	NQ.neg()
	D:=E.Add(NQ)
	//Q.neg()
	return D
}

func ECP8_frob_constants() [3]*FP2 {
	Fra:=NewBIGints(Fra)
	Frb:=NewBIGints(Frb)
	X:=NewFP2bigs(Fra,Frb)	

	F0:=NewFP2copy(X); F0.sqr()
	F2:=NewFP2copy(F0)
	F2.mul_ip(); F2.norm()
	F1:=NewFP2copy(F2); F1.sqr()
	F2.mul(F1)

	F2.mul_ip(); F2.norm()

	F1.copy(X)
	if SEXTIC_TWIST == M_TYPE {
		F1.mul_ip()
		F1.inverse()
		F0.copy(F1); F0.sqr()
	}
	F0.mul_ip(); F0.norm()
	F1.mul(F0)
	F:=[3]*FP2{F0,F1,F2}
	return F
}

/* set this*=q, where q is Modulus, using Frobenius */
func (E *ECP8) frob(F [3]*FP2,n int) {
//	if E.INF {return}
	for i:=0;i<n;i++ {
		E.x.frob(F[2])
		E.x.qmul(F[0])
		if SEXTIC_TWIST == M_TYPE {
			E.x.div_i2()
		}
		if SEXTIC_TWIST == D_TYPE {
			E.x.times_i2()
		}		

		E.y.frob(F[2])
		E.y.qmul(F[1])
		if SEXTIC_TWIST == M_TYPE {
			E.y.div_i()
		}
		if SEXTIC_TWIST == D_TYPE {
			E.y.times_i2(); E.y.times_i2(); E.y.times_i()
		}		
		E.z.frob(F[2])
	}
}

/* P*=e */
func (E *ECP8) mul(e *BIG) *ECP8 {
/* fixed size windows */
	mt:=NewBIG()
	t:=NewBIG()
	P:=NewECP8()
	Q:=NewECP8()
	C:=NewECP8()

	if E.Is_infinity() {return NewECP8()}

	var W []*ECP8
	var w [1+(NLEN*int(BASEBITS)+3)/4]int8

	//E.Affine()
/* precompute table */
	Q.Copy(E)
	Q.dbl()
		
	W=append(W,NewECP8())
	W[0].Copy(E);

	for i:=1;i<8;i++ {
		W=append(W,NewECP8())
		W[i].Copy(W[i-1])
		W[i].Add(Q)
	}

/* make exponent odd - add 2P if even, P if odd */
	t.copy(e)
	s:=int(t.parity())
	t.inc(1); t.norm(); ns:=int(t.parity()); mt.copy(t); mt.inc(1); mt.norm()
	t.cmove(mt,s)
	Q.cmove(E,ns)
	C.Copy(Q)

	nb:=1+(t.nbits()+3)/4
/* convert exponent to signed 4-bit window */
	for i:=0;i<nb;i++ {
		w[i]=int8(t.lastbits(5)-16)
		t.dec(int(w[i])); t.norm()
		t.fshr(4)	
	}
	w[nb]=int8(t.lastbits(5))
		
	P.Copy(W[(w[nb]-1)/2])
	for i:=nb-1;i>=0;i-- {
		Q.selector(W,int32(w[i]))
		P.dbl()
		P.dbl()
		P.dbl()
		P.dbl()
		P.Add(Q)
	}
	P.Sub(C)
	P.Affine()
	return P
}

/* Public version */
func (E *ECP8) Mul(e *BIG) *ECP8 {
	return E.mul(e)
}

func ECP8_generator() *ECP8 {
	var G *ECP8
	G=NewECP8fp8s( 
		NewFP8fp4s(
			NewFP4fp2s(
				NewFP2bigs(NewBIGints(CURVE_Pxaaa),NewBIGints(CURVE_Pxaab)),
				NewFP2bigs(NewBIGints(CURVE_Pxaba),NewBIGints(CURVE_Pxabb))),
			NewFP4fp2s(
				NewFP2bigs(NewBIGints(CURVE_Pxbaa),NewBIGints(CURVE_Pxbab)),
				NewFP2bigs(NewBIGints(CURVE_Pxbba),NewBIGints(CURVE_Pxbbb)))),
		NewFP8fp4s(
			NewFP4fp2s(
				NewFP2bigs(NewBIGints(CURVE_Pyaaa),NewBIGints(CURVE_Pyaab)),
				NewFP2bigs(NewBIGints(CURVE_Pyaba),NewBIGints(CURVE_Pyabb))),
			NewFP4fp2s(
				NewFP2bigs(NewBIGints(CURVE_Pybaa),NewBIGints(CURVE_Pybab)),
				NewFP2bigs(NewBIGints(CURVE_Pybba),NewBIGints(CURVE_Pybbb)))))
	return G
}

/* needed for SOK */
func ECP8_mapit(h []byte) *ECP8 {
	q:=NewBIGints(Modulus)
	hv:=FromBytes(h[:])
	one:=NewBIGint(1)
	var X2 *FP2
	var X4 *FP4 
	var X *FP8
	var Q *ECP8
	hv.Mod(q)
	for true {
		X2=NewFP2bigs(one,hv)
		X4=NewFP4fp2(X2)
		X=NewFP8fp4(X4)
		Q=NewECP8fp8(X)
		if !Q.Is_infinity() {break}
		hv.inc(1); hv.norm()
	}
	F:=ECP8_frob_constants()
	x:=NewBIGints(CURVE_Bnx)

	xQ:=Q.mul(x)
	x2Q:=xQ.mul(x)
	x3Q:=x2Q.mul(x)
	x4Q:=x3Q.mul(x)
	x5Q:=x4Q.mul(x)
	x6Q:=x5Q.mul(x)
	x7Q:=x6Q.mul(x)
	x8Q:=x7Q.mul(x)

	if SIGN_OF_X==NEGATIVEX {
		xQ.neg()
		x3Q.neg()
		x5Q.neg()
		x7Q.neg()
	}
	x8Q.Sub(x7Q)
	x8Q.Sub(Q)

	x7Q.Sub(x6Q)
	x7Q.frob(F,1)

	x6Q.Sub(x5Q)
	x6Q.frob(F,2)

	x5Q.Sub(x4Q)
	x5Q.frob(F,3)

	x4Q.Sub(x3Q)
	x4Q.frob(F,4)

	x3Q.Sub(x2Q)
	x3Q.frob(F,5)

	x2Q.Sub(xQ)
	x2Q.frob(F,6)

	xQ.Sub(Q)
	xQ.frob(F,7)

	Q.dbl()
	Q.frob(F,8)

	Q.Add(x8Q)
	Q.Add(x7Q)
	Q.Add(x6Q)
	Q.Add(x5Q)

	Q.Add(x4Q)
	Q.Add(x3Q)
	Q.Add(x2Q)
	Q.Add(xQ)

	Q.Affine()
	return Q
}

/* P=u0.Q0+u1*Q1+u2*Q2+u3*Q3.. */
// Bos & Costello https://eprint.iacr.org/2013/458.pdf
// Faz-Hernandez & Longa & Sanchez  https://eprint.iacr.org/2013/158.pdf
// Side channel attack secure 
func mul16(Q []*ECP8,u []*BIG) *ECP8 {
	W:=NewECP8()
	P:=NewECP8()
	var T1 [] *ECP8
	var T2 [] *ECP8
	var T3 [] *ECP8
	var T4 [] *ECP8
	mt:=NewBIG()
	var t [] *BIG
	var bt int8
	var k int

	var w1 [NLEN*int(BASEBITS)+1]int8	
	var s1 [NLEN*int(BASEBITS)+1]int8	
	var w2 [NLEN*int(BASEBITS)+1]int8	
	var s2 [NLEN*int(BASEBITS)+1]int8	
	var w3 [NLEN*int(BASEBITS)+1]int8	
	var s3 [NLEN*int(BASEBITS)+1]int8	
	var w4 [NLEN*int(BASEBITS)+1]int8	
	var s4 [NLEN*int(BASEBITS)+1]int8	

	for i:=0;i<16;i++ {
		t=append(t,NewBIGcopy(u[i]));
		//Q[i].Affine();
	}

	T1=append(T1,NewECP8()); T1[0].Copy(Q[0])	// Q[0]
	T1=append(T1,NewECP8()); T1[1].Copy(T1[0]); T1[1].Add(Q[1])	// Q[0]+Q[1]
	T1=append(T1,NewECP8()); T1[2].Copy(T1[0]); T1[2].Add(Q[2])	// Q[0]+Q[2]
	T1=append(T1,NewECP8()); T1[3].Copy(T1[1]); T1[3].Add(Q[2])	// Q[0]+Q[1]+Q[2]
	T1=append(T1,NewECP8()); T1[4].Copy(T1[0]); T1[4].Add(Q[3])	// Q[0]+Q[3]
	T1=append(T1,NewECP8()); T1[5].Copy(T1[1]); T1[5].Add(Q[3])	// Q[0]+Q[1]+Q[3]
	T1=append(T1,NewECP8()); T1[6].Copy(T1[2]); T1[6].Add(Q[3])	// Q[0]+Q[2]+Q[3]
	T1=append(T1,NewECP8()); T1[7].Copy(T1[3]); T1[7].Add(Q[3])	// Q[0]+Q[1]+Q[2]+Q[3]

//  Use Frobenius 
	F:=ECP8_frob_constants()

	for i:=0;i<8;i++ {
		T2=append(T2,NewECP8()); T2[i].Copy(T1[i]); T2[i].frob(F,4)
		T3=append(T3,NewECP8()); T3[i].Copy(T2[i]); T3[i].frob(F,4)
		T4=append(T4,NewECP8()); T4[i].Copy(T3[i]); T4[i].frob(F,4)
	}

// Make them odd
	pb1:=1-t[0].parity()
	t[0].inc(pb1)
//	t[0].norm();

	pb2:=1-t[4].parity()
	t[4].inc(pb2)
//	t[4].norm();

	pb3:=1-t[8].parity()
	t[8].inc(pb3)
//	t[8].norm();

	pb4:=1-t[12].parity()
	t[12].inc(pb4)
//	t[12].norm();

// Number of bits
	mt.zero()
	for i:=0;i<16;i++ {
		t[i].norm()
		mt.or(t[i])
	}

	nb:=1+mt.nbits();
	
// Sign pivot 
	s1[nb-1]=1
	s2[nb-1]=1
	s3[nb-1]=1
	s4[nb-1]=1
	for i:=0;i<nb-1;i++ {
		t[0].fshr(1)
		s1[i]=2*int8(t[0].parity())-1
		t[4].fshr(1)
		s2[i]=2*int8(t[4].parity())-1
		t[8].fshr(1)
		s3[i]=2*int8(t[8].parity())-1
		t[12].fshr(1)
		s4[i]=2*int8(t[12].parity())-1

	}

// Recoded exponents
	for i:=0; i<nb; i++ {
		w1[i]=0
		k=1
		for j:=1; j<4; j++ {
			bt=s1[i]*int8(t[j].parity())
			t[j].fshr(1)
			t[j].dec(int(bt)>>1)
			t[j].norm()
			w1[i]+=bt*int8(k)
			k*=2
		}
		w2[i]=0
		k=1
		for j:=5; j<8; j++ {
			bt=s2[i]*int8(t[j].parity())
			t[j].fshr(1)
			t[j].dec(int(bt)>>1)
			t[j].norm()
			w2[i]+=bt*int8(k)
			k*=2
		}
		w3[i]=0
		k=1
		for j:=9; j<12; j++ {
			bt=s3[i]*int8(t[j].parity())
			t[j].fshr(1)
			t[j].dec(int(bt)>>1)
			t[j].norm()
			w3[i]+=bt*int8(k)
			k*=2
		}
		w4[i]=0
		k=1
		for j:=13; j<16; j++ {
			bt=s4[i]*int8(t[j].parity())
			t[j].fshr(1)
			t[j].dec(int(bt)>>1)
			t[j].norm()
			w4[i]+=bt*int8(k)
			k*=2
		}
	}

// Main loop
	P.selector(T1,int32(2*w1[nb-1]+1))  
	W.selector(T2,int32(2*w2[nb-1]+1))
	P.Add(W)
	W.selector(T3,int32(2*w3[nb-1]+1))
	P.Add(W)
	W.selector(T4,int32(2*w4[nb-1]+1))
	P.Add(W)
	for i:=nb-2;i>=0;i-- {
		P.dbl()
		W.selector(T1,int32(2*w1[i]+s1[i]))
		P.Add(W)
		W.selector(T2,int32(2*w2[i]+s2[i]))
		P.Add(W)
		W.selector(T3,int32(2*w3[i]+s3[i]))
		P.Add(W)
		W.selector(T4,int32(2*w4[i]+s4[i]))
		P.Add(W)

	}

// apply correction
	W.Copy(P)   
	W.Sub(Q[0])
	P.cmove(W,pb1)
	W.Copy(P)   
	W.Sub(Q[4])
	P.cmove(W,pb2)
	W.Copy(P)   
	W.Sub(Q[8])
	P.cmove(W,pb3)
	W.Copy(P)   
	W.Sub(Q[12])
	P.cmove(W,pb4)

	P.Affine()
	return P
}