// See "Multiplication and Squaring in Pairing-Friendly Fields",
// http://eprint.iacr.org/2006/471.pdf
976244
func (e *gfP2) Mul(a, b *gfP2, pool *bnPool) *gfP2 {
	tx := pool.Get().Mul(a.x, b.y)
	t := pool.Get().Mul(b.x, a.y)
	tx.Add(tx, t)
	tx.Mod(tx, P)

	ty := pool.Get().Mul(a.y, b.y)
	t.Mul(a.x, b.x)
	ty.Sub(ty, t)
	e.y.Mod(ty, P)
	e.x.Set(tx)

	pool.Put(tx)
	pool.Put(ty)
	pool.Put(t)

	return e
}
28868
func (ec *EllipticCurve) ScalarBaseMult(k *big.Int) (Q Point) {
	return ec.ScalarMult(k, ec.G)
}
822871
func roundFunc(q query, t iterator) interface{} {
	val := asNumber(t, q.Evaluate(t))
	//return math.Round(val)
	return round(val)
}
360751
func NewGaloisField(pp, fieldSize, b int) *GaloisField {
	result := new(GaloisField)

	result.Size = fieldSize
	result.Base = b
	result.ALogTbl = make([]int, fieldSize)
	result.LogTbl = make([]int, fieldSize)

	x := 1
	for i := 0; i < fieldSize; i++ {
		result.ALogTbl[i] = x
		x = x * 2
		if x >= fieldSize {
			x = (x ^ pp) & (fieldSize - 1)
		}
	}

	for i := 0; i < fieldSize; i++ {
		result.LogTbl[result.ALogTbl[i]] = int(i)
	}

	return result
}
1284870
func (u *Ugen) Sqrsum(val Input) Input {
	return binOpSqrsum(u.Rate, u, val, u.NumOutputs)
}
929799
func Subtract(vs ReaderWriter, vsOther Iterable) error {
	return vsOther.IterateValidators(func(id crypto.Addressable, power *big.Int) error {
		return SubtractPower(vs, id.GetPublicKey(), power)
	})
}
20303
func gcmDouble(x *gcmFieldElement) (double gcmFieldElement) {
	msbSet := x.high&1 == 1

	// Because of the bit-ordering, doubling is actually a right shift.
	double.high = x.high >> 1
	double.high |= x.low << 63
	double.low = x.low >> 1

	// If the most-significant bit was set before shifting then it,
	// conceptually, becomes a term of x^128. This is greater than the
	// irreducible polynomial so the result has to be reduced. The
	// irreducible polynomial is 1+x+x^2+x^7+x^128. We can subtract that to
	// eliminate the term at x^128 which also means subtracting the other
	// four terms. In characteristic 2 fields, subtraction == addition ==
	// XOR.
	if msbSet {
		double.low ^= 0xe100000000000000
	}

	return
}
1085614
func (as ArraySpec) Sqrt() Input {
	return as.proc(func(i Input) Input {
		return i.Sqrt()
	})
}
335250
func basicMul(z, x, y fermat) {
	// initialize z
	for i := 0; i < len(z); i++ {
		z[i] = 0
	}
	for i, d := range y {
		if d != 0 {
			z[len(x)+i] = addMulVVW(z[i:i+len(x)], x, d)
		}
	}
}
614786
func regspillsRef(x, y []simd.I32x4) int32 {
	if len(x) != len(y) {
		return -1
	}
	dist := int32(math.MaxInt32)
	i := 0
	j := 1
	dx := simd.SubI32x4(x[j], x[i])
	dy := simd.SubI32x4(y[j], y[i])
	sqX := simd.MulI32x4(dx, dx)
	sqY := simd.MulI32x4(dy, dy)
	sqDist := simd.AddI32x4(sqX, sqY)
	dx2 := simd.SubI32x4(dx, dy)

	dy2 := simd.SubI32x4(sqX, sqY)
	sqX2 := simd.MulI32x4(dx2, dx2)
	sqY2 := simd.MulI32x4(dy2, dy2)
	sqDist2 := simd.AddI32x4(sqX2, sqY2)
	dx3 := simd.SubI32x4(dx2, dy2)
	dy3 := simd.SubI32x4(sqX2, sqY2)
	sqX3 := simd.MulI32x4(dx3, dx3)
	sqY3 := simd.MulI32x4(dy3, dy3)
	sqDist3 := simd.AddI32x4(sqX3, sqY3)
	t := dx[0] + dx[1] + dx[2] + dx[3] +
		dx2[0] + dx2[1] + dx2[2] + dx2[3] +
		dx3[0] + dx3[1] + dx3[2] + dx3[3]
	v := dy[0] + dy[1] + dy[2] + dy[3] +
		dy2[0] + dy2[1] + dy2[2] + dy2[3] +
		dy3[0] + dy3[1] + dy3[2] + dy3[3]
	dist = t + v + sqDist[0] + sqDist2[1] + sqDist3[2]
	return dist
}
387275
func (u *Ugen) Squared() Input {
	return unaryOpSquared(u.Rate, u, u.NumOutputs)
}
413264
func DoArithmetic(a, b interface{}, op rune) (interface{}, error) {
	av := reflect.ValueOf(a)
	bv := reflect.ValueOf(b)
	var ai, bi int64
	var af, bf float64
	var au, bu uint64
	switch av.Kind() {
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
		ai = av.Int()
		switch bv.Kind() {
		case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
			bi = bv.Int()
		case reflect.Float32, reflect.Float64:
			af = float64(ai) // may overflow
			ai = 0
			bf = bv.Float()
		case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64:
			bu = bv.Uint()
			if ai >= 0 {
				au = uint64(ai)
				ai = 0
			} else {
				bi = int64(bu) // may overflow
				bu = 0
			}
		default:
			return nil, errors.New("can't apply the operator to the values")
		}
	case reflect.Float32, reflect.Float64:
		af = av.Float()
		switch bv.Kind() {
		case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
			bf = float64(bv.Int()) // may overflow
		case reflect.Float32, reflect.Float64:
			bf = bv.Float()
		case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64:
			bf = float64(bv.Uint()) // may overflow
		default:
			return nil, errors.New("can't apply the operator to the values")
		}
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64:
		au = av.Uint()
		switch bv.Kind() {
		case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
			bi = bv.Int()
			if bi >= 0 {
				bu = uint64(bi)
				bi = 0
			} else {
				ai = int64(au) // may overflow
				au = 0
			}
		case reflect.Float32, reflect.Float64:
			af = float64(au) // may overflow
			au = 0
			bf = bv.Float()
		case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64:
			bu = bv.Uint()
		default:
			return nil, errors.New("can't apply the operator to the values")
		}
	case reflect.String:
		as := av.String()
		if bv.Kind() == reflect.String && op == '+' {
			bs := bv.String()
			return as + bs, nil
		}
		return nil, errors.New("can't apply the operator to the values")
	default:
		return nil, errors.New("can't apply the operator to the values")
	}

	switch op {
	case '+':
		if ai != 0 || bi != 0 {
			return ai + bi, nil
		} else if af != 0 || bf != 0 {
			return af + bf, nil
		} else if au != 0 || bu != 0 {
			return au + bu, nil
		}
		return 0, nil
	case '-':
		if ai != 0 || bi != 0 {
			return ai - bi, nil
		} else if af != 0 || bf != 0 {
			return af - bf, nil
		} else if au != 0 || bu != 0 {
			return au - bu, nil
		}
		return 0, nil
	case '*':
		if ai != 0 || bi != 0 {
			return ai * bi, nil
		} else if af != 0 || bf != 0 {
			return af * bf, nil
		} else if au != 0 || bu != 0 {
			return au * bu, nil
		}
		return 0, nil
	case '/':
		if bi != 0 {
			return ai / bi, nil
		} else if bf != 0 {
			return af / bf, nil
		} else if bu != 0 {
			return au / bu, nil
		}
		return nil, errors.New("can't divide the value by 0")
	default:
		return nil, errors.New("there is no such an operation")
	}
}
928488
func (ec *EllipticCurve) ScalarMult(k *big.Int, P Point) (Q Point) {
	/* Note: this function is not constant time, due to the branching nature of
	 * the underlying point Add() function. */

	/* Montgomery Ladder Point Multiplication
	 *
	 * Implementation based on pseudocode here:
	 * See https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder */

	var R0 Point
	var R1 Point

	R0.X = nil
	R0.Y = nil
	R1.X = new(big.Int).Set(P.X)
	R1.Y = new(big.Int).Set(P.Y)

	for i := ec.N.BitLen() - 1; i >= 0; i-- {
		if k.Bit(i) == 0 {
			R1 = ec.Add(R0, R1)
			R0 = ec.Add(R0, R0)
		} else {
			R0 = ec.Add(R0, R1)
			R1 = ec.Add(R1, R1)
		}
	}

	return R0
}
756457
func (curve *KoblitzCurve) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
	// Point Q = ∞ (point at infinity).
	qx, qy, qz := new(fieldVal), new(fieldVal), new(fieldVal)

	// Decompose K into k1 and k2 in order to halve the number of EC ops.
	// See Algorithm 3.74 in [GECC].
	k1, k2, signK1, signK2 := curve.splitK(curve.moduloReduce(k))

	// The main equation here to remember is:
	//   k * P = k1 * P + k2 * ϕ(P)
	//
	// P1 below is P in the equation, P2 below is ϕ(P) in the equation
	p1x, p1y := curve.bigAffineToField(Bx, By)
	p1yNeg := new(fieldVal).NegateVal(p1y, 1)
	p1z := new(fieldVal).SetInt(1)

	// NOTE: ϕ(x,y) = (βx,y).  The Jacobian z coordinate is 1, so this math
	// goes through.
	p2x := new(fieldVal).Mul2(p1x, curve.beta)
	p2y := new(fieldVal).Set(p1y)
	p2yNeg := new(fieldVal).NegateVal(p2y, 1)
	p2z := new(fieldVal).SetInt(1)

	// Flip the positive and negative values of the points as needed
	// depending on the signs of k1 and k2.  As mentioned in the equation
	// above, each of k1 and k2 are multiplied by the respective point.
	// Since -k * P is the same thing as k * -P, and the group law for
	// elliptic curves states that P(x, y) = -P(x, -y), it's faster and
	// simplifies the code to just make the point negative.
	if signK1 == -1 {
		p1y, p1yNeg = p1yNeg, p1y
	}
	if signK2 == -1 {
		p2y, p2yNeg = p2yNeg, p2y
	}

	// NAF versions of k1 and k2 should have a lot more zeros.
	//
	// The Pos version of the bytes contain the +1s and the Neg versions
	// contain the -1s.
	k1PosNAF, k1NegNAF := NAF(k1)
	k2PosNAF, k2NegNAF := NAF(k2)
	k1Len := len(k1PosNAF)
	k2Len := len(k2PosNAF)

	m := k1Len
	if m < k2Len {
		m = k2Len
	}

	// Add left-to-right using the NAF optimization.  See algorithm 3.77
	// from [GECC].  This should be faster overall since there will be a lot
	// more instances of 0, hence reducing the number of Jacobian additions
	// at the cost of 1 possible extra doubling.
	var k1BytePos, k1ByteNeg, k2BytePos, k2ByteNeg byte
	for i := 0; i < m; i++ {
		// Since we're going left-to-right, pad the front with 0s.
		if i < m-k1Len {
			k1BytePos = 0
			k1ByteNeg = 0
		} else {
			k1BytePos = k1PosNAF[i-(m-k1Len)]
			k1ByteNeg = k1NegNAF[i-(m-k1Len)]
		}
		if i < m-k2Len {
			k2BytePos = 0
			k2ByteNeg = 0
		} else {
			k2BytePos = k2PosNAF[i-(m-k2Len)]
			k2ByteNeg = k2NegNAF[i-(m-k2Len)]
		}

		for j := 7; j >= 0; j-- {
			// Q = 2 * Q
			curve.doubleJacobian(qx, qy, qz, qx, qy, qz)

			if k1BytePos&0x80 == 0x80 {
				curve.addJacobian(qx, qy, qz, p1x, p1y, p1z,
					qx, qy, qz)
			} else if k1ByteNeg&0x80 == 0x80 {
				curve.addJacobian(qx, qy, qz, p1x, p1yNeg, p1z,
					qx, qy, qz)
			}

			if k2BytePos&0x80 == 0x80 {
				curve.addJacobian(qx, qy, qz, p2x, p2y, p2z,
					qx, qy, qz)
			} else if k2ByteNeg&0x80 == 0x80 {
				curve.addJacobian(qx, qy, qz, p2x, p2yNeg, p2z,
					qx, qy, qz)
			}
			k1BytePos <<= 1
			k1ByteNeg <<= 1
			k2BytePos <<= 1
			k2ByteNeg <<= 1
		}
	}

	// Convert the Jacobian coordinate field values back to affine big.Ints.
	return curve.fieldJacobianToBigAffine(qx, qy, qz)
}
1283655
func Poly(xvalues, yvalues []float64, degree int) ([]float64, error) {
	if len(xvalues) != len(yvalues) {
		return nil, ErrPolyRegArraysSameLength
	}

	m := len(yvalues)
	n := degree + 1
	y := New(m, 1, yvalues...)
	x := Zero(m, n)

	for i := 0; i < m; i++ {
		ip := float64(1)
		for j := 0; j < n; j++ {
			x.Set(i, j, ip)
			ip *= xvalues[i]
		}
	}

	q, r := x.QR()
	qty, err := q.Transpose().Times(y)
	if err != nil {
		return nil, err
	}

	c := make([]float64, n)
	for i := n - 1; i >= 0; i-- {
		c[i] = qty.Get(i, 0)
		for j := i + 1; j < n; j++ {
			c[i] -= c[j] * r.Get(i, j)
		}
		c[i] /= r.Get(i, i)
	}

	return c, nil
}
1360209
func (f *extFloat) Multiply(g extFloat) {
	fhi, flo := f.mant>>32, uint64(uint32(f.mant))
	ghi, glo := g.mant>>32, uint64(uint32(g.mant))

	// Cross products.
	cross1 := fhi * glo
	cross2 := flo * ghi

	// f.mant*g.mant is fhi*ghi << 64 + (cross1+cross2) << 32 + flo*glo
	f.mant = fhi*ghi + (cross1 >> 32) + (cross2 >> 32)
	rem := uint64(uint32(cross1)) + uint64(uint32(cross2)) + ((flo * glo) >> 32)
	// Round up.
	rem += (1 << 31)

	f.mant += (rem >> 32)
	f.exp = f.exp + g.exp + 64
}
459226
func (f *fieldVal) Normalize() *fieldVal {
	// The field representation leaves 6 bits of overflow in each word so
	// intermediate calculations can be performed without needing to
	// propagate the carry to each higher word during the calculations.  In
	// order to normalize, we need to "compact" the full 256-bit value to
	// the right while propagating any carries through to the high order
	// word.
	//
	// Since this field is doing arithmetic modulo the secp256k1 prime, we
	// also need to perform modular reduction over the prime.
	//
	// Per [HAC] section 14.3.4: Reduction method of moduli of special form,
	// when the modulus is of the special form m = b^t - c, highly efficient
	// reduction can be achieved.
	//
	// The secp256k1 prime is equivalent to 2^256 - 4294968273, so it fits
	// this criteria.
	//
	// 4294968273 in field representation (base 2^26) is:
	// n[0] = 977
	// n[1] = 64
	// That is to say (2^26 * 64) + 977 = 4294968273
	//
	// The algorithm presented in the referenced section typically repeats
	// until the quotient is zero.  However, due to our field representation
	// we already know to within one reduction how many times we would need
	// to repeat as it's the uppermost bits of the high order word.  Thus we
	// can simply multiply the magnitude by the field representation of the
	// prime and do a single iteration.  After this step there might be an
	// additional carry to bit 256 (bit 22 of the high order word).
	t9 := f.n[9]
	m := t9 >> fieldMSBBits
	t9 = t9 & fieldMSBMask
	t0 := f.n[0] + m*977
	t1 := (t0 >> fieldBase) + f.n[1] + (m << 6)
	t0 = t0 & fieldBaseMask
	t2 := (t1 >> fieldBase) + f.n[2]
	t1 = t1 & fieldBaseMask
	t3 := (t2 >> fieldBase) + f.n[3]
	t2 = t2 & fieldBaseMask
	t4 := (t3 >> fieldBase) + f.n[4]
	t3 = t3 & fieldBaseMask
	t5 := (t4 >> fieldBase) + f.n[5]
	t4 = t4 & fieldBaseMask
	t6 := (t5 >> fieldBase) + f.n[6]
	t5 = t5 & fieldBaseMask
	t7 := (t6 >> fieldBase) + f.n[7]
	t6 = t6 & fieldBaseMask
	t8 := (t7 >> fieldBase) + f.n[8]
	t7 = t7 & fieldBaseMask
	t9 = (t8 >> fieldBase) + t9
	t8 = t8 & fieldBaseMask

	// At this point, the magnitude is guaranteed to be one, however, the
	// value could still be greater than the prime if there was either a
	// carry through to bit 256 (bit 22 of the higher order word) or the
	// value is greater than or equal to the field characteristic.  The
	// following determines if either or these conditions are true and does
	// the final reduction in constant time.
	//
	// Note that the if/else statements here intentionally do the bitwise
	// operators even when it won't change the value to ensure constant time
	// between the branches.  Also note that 'm' will be zero when neither
	// of the aforementioned conditions are true and the value will not be
	// changed when 'm' is zero.
	m = 1
	if t9 == fieldMSBMask {
		m &= 1
	} else {
		m &= 0
	}
	if t2&t3&t4&t5&t6&t7&t8 == fieldBaseMask {
		m &= 1
	} else {
		m &= 0
	}
	if ((t0+977)>>fieldBase + t1 + 64) > fieldBaseMask {
		m &= 1
	} else {
		m &= 0
	}
	if t9>>fieldMSBBits != 0 {
		m |= 1
	} else {
		m |= 0
	}
	t0 = t0 + m*977
	t1 = (t0 >> fieldBase) + t1 + (m << 6)
	t0 = t0 & fieldBaseMask
	t2 = (t1 >> fieldBase) + t2
	t1 = t1 & fieldBaseMask
	t3 = (t2 >> fieldBase) + t3
	t2 = t2 & fieldBaseMask
	t4 = (t3 >> fieldBase) + t4
	t3 = t3 & fieldBaseMask
	t5 = (t4 >> fieldBase) + t5
	t4 = t4 & fieldBaseMask
	t6 = (t5 >> fieldBase) + t6
	t5 = t5 & fieldBaseMask
	t7 = (t6 >> fieldBase) + t7
	t6 = t6 & fieldBaseMask
	t8 = (t7 >> fieldBase) + t8
	t7 = t7 & fieldBaseMask
	t9 = (t8 >> fieldBase) + t9
	t8 = t8 & fieldBaseMask
	t9 = t9 & fieldMSBMask // Remove potential multiple of 2^256.

	// Finally, set the normalized and reduced words.
	f.n[0] = t0
	f.n[1] = t1
	f.n[2] = t2
	f.n[3] = t3
	f.n[4] = t4
	f.n[5] = t5
	f.n[6] = t6
	f.n[7] = t7
	f.n[8] = t8
	f.n[9] = t9
	return f
}