element.go

// Copyright 2020 ConsenSys Software Inc.
//
// Licensed 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.

// Code generated by consensys/gnark-crypto DO NOT EDIT

package fp

// /!\ WARNING /!\
// this code has not been audited and is provided as-is. In particular,
// there is no security guarantees such as constant time implementation
// or side-channel attack resistance
// /!\ WARNING /!\

import (
	"crypto/rand"
	"encoding/binary"
	"errors"
	"io"
	"math/big"
	"math/bits"
	"reflect"
	"strconv"
	"sync"
)

// Element represents a field element stored on 12 words (uint64)
// Element are assumed to be in Montgomery form in all methods
// field modulus q =
//
// 6891450384315732539396789682275657542479668912536150109513790160209623422243491736087683183289411687640864567753786613451161759120554247759349511699125301598951605099378508850372543631423596795951899700429969112842764913119068299
type Element [12]uint64

// Limbs number of 64 bits words needed to represent Element
const Limbs = 12

// Bits number bits needed to represent Element
const Bits = 761

// Bytes number bytes needed to represent Element
const Bytes = Limbs * 8

// field modulus stored as big.Int
var _modulus big.Int

// Modulus returns q as a big.Int
// q =
//
// 6891450384315732539396789682275657542479668912536150109513790160209623422243491736087683183289411687640864567753786613451161759120554247759349511699125301598951605099378508850372543631423596795951899700429969112842764913119068299
func Modulus() *big.Int {
	return new(big.Int).Set(&_modulus)
}

// q (modulus)
var qElement = Element{
	17626244516597989515,
	16614129118623039618,
	1588918198704579639,
	10998096788944562424,
	8204665564953313070,
	9694500593442880912,
	274362232328168196,
	8105254717682411801,
	5945444129596489281,
	13341377791855249032,
	15098257552581525310,
	81882988782276106,
}

// rSquare
var rSquare = Element{
	14305184132582319705,
	8868935336694416555,
	9196887162930508889,
	15486798265448570248,
	5402985275949444416,
	10893197322525159598,
	3204916688966998390,
	12417238192559061753,
	12426306557607898622,
	1305582522441154384,
	10311846026977660324,
	48736111365249031,
}

var bigIntPool = sync.Pool{
	New: func() interface{} {
		return new(big.Int)
	},
}

func init() {
	_modulus.SetString("6891450384315732539396789682275657542479668912536150109513790160209623422243491736087683183289411687640864567753786613451161759120554247759349511699125301598951605099378508850372543631423596795951899700429969112842764913119068299", 10)
}

// NewElement returns a new Element from a uint64 value
//
// it is equivalent to
// 		var v NewElement
// 		v.SetUint64(...)
func NewElement(v uint64) Element {
	z := Element{v}
	z.Mul(&z, &rSquare)
	return z
}

// SetUint64 z = v, sets z LSB to v (non-Montgomery form) and convert z to Montgomery form
func (z *Element) SetUint64(v uint64) *Element {
	*z = Element{v}
	return z.Mul(z, &rSquare) // z.ToMont()
}

// Set z = x
func (z *Element) Set(x *Element) *Element {
	z[0] = x[0]
	z[1] = x[1]
	z[2] = x[2]
	z[3] = x[3]
	z[4] = x[4]
	z[5] = x[5]
	z[6] = x[6]
	z[7] = x[7]
	z[8] = x[8]
	z[9] = x[9]
	z[10] = x[10]
	z[11] = x[11]
	return z
}

// SetInterface converts provided interface into Element
// returns an error if provided type is not supported
// supported types: Element, *Element, uint64, int, string (interpreted as base10 integer),
// *big.Int, big.Int, []byte
func (z *Element) SetInterface(i1 interface{}) (*Element, error) {
	switch c1 := i1.(type) {
	case Element:
		return z.Set(&c1), nil
	case *Element:
		return z.Set(c1), nil
	case uint64:
		return z.SetUint64(c1), nil
	case int:
		return z.SetString(strconv.Itoa(c1)), nil
	case string:
		return z.SetString(c1), nil
	case *big.Int:
		return z.SetBigInt(c1), nil
	case big.Int:
		return z.SetBigInt(&c1), nil
	case []byte:
		return z.SetBytes(c1), nil
	default:
		return nil, errors.New("can't set fp.Element from type " + reflect.TypeOf(i1).String())
	}
}

// SetZero z = 0
func (z *Element) SetZero() *Element {
	z[0] = 0
	z[1] = 0
	z[2] = 0
	z[3] = 0
	z[4] = 0
	z[5] = 0
	z[6] = 0
	z[7] = 0
	z[8] = 0
	z[9] = 0
	z[10] = 0
	z[11] = 0
	return z
}

// SetOne z = 1 (in Montgomery form)
func (z *Element) SetOne() *Element {
	z[0] = 144959613005956565
	z[1] = 6509995272855063783
	z[2] = 11428286765660613342
	z[3] = 15738672438262922740
	z[4] = 17071399330169272331
	z[5] = 13899911246788437003
	z[6] = 12055474021000362245
	z[7] = 2545351818702954755
	z[8] = 8887388221587179644
	z[9] = 5009280847225881135
	z[10] = 15539704305423854047
	z[11] = 23071597697427581
	return z
}

// Div z = x*y^-1 mod q
func (z *Element) Div(x, y *Element) *Element {
	var yInv Element
	yInv.Inverse(y)
	z.Mul(x, &yInv)
	return z
}

// Bit returns the i'th bit, with lsb == bit 0.
// It is the responsability of the caller to convert from Montgomery to Regular form if needed
func (z *Element) Bit(i uint64) uint64 {
	j := i / 64
	if j >= 12 {
		return 0
	}
	return uint64(z[j] >> (i % 64) & 1)
}

// Equal returns z == x
func (z *Element) Equal(x *Element) bool {
	return (z[11] == x[11]) && (z[10] == x[10]) && (z[9] == x[9]) && (z[8] == x[8]) && (z[7] == x[7]) && (z[6] == x[6]) && (z[5] == x[5]) && (z[4] == x[4]) && (z[3] == x[3]) && (z[2] == x[2]) && (z[1] == x[1]) && (z[0] == x[0])
}

// IsZero returns z == 0
func (z *Element) IsZero() bool {
	return (z[11] | z[10] | z[9] | z[8] | z[7] | z[6] | z[5] | z[4] | z[3] | z[2] | z[1] | z[0]) == 0
}

// IsUint64 returns true if z[0] >= 0 and all other words are 0
func (z *Element) IsUint64() bool {
	return (z[11] | z[10] | z[9] | z[8] | z[7] | z[6] | z[5] | z[4] | z[3] | z[2] | z[1]) == 0
}

// Cmp compares (lexicographic order) z and x and returns:
//
//   -1 if z <  x
//    0 if z == x
//   +1 if z >  x
//
func (z *Element) Cmp(x *Element) int {
	_z := *z
	_x := *x
	_z.FromMont()
	_x.FromMont()
	if _z[11] > _x[11] {
		return 1
	} else if _z[11] < _x[11] {
		return -1
	}
	if _z[10] > _x[10] {
		return 1
	} else if _z[10] < _x[10] {
		return -1
	}
	if _z[9] > _x[9] {
		return 1
	} else if _z[9] < _x[9] {
		return -1
	}
	if _z[8] > _x[8] {
		return 1
	} else if _z[8] < _x[8] {
		return -1
	}
	if _z[7] > _x[7] {
		return 1
	} else if _z[7] < _x[7] {
		return -1
	}
	if _z[6] > _x[6] {
		return 1
	} else if _z[6] < _x[6] {
		return -1
	}
	if _z[5] > _x[5] {
		return 1
	} else if _z[5] < _x[5] {
		return -1
	}
	if _z[4] > _x[4] {
		return 1
	} else if _z[4] < _x[4] {
		return -1
	}
	if _z[3] > _x[3] {
		return 1
	} else if _z[3] < _x[3] {
		return -1
	}
	if _z[2] > _x[2] {
		return 1
	} else if _z[2] < _x[2] {
		return -1
	}
	if _z[1] > _x[1] {
		return 1
	} else if _z[1] < _x[1] {
		return -1
	}
	if _z[0] > _x[0] {
		return 1
	} else if _z[0] < _x[0] {
		return -1
	}
	return 0
}

// LexicographicallyLargest returns true if this element is strictly lexicographically
// larger than its negation, false otherwise
func (z *Element) LexicographicallyLargest() bool {
	// adapted from github.com/zkcrypto/bls12_381
	// we check if the element is larger than (q-1) / 2
	// if z - (((q -1) / 2) + 1) have no underflow, then z > (q-1) / 2

	_z := *z
	_z.FromMont()

	var b uint64
	_, b = bits.Sub64(_z[0], 8813122258298994758, 0)
	_, b = bits.Sub64(_z[1], 17530436596166295617, b)
	_, b = bits.Sub64(_z[2], 794459099352289819, b)
	_, b = bits.Sub64(_z[3], 5499048394472281212, b)
	_, b = bits.Sub64(_z[4], 4102332782476656535, b)
	_, b = bits.Sub64(_z[5], 4847250296721440456, b)
	_, b = bits.Sub64(_z[6], 9360553153018859906, b)
	_, b = bits.Sub64(_z[7], 13275999395695981708, b)
	_, b = bits.Sub64(_z[8], 2972722064798244640, b)
	_, b = bits.Sub64(_z[9], 6670688895927624516, b)
	_, b = bits.Sub64(_z[10], 7549128776290762655, b)
	_, b = bits.Sub64(_z[11], 40941494391138053, b)

	return b == 0
}

// SetRandom sets z to a random element < q
func (z *Element) SetRandom() (*Element, error) {
	var bytes [96]byte
	if _, err := io.ReadFull(rand.Reader, bytes[:]); err != nil {
		return nil, err
	}
	z[0] = binary.BigEndian.Uint64(bytes[0:8])
	z[1] = binary.BigEndian.Uint64(bytes[8:16])
	z[2] = binary.BigEndian.Uint64(bytes[16:24])
	z[3] = binary.BigEndian.Uint64(bytes[24:32])
	z[4] = binary.BigEndian.Uint64(bytes[32:40])
	z[5] = binary.BigEndian.Uint64(bytes[40:48])
	z[6] = binary.BigEndian.Uint64(bytes[48:56])
	z[7] = binary.BigEndian.Uint64(bytes[56:64])
	z[8] = binary.BigEndian.Uint64(bytes[64:72])
	z[9] = binary.BigEndian.Uint64(bytes[72:80])
	z[10] = binary.BigEndian.Uint64(bytes[80:88])
	z[11] = binary.BigEndian.Uint64(bytes[88:96])
	z[11] %= 81882988782276106

	// if z > q --> z -= q
	// note: this is NOT constant time
	if !(z[11] < 81882988782276106 || (z[11] == 81882988782276106 && (z[10] < 15098257552581525310 || (z[10] == 15098257552581525310 && (z[9] < 13341377791855249032 || (z[9] == 13341377791855249032 && (z[8] < 5945444129596489281 || (z[8] == 5945444129596489281 && (z[7] < 8105254717682411801 || (z[7] == 8105254717682411801 && (z[6] < 274362232328168196 || (z[6] == 274362232328168196 && (z[5] < 9694500593442880912 || (z[5] == 9694500593442880912 && (z[4] < 8204665564953313070 || (z[4] == 8204665564953313070 && (z[3] < 10998096788944562424 || (z[3] == 10998096788944562424 && (z[2] < 1588918198704579639 || (z[2] == 1588918198704579639 && (z[1] < 16614129118623039618 || (z[1] == 16614129118623039618 && (z[0] < 17626244516597989515))))))))))))))))))))))) {
		var b uint64
		z[0], b = bits.Sub64(z[0], 17626244516597989515, 0)
		z[1], b = bits.Sub64(z[1], 16614129118623039618, b)
		z[2], b = bits.Sub64(z[2], 1588918198704579639, b)
		z[3], b = bits.Sub64(z[3], 10998096788944562424, b)
		z[4], b = bits.Sub64(z[4], 8204665564953313070, b)
		z[5], b = bits.Sub64(z[5], 9694500593442880912, b)
		z[6], b = bits.Sub64(z[6], 274362232328168196, b)
		z[7], b = bits.Sub64(z[7], 8105254717682411801, b)
		z[8], b = bits.Sub64(z[8], 5945444129596489281, b)
		z[9], b = bits.Sub64(z[9], 13341377791855249032, b)
		z[10], b = bits.Sub64(z[10], 15098257552581525310, b)
		z[11], _ = bits.Sub64(z[11], 81882988782276106, b)
	}

	return z, nil
}

// One returns 1 (in montgommery form)
func One() Element {
	var one Element
	one.SetOne()
	return one
}

// Halve sets z to z / 2 (mod p)
func (z *Element) Halve() {
	if z[0]&1 == 1 {
		var carry uint64

		// z = z + q
		z[0], carry = bits.Add64(z[0], 17626244516597989515, 0)
		z[1], carry = bits.Add64(z[1], 16614129118623039618, carry)
		z[2], carry = bits.Add64(z[2], 1588918198704579639, carry)
		z[3], carry = bits.Add64(z[3], 10998096788944562424, carry)
		z[4], carry = bits.Add64(z[4], 8204665564953313070, carry)
		z[5], carry = bits.Add64(z[5], 9694500593442880912, carry)
		z[6], carry = bits.Add64(z[6], 274362232328168196, carry)
		z[7], carry = bits.Add64(z[7], 8105254717682411801, carry)
		z[8], carry = bits.Add64(z[8], 5945444129596489281, carry)
		z[9], carry = bits.Add64(z[9], 13341377791855249032, carry)
		z[10], carry = bits.Add64(z[10], 15098257552581525310, carry)
		z[11], _ = bits.Add64(z[11], 81882988782276106, carry)

	}

	// z = z >> 1

	z[0] = z[0]>>1 | z[1]<<63
	z[1] = z[1]>>1 | z[2]<<63
	z[2] = z[2]>>1 | z[3]<<63
	z[3] = z[3]>>1 | z[4]<<63
	z[4] = z[4]>>1 | z[5]<<63
	z[5] = z[5]>>1 | z[6]<<63
	z[6] = z[6]>>1 | z[7]<<63
	z[7] = z[7]>>1 | z[8]<<63
	z[8] = z[8]>>1 | z[9]<<63
	z[9] = z[9]>>1 | z[10]<<63
	z[10] = z[10]>>1 | z[11]<<63
	z[11] >>= 1

}

// API with assembly impl

// Mul z = x * y mod q
// see https://hackmd.io/@zkteam/modular_multiplication
func (z *Element) Mul(x, y *Element) *Element {
	mul(z, x, y)
	return z
}

// Square z = x * x mod q
// see https://hackmd.io/@zkteam/modular_multiplication
func (z *Element) Square(x *Element) *Element {
	mul(z, x, x)
	return z
}

// FromMont converts z in place (i.e. mutates) from Montgomery to regular representation
// sets and returns z = z * 1
func (z *Element) FromMont() *Element {
	fromMont(z)
	return z
}

// Add z = x + y mod q
func (z *Element) Add(x, y *Element) *Element {
	add(z, x, y)
	return z
}

// Double z = x + x mod q, aka Lsh 1
func (z *Element) Double(x *Element) *Element {
	double(z, x)
	return z
}

// Sub  z = x - y mod q
func (z *Element) Sub(x, y *Element) *Element {
	sub(z, x, y)
	return z
}

// Neg z = q - x
func (z *Element) Neg(x *Element) *Element {
	neg(z, x)
	return z
}

// Generic (no ADX instructions, no AMD64) versions of multiplication and squaring algorithms

func _mulGeneric(z, x, y *Element) {

	var t [12]uint64
	var c [3]uint64
	{
		// round 0
		v := x[0]
		c[1], c[0] = bits.Mul64(v, y[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd1(v, y[1], c[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd1(v, y[2], c[1])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd1(v, y[3], c[1])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd1(v, y[4], c[1])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd1(v, y[5], c[1])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd1(v, y[6], c[1])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd1(v, y[7], c[1])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd1(v, y[8], c[1])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd1(v, y[9], c[1])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd1(v, y[10], c[1])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd1(v, y[11], c[1])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 1
		v := x[1]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 2
		v := x[2]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 3
		v := x[3]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 4
		v := x[4]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 5
		v := x[5]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 6
		v := x[6]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 7
		v := x[7]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 8
		v := x[8]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 9
		v := x[9]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 10
		v := x[10]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], t[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], t[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], t[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], t[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], t[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], t[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], t[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], t[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], t[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], t[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		t[11], t[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}
	{
		// round 11
		v := x[11]
		c[1], c[0] = madd1(v, y[0], t[0])
		m := c[0] * 744663313386281181
		c[2] = madd0(m, 17626244516597989515, c[0])
		c[1], c[0] = madd2(v, y[1], c[1], t[1])
		c[2], z[0] = madd2(m, 16614129118623039618, c[2], c[0])
		c[1], c[0] = madd2(v, y[2], c[1], t[2])
		c[2], z[1] = madd2(m, 1588918198704579639, c[2], c[0])
		c[1], c[0] = madd2(v, y[3], c[1], t[3])
		c[2], z[2] = madd2(m, 10998096788944562424, c[2], c[0])
		c[1], c[0] = madd2(v, y[4], c[1], t[4])
		c[2], z[3] = madd2(m, 8204665564953313070, c[2], c[0])
		c[1], c[0] = madd2(v, y[5], c[1], t[5])
		c[2], z[4] = madd2(m, 9694500593442880912, c[2], c[0])
		c[1], c[0] = madd2(v, y[6], c[1], t[6])
		c[2], z[5] = madd2(m, 274362232328168196, c[2], c[0])
		c[1], c[0] = madd2(v, y[7], c[1], t[7])
		c[2], z[6] = madd2(m, 8105254717682411801, c[2], c[0])
		c[1], c[0] = madd2(v, y[8], c[1], t[8])
		c[2], z[7] = madd2(m, 5945444129596489281, c[2], c[0])
		c[1], c[0] = madd2(v, y[9], c[1], t[9])
		c[2], z[8] = madd2(m, 13341377791855249032, c[2], c[0])
		c[1], c[0] = madd2(v, y[10], c[1], t[10])
		c[2], z[9] = madd2(m, 15098257552581525310, c[2], c[0])
		c[1], c[0] = madd2(v, y[11], c[1], t[11])
		z[11], z[10] = madd3(m, 81882988782276106, c[0], c[2], c[1])
	}

	// if z > q --> z -= q
	// note: this is NOT constant time
	if !(z[11] < 81882988782276106 || (z[11] == 81882988782276106 && (z[10] < 15098257552581525310 || (z[10] == 15098257552581525310 && (z[9] < 13341377791855249032 || (z[9] == 13341377791855249032 && (z[8] < 5945444129596489281 || (z[8] == 5945444129596489281 && (z[7] < 8105254717682411801 || (z[7] == 8105254717682411801 && (z[6] < 274362232328168196 || (z[6] == 274362232328168196 && (z[5] < 9694500593442880912 || (z[5] == 9694500593442880912 && (z[4] < 8204665564953313070 || (z[4] == 8204665564953313070 && (z[3] < 10998096788944562424 || (z[3] == 10998096788944562424 && (z[2] < 1588918198704579639 || (z[2] == 1588918198704579639 && (z[1] < 16614129118623039618 || (z[1] == 16614129118623039618 && (z[0] < 17626244516597989515))))))))))))))))))))))) {
		var b uint64
		z[0], b = bits.Sub64(z[0], 17626244516597989515, 0)
		z[1], b = bits.Sub64(z[1], 16614129118623039618, b)
		z[2], b = bits.Sub64(z[2], 1588918198704579639, b)
		z[3], b = bits.Sub64(z[3], 10998096788944562424, b)
		z[4], b = bits.Sub64(z[4], 8204665564953313070, b)
		z[5], b = bits.Sub64(z[5], 9694500593442880912, b)
		z[6], b = bits.Sub64(z[6], 274362232328168196, b)
		z[7], b = bits.Sub64(z[7], 8105254717682411801, b)
		z[8], b = bits.Sub64(z[8], 5945444129596489281, b)
		z[9], b = bits.Sub64(z[9], 13341377791855249032, b)
		z[10], b = bits.Sub64(z[10], 15098257552581525310, b)
		z[11], _ = bits.Sub64(z[11], 81882988782276106, b)
	}
}

func _fromMontGeneric(z *Element) {
	// the following lines implement z = z * 1
	// with a modified CIOS montgomery multiplication
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}
	{
		// m = z[0]n'[0] mod W
		m := z[0] * 744663313386281181
		C := madd0(m, 17626244516597989515, z[0])
		C, z[0] = madd2(m, 16614129118623039618, z[1], C)
		C, z[1] = madd2(m, 1588918198704579639, z[2], C)
		C, z[2] = madd2(m, 10998096788944562424, z[3], C)
		C, z[3] = madd2(m, 8204665564953313070, z[4], C)
		C, z[4] = madd2(m, 9694500593442880912, z[5], C)
		C, z[5] = madd2(m, 274362232328168196, z[6], C)
		C, z[6] = madd2(m, 8105254717682411801, z[7], C)
		C, z[7] = madd2(m, 5945444129596489281, z[8], C)
		C, z[8] = madd2(m, 13341377791855249032, z[9], C)
		C, z[9] = madd2(m, 15098257552581525310, z[10], C)
		C, z[10] = madd2(m, 81882988782276106, z[11], C)
		z[11] = C
	}

	// if z > q --> z -= q
	// note: this is NOT constant time
	if !(z[11] < 81882988782276106 || (z[11] == 81882988782276106 && (z[10] < 15098257552581525310 || (z[10] == 15098257552581525310 && (z[9] < 13341377791855249032 || (z[9] == 13341377791855249032 && (z[8] < 5945444129596489281 || (z[8] == 5945444129596489281 && (z[7] < 8105254717682411801 || (z[7] == 8105254717682411801 && (z[6] < 274362232328168196 || (z[6] == 274362232328168196 && (z[5] < 9694500593442880912 || (z[5] == 9694500593442880912 && (z[4] < 8204665564953313070 || (z[4] == 8204665564953313070 && (z[3] < 10998096788944562424 || (z[3] == 10998096788944562424 && (z[2] < 1588918198704579639 || (z[2] == 1588918198704579639 && (z[1] < 16614129118623039618 || (z[1] == 16614129118623039618 && (z[0] < 17626244516597989515))))))))))))))))))))))) {
		var b uint64
		z[0], b = bits.Sub64(z[0], 17626244516597989515, 0)
		z[1], b = bits.Sub64(z[1], 16614129118623039618, b)
		z[2], b = bits.Sub64(z[2], 1588918198704579639, b)
		z[3], b = bits.Sub64(z[3], 10998096788944562424, b)
		z[4], b = bits.Sub64(z[4], 8204665564953313070, b)
		z[5], b = bits.Sub64(z[5], 9694500593442880912, b)
		z[6], b = bits.Sub64(z[6], 274362232328168196, b)
		z[7], b = bits.Sub64(z[7], 8105254717682411801, b)
		z[8], b = bits.Sub64(z[8], 5945444129596489281, b)
		z[9], b = bits.Sub64(z[9], 13341377791855249032, b)
		z[10], b = bits.Sub64(z[10], 15098257552581525310, b)
		z[11], _ = bits.Sub64(z[11], 81882988782276106, b)
	}
}

func _addGeneric(z, x, y *Element) {
	var carry uint64

	z[0], carry = bits.Add64(x[0], y[0], 0)
	z[1], carry = bits.Add64(x[1], y[1], carry)
	z[2], carry = bits.Add64(x[2], y[2], carry)
	z[3], carry = bits.Add64(x[3], y[3], carry)
	z[4], carry = bits.Add64(x[4], y[4], carry)
	z[5], carry = bits.Add64(x[5], y[5], carry)
	z[6], carry = bits.Add64(x[6], y[6], carry)
	z[7], carry = bits.Add64(x[7], y[7], carry)
	z[8], carry = bits.Add64(x[8], y[8], carry)
	z[9], carry = bits.Add64(x[9], y[9], carry)
	z[10], carry = bits.Add64(x[10], y[10], carry)
	z[11], _ = bits.Add64(x[11], y[11], carry)

	// if z > q --> z -= q
	// note: this is NOT constant time
	if !(z[11] < 81882988782276106 || (z[11] == 81882988782276106 && (z[10] < 15098257552581525310 || (z[10] == 15098257552581525310 && (z[9] < 13341377791855249032 || (z[9] == 13341377791855249032 && (z[8] < 5945444129596489281 || (z[8] == 5945444129596489281 && (z[7] < 8105254717682411801 || (z[7] == 8105254717682411801 && (z[6] < 274362232328168196 || (z[6] == 274362232328168196 && (z[5] < 9694500593442880912 || (z[5] == 9694500593442880912 && (z[4] < 8204665564953313070 || (z[4] == 8204665564953313070 && (z[3] < 10998096788944562424 || (z[3] == 10998096788944562424 && (z[2] < 1588918198704579639 || (z[2] == 1588918198704579639 && (z[1] < 16614129118623039618 || (z[1] == 16614129118623039618 && (z[0] < 17626244516597989515))))))))))))))))))))))) {
		var b uint64
		z[0], b = bits.Sub64(z[0], 17626244516597989515, 0)
		z[1], b = bits.Sub64(z[1], 16614129118623039618, b)
		z[2], b = bits.Sub64(z[2], 1588918198704579639, b)
		z[3], b = bits.Sub64(z[3], 10998096788944562424, b)
		z[4], b = bits.Sub64(z[4], 8204665564953313070, b)
		z[5], b = bits.Sub64(z[5], 9694500593442880912, b)
		z[6], b = bits.Sub64(z[6], 274362232328168196, b)
		z[7], b = bits.Sub64(z[7], 8105254717682411801, b)
		z[8], b = bits.Sub64(z[8], 5945444129596489281, b)
		z[9], b = bits.Sub64(z[9], 13341377791855249032, b)
		z[10], b = bits.Sub64(z[10], 15098257552581525310, b)
		z[11], _ = bits.Sub64(z[11], 81882988782276106, b)
	}
}

func _doubleGeneric(z, x *Element) {
	var carry uint64

	z[0], carry = bits.Add64(x[0], x[0], 0)
	z[1], carry = bits.Add64(x[1], x[1], carry)
	z[2], carry = bits.Add64(x[2], x[2], carry)
	z[3], carry = bits.Add64(x[3], x[3], carry)
	z[4], carry = bits.Add64(x[4], x[4], carry)
	z[5], carry = bits.Add64(x[5], x[5], carry)
	z[6], carry = bits.Add64(x[6], x[6], carry)
	z[7], carry = bits.Add64(x[7], x[7], carry)
	z[8], carry = bits.Add64(x[8], x[8], carry)
	z[9], carry = bits.Add64(x[9], x[9], carry)
	z[10], carry = bits.Add64(x[10], x[10], carry)
	z[11], _ = bits.Add64(x[11], x[11], carry)

	// if z > q --> z -= q
	// note: this is NOT constant time
	if !(z[11] < 81882988782276106 || (z[11] == 81882988782276106 && (z[10] < 15098257552581525310 || (z[10] == 15098257552581525310 && (z[9] < 13341377791855249032 || (z[9] == 13341377791855249032 && (z[8] < 5945444129596489281 || (z[8] == 5945444129596489281 && (z[7] < 8105254717682411801 || (z[7] == 8105254717682411801 && (z[6] < 274362232328168196 || (z[6] == 274362232328168196 && (z[5] < 9694500593442880912 || (z[5] == 9694500593442880912 && (z[4] < 8204665564953313070 || (z[4] == 8204665564953313070 && (z[3] < 10998096788944562424 || (z[3] == 10998096788944562424 && (z[2] < 1588918198704579639 || (z[2] == 1588918198704579639 && (z[1] < 16614129118623039618 || (z[1] == 16614129118623039618 && (z[0] < 17626244516597989515))))))))))))))))))))))) {
		var b uint64
		z[0], b = bits.Sub64(z[0], 17626244516597989515, 0)
		z[1], b = bits.Sub64(z[1], 16614129118623039618, b)
		z[2], b = bits.Sub64(z[2], 1588918198704579639, b)
		z[3], b = bits.Sub64(z[3], 10998096788944562424, b)
		z[4], b = bits.Sub64(z[4], 8204665564953313070, b)
		z[5], b = bits.Sub64(z[5], 9694500593442880912, b)
		z[6], b = bits.Sub64(z[6], 274362232328168196, b)
		z[7], b = bits.Sub64(z[7], 8105254717682411801, b)
		z[8], b = bits.Sub64(z[8], 5945444129596489281, b)
		z[9], b = bits.Sub64(z[9], 13341377791855249032, b)
		z[10], b = bits.Sub64(z[10], 15098257552581525310, b)
		z[11], _ = bits.Sub64(z[11], 81882988782276106, b)
	}
}

func _subGeneric(z, x, y *Element) {
	var b uint64
	z[0], b = bits.Sub64(x[0], y[0], 0)
	z[1], b = bits.Sub64(x[1], y[1], b)
	z[2], b = bits.Sub64(x[2], y[2], b)
	z[3], b = bits.Sub64(x[3], y[3], b)
	z[4], b = bits.Sub64(x[4], y[4], b)
	z[5], b = bits.Sub64(x[5], y[5], b)
	z[6], b = bits.Sub64(x[6], y[6], b)
	z[7], b = bits.Sub64(x[7], y[7], b)
	z[8], b = bits.Sub64(x[8], y[8], b)
	z[9], b = bits.Sub64(x[9], y[9], b)
	z[10], b = bits.Sub64(x[10], y[10], b)
	z[11], b = bits.Sub64(x[11], y[11], b)
	if b != 0 {
		var c uint64
		z[0], c = bits.Add64(z[0], 17626244516597989515, 0)
		z[1], c = bits.Add64(z[1], 16614129118623039618, c)
		z[2], c = bits.Add64(z[2], 1588918198704579639, c)
		z[3], c = bits.Add64(z[3], 10998096788944562424, c)
		z[4], c = bits.Add64(z[4], 8204665564953313070, c)
		z[5], c = bits.Add64(z[5], 9694500593442880912, c)
		z[6], c = bits.Add64(z[6], 274362232328168196, c)
		z[7], c = bits.Add64(z[7], 8105254717682411801, c)
		z[8], c = bits.Add64(z[8], 5945444129596489281, c)
		z[9], c = bits.Add64(z[9], 13341377791855249032, c)
		z[10], c = bits.Add64(z[10], 15098257552581525310, c)
		z[11], _ = bits.Add64(z[11], 81882988782276106, c)
	}
}

func _negGeneric(z, x *Element) {
	if x.IsZero() {
		z.SetZero()
		return
	}
	var borrow uint64
	z[0], borrow = bits.Sub64(17626244516597989515, x[0], 0)
	z[1], borrow = bits.Sub64(16614129118623039618, x[1], borrow)
	z[2], borrow = bits.Sub64(1588918198704579639, x[2], borrow)
	z[3], borrow = bits.Sub64(10998096788944562424, x[3], borrow)
	z[4], borrow = bits.Sub64(8204665564953313070, x[4], borrow)
	z[5], borrow = bits.Sub64(9694500593442880912, x[5], borrow)
	z[6], borrow = bits.Sub64(274362232328168196, x[6], borrow)
	z[7], borrow = bits.Sub64(8105254717682411801, x[7], borrow)
	z[8], borrow = bits.Sub64(5945444129596489281, x[8], borrow)
	z[9], borrow = bits.Sub64(13341377791855249032, x[9], borrow)
	z[10], borrow = bits.Sub64(15098257552581525310, x[10], borrow)
	z[11], _ = bits.Sub64(81882988782276106, x[11], borrow)
}

func _reduceGeneric(z *Element) {

	// if z > q --> z -= q
	// note: this is NOT constant time
	if !(z[11] < 81882988782276106 || (z[11] == 81882988782276106 && (z[10] < 15098257552581525310 || (z[10] == 15098257552581525310 && (z[9] < 13341377791855249032 || (z[9] == 13341377791855249032 && (z[8] < 5945444129596489281 || (z[8] == 5945444129596489281 && (z[7] < 8105254717682411801 || (z[7] == 8105254717682411801 && (z[6] < 274362232328168196 || (z[6] == 274362232328168196 && (z[5] < 9694500593442880912 || (z[5] == 9694500593442880912 && (z[4] < 8204665564953313070 || (z[4] == 8204665564953313070 && (z[3] < 10998096788944562424 || (z[3] == 10998096788944562424 && (z[2] < 1588918198704579639 || (z[2] == 1588918198704579639 && (z[1] < 16614129118623039618 || (z[1] == 16614129118623039618 && (z[0] < 17626244516597989515))))))))))))))))))))))) {
		var b uint64
		z[0], b = bits.Sub64(z[0], 17626244516597989515, 0)
		z[1], b = bits.Sub64(z[1], 16614129118623039618, b)
		z[2], b = bits.Sub64(z[2], 1588918198704579639, b)
		z[3], b = bits.Sub64(z[3], 10998096788944562424, b)
		z[4], b = bits.Sub64(z[4], 8204665564953313070, b)
		z[5], b = bits.Sub64(z[5], 9694500593442880912, b)
		z[6], b = bits.Sub64(z[6], 274362232328168196, b)
		z[7], b = bits.Sub64(z[7], 8105254717682411801, b)
		z[8], b = bits.Sub64(z[8], 5945444129596489281, b)
		z[9], b = bits.Sub64(z[9], 13341377791855249032, b)
		z[10], b = bits.Sub64(z[10], 15098257552581525310, b)
		z[11], _ = bits.Sub64(z[11], 81882988782276106, b)
	}
}

func mulByConstant(z *Element, c uint8) {
	switch c {
	case 0:
		z.SetZero()
		return
	case 1:
		return
	case 2:
		z.Double(z)
		return
	case 3:
		_z := *z
		z.Double(z).Add(z, &_z)
	case 5:
		_z := *z
		z.Double(z).Double(z).Add(z, &_z)
	default:
		var y Element
		y.SetUint64(uint64(c))
		z.Mul(z, &y)
	}
}

// BatchInvert returns a new slice with every element inverted.
// Uses Montgomery batch inversion trick
func BatchInvert(a []Element) []Element {
	res := make([]Element, len(a))
	if len(a) == 0 {
		return res
	}

	zeroes := make([]bool, len(a))
	accumulator := One()

	for i := 0; i < len(a); i++ {
		if a[i].IsZero() {
			zeroes[i] = true
			continue
		}
		res[i] = accumulator
		accumulator.Mul(&accumulator, &a[i])
	}

	accumulator.Inverse(&accumulator)

	for i := len(a) - 1; i >= 0; i-- {
		if zeroes[i] {
			continue
		}
		res[i].Mul(&res[i], &accumulator)
		accumulator.Mul(&accumulator, &a[i])
	}

	return res
}

func _butterflyGeneric(a, b *Element) {
	t := *a
	a.Add(a, b)
	b.Sub(&t, b)
}

// BitLen returns the minimum number of bits needed to represent z
// returns 0 if z == 0
func (z *Element) BitLen() int {
	if z[11] != 0 {
		return 704 + bits.Len64(z[11])
	}
	if z[10] != 0 {
		return 640 + bits.Len64(z[10])
	}
	if z[9] != 0 {
		return 576 + bits.Len64(z[9])
	}
	if z[8] != 0 {
		return 512 + bits.Len64(z[8])
	}
	if z[7] != 0 {
		return 448 + bits.Len64(z[7])
	}
	if z[6] != 0 {
		return 384 + bits.Len64(z[6])
	}
	if z[5] != 0 {
		return 320 + bits.Len64(z[5])
	}
	if z[4] != 0 {
		return 256 + bits.Len64(z[4])
	}
	if z[3] != 0 {
		return 192 + bits.Len64(z[3])
	}
	if z[2] != 0 {
		return 128 + bits.Len64(z[2])
	}
	if z[1] != 0 {
		return 64 + bits.Len64(z[1])
	}
	return bits.Len64(z[0])
}

// Exp z = x^exponent mod q
func (z *Element) Exp(x Element, exponent *big.Int) *Element {
	var bZero big.Int
	if exponent.Cmp(&bZero) == 0 {
		return z.SetOne()
	}

	z.Set(&x)

	for i := exponent.BitLen() - 2; i >= 0; i-- {
		z.Square(z)
		if exponent.Bit(i) == 1 {
			z.Mul(z, &x)
		}
	}

	return z
}

// ToMont converts z to Montgomery form
// sets and returns z = z * r^2
func (z *Element) ToMont() *Element {
	return z.Mul(z, &rSquare)
}

// ToRegular returns z in regular form (doesn't mutate z)
func (z Element) ToRegular() Element {
	return *z.FromMont()
}

// String returns the string form of an Element in Montgomery form
func (z *Element) String() string {
	zz := *z
	zz.FromMont()
	if zz.IsUint64() {
		return strconv.FormatUint(zz[0], 10)
	} else {
		var zzNeg Element
		zzNeg.Neg(z)
		zzNeg.FromMont()
		if zzNeg.IsUint64() {
			return "-" + strconv.FormatUint(zzNeg[0], 10)
		}
	}
	vv := bigIntPool.Get().(*big.Int)
	defer bigIntPool.Put(vv)
	return zz.ToBigInt(vv).String()
}

// ToBigInt returns z as a big.Int in Montgomery form
func (z *Element) ToBigInt(res *big.Int) *big.Int {
	var b [Limbs * 8]byte
	binary.BigEndian.PutUint64(b[88:96], z[0])
	binary.BigEndian.PutUint64(b[80:88], z[1])
	binary.BigEndian.PutUint64(b[72:80], z[2])
	binary.BigEndian.PutUint64(b[64:72], z[3])
	binary.BigEndian.PutUint64(b[56:64], z[4])
	binary.BigEndian.PutUint64(b[48:56], z[5])
	binary.BigEndian.PutUint64(b[40:48], z[6])
	binary.BigEndian.PutUint64(b[32:40], z[7])
	binary.BigEndian.PutUint64(b[24:32], z[8])
	binary.BigEndian.PutUint64(b[16:24], z[9])
	binary.BigEndian.PutUint64(b[8:16], z[10])
	binary.BigEndian.PutUint64(b[0:8], z[11])

	return res.SetBytes(b[:])
}

// ToBigIntRegular returns z as a big.Int in regular form
func (z Element) ToBigIntRegular(res *big.Int) *big.Int {
	z.FromMont()
	return z.ToBigInt(res)
}

// Bytes returns the regular (non montgomery) value
// of z as a big-endian byte array.
func (z *Element) Bytes() (res [Limbs * 8]byte) {
	_z := z.ToRegular()
	binary.BigEndian.PutUint64(res[88:96], _z[0])
	binary.BigEndian.PutUint64(res[80:88], _z[1])
	binary.BigEndian.PutUint64(res[72:80], _z[2])
	binary.BigEndian.PutUint64(res[64:72], _z[3])
	binary.BigEndian.PutUint64(res[56:64], _z[4])
	binary.BigEndian.PutUint64(res[48:56], _z[5])
	binary.BigEndian.PutUint64(res[40:48], _z[6])
	binary.BigEndian.PutUint64(res[32:40], _z[7])
	binary.BigEndian.PutUint64(res[24:32], _z[8])
	binary.BigEndian.PutUint64(res[16:24], _z[9])
	binary.BigEndian.PutUint64(res[8:16], _z[10])
	binary.BigEndian.PutUint64(res[0:8], _z[11])

	return
}

// Marshal returns the regular (non montgomery) value
// of z as a big-endian byte slice.
func (z *Element) Marshal() []byte {
	b := z.Bytes()
	return b[:]
}

// SetBytes interprets e as the bytes of a big-endian unsigned integer,
// sets z to that value (in Montgomery form), and returns z.
func (z *Element) SetBytes(e []byte) *Element {
	// get a big int from our pool
	vv := bigIntPool.Get().(*big.Int)
	vv.SetBytes(e)

	// set big int
	z.SetBigInt(vv)

	// put temporary object back in pool
	bigIntPool.Put(vv)

	return z
}

// SetBigInt sets z to v (regular form) and returns z in Montgomery form
func (z *Element) SetBigInt(v *big.Int) *Element {
	z.SetZero()

	var zero big.Int

	// fast path
	c := v.Cmp(&_modulus)
	if c == 0 {
		// v == 0
		return z
	} else if c != 1 && v.Cmp(&zero) != -1 {
		// 0 < v < q
		return z.setBigInt(v)
	}

	// get temporary big int from the pool
	vv := bigIntPool.Get().(*big.Int)

	// copy input + modular reduction
	vv.Set(v)
	vv.Mod(v, &_modulus)

	// set big int byte value
	z.setBigInt(vv)

	// release object into pool
	bigIntPool.Put(vv)
	return z
}

// setBigInt assumes 0 <= v < q
func (z *Element) setBigInt(v *big.Int) *Element {
	vBits := v.Bits()

	if bits.UintSize == 64 {
		for i := 0; i < len(vBits); i++ {
			z[i] = uint64(vBits[i])
		}
	} else {
		for i := 0; i < len(vBits); i++ {
			if i%2 == 0 {
				z[i/2] = uint64(vBits[i])
			} else {
				z[i/2] |= uint64(vBits[i]) << 32
			}
		}
	}

	return z.ToMont()
}

// SetString creates a big.Int with s (in base 10) and calls SetBigInt on z
func (z *Element) SetString(s string) *Element {
	// get temporary big int from the pool
	vv := bigIntPool.Get().(*big.Int)

	if _, ok := vv.SetString(s, 10); !ok {
		panic("Element.SetString failed -> can't parse number in base10 into a big.Int")
	}
	z.SetBigInt(vv)

	// release object into pool
	bigIntPool.Put(vv)

	return z
}

var (
	_bLegendreExponentElement *big.Int
	_bSqrtExponentElement     *big.Int
)

func init() {
	_bLegendreExponentElement, _ = new(big.Int).SetString("9174127dc1e70568c3e4a0027d7f9f5c930c3540e8a34429413af7c043df20b83dd31c72c2748c81e75d7f92da11824344e476897cfec838ee69ee39f5ff974c508b612b33d47c0b067c577578521bf3489f34380000417a4e800000000045", 16)
	const sqrtExponentElement = "48ba093ee0f382b461f250013ebfcfae49861aa07451a214a09d7be021ef905c1ee98e39613a4640f3aebfc96d08c121a2723b44be7f641c7734f71cfaffcba62845b09599ea3e05833e2bbabc290df9a44f9a1c000020bd27400000000023"
	_bSqrtExponentElement, _ = new(big.Int).SetString(sqrtExponentElement, 16)
}

// Legendre returns the Legendre symbol of z (either +1, -1, or 0.)
func (z *Element) Legendre() int {
	var l Element
	// z^((q-1)/2)
	l.Exp(*z, _bLegendreExponentElement)

	if l.IsZero() {
		return 0
	}

	// if l == 1
	if (l[11] == 23071597697427581) && (l[10] == 15539704305423854047) && (l[9] == 5009280847225881135) && (l[8] == 8887388221587179644) && (l[7] == 2545351818702954755) && (l[6] == 12055474021000362245) && (l[5] == 13899911246788437003) && (l[4] == 17071399330169272331) && (l[3] == 15738672438262922740) && (l[2] == 11428286765660613342) && (l[1] == 6509995272855063783) && (l[0] == 144959613005956565) {
		return 1
	}
	return -1
}

// Sqrt z = √x mod q
// if the square root doesn't exist (x is not a square mod q)
// Sqrt leaves z unchanged and returns nil
func (z *Element) Sqrt(x *Element) *Element {
	// q ≡ 3 (mod 4)
	// using  z ≡ ± x^((p+1)/4) (mod q)
	var y, square Element
	y.Exp(*x, _bSqrtExponentElement)
	// as we didn't compute the legendre symbol, ensure we found y such that y * y = x
	square.Square(&y)
	if square.Equal(x) {
		return z.Set(&y)
	}
	return nil
}

// Inverse z = x^-1 mod q
// Algorithm 16 in "Efficient Software-Implementation of Finite Fields with Applications to Cryptography"
// if x == 0, sets and returns z = x
func (z *Element) Inverse(x *Element) *Element {
	if x.IsZero() {
		z.SetZero()
		return z
	}

	// initialize u = q
	var u = Element{
		17626244516597989515,
		16614129118623039618,
		1588918198704579639,
		10998096788944562424,
		8204665564953313070,
		9694500593442880912,
		274362232328168196,
		8105254717682411801,
		5945444129596489281,
		13341377791855249032,
		15098257552581525310,
		81882988782276106,
	}

	// initialize s = r^2
	var s = Element{
		14305184132582319705,
		8868935336694416555,
		9196887162930508889,
		15486798265448570248,
		5402985275949444416,
		10893197322525159598,
		3204916688966998390,
		12417238192559061753,
		12426306557607898622,
		1305582522441154384,
		10311846026977660324,
		48736111365249031,
	}

	// r = 0
	r := Element{}

	v := *x

	var carry, borrow uint64
	var bigger bool

	for {
		for v[0]&1 == 0 {

			// v = v >> 1

			v[0] = v[0]>>1 | v[1]<<63
			v[1] = v[1]>>1 | v[2]<<63
			v[2] = v[2]>>1 | v[3]<<63
			v[3] = v[3]>>1 | v[4]<<63
			v[4] = v[4]>>1 | v[5]<<63
			v[5] = v[5]>>1 | v[6]<<63
			v[6] = v[6]>>1 | v[7]<<63
			v[7] = v[7]>>1 | v[8]<<63
			v[8] = v[8]>>1 | v[9]<<63
			v[9] = v[9]>>1 | v[10]<<63
			v[10] = v[10]>>1 | v[11]<<63
			v[11] >>= 1

			if s[0]&1 == 1 {

				// s = s + q
				s[0], carry = bits.Add64(s[0], 17626244516597989515, 0)
				s[1], carry = bits.Add64(s[1], 16614129118623039618, carry)
				s[2], carry = bits.Add64(s[2], 1588918198704579639, carry)
				s[3], carry = bits.Add64(s[3], 10998096788944562424, carry)
				s[4], carry = bits.Add64(s[4], 8204665564953313070, carry)
				s[5], carry = bits.Add64(s[5], 9694500593442880912, carry)
				s[6], carry = bits.Add64(s[6], 274362232328168196, carry)
				s[7], carry = bits.Add64(s[7], 8105254717682411801, carry)
				s[8], carry = bits.Add64(s[8], 5945444129596489281, carry)
				s[9], carry = bits.Add64(s[9], 13341377791855249032, carry)
				s[10], carry = bits.Add64(s[10], 15098257552581525310, carry)
				s[11], _ = bits.Add64(s[11], 81882988782276106, carry)

			}

			// s = s >> 1

			s[0] = s[0]>>1 | s[1]<<63
			s[1] = s[1]>>1 | s[2]<<63
			s[2] = s[2]>>1 | s[3]<<63
			s[3] = s[3]>>1 | s[4]<<63
			s[4] = s[4]>>1 | s[5]<<63
			s[5] = s[5]>>1 | s[6]<<63
			s[6] = s[6]>>1 | s[7]<<63
			s[7] = s[7]>>1 | s[8]<<63
			s[8] = s[8]>>1 | s[9]<<63
			s[9] = s[9]>>1 | s[10]<<63
			s[10] = s[10]>>1 | s[11]<<63
			s[11] >>= 1

		}
		for u[0]&1 == 0 {

			// u = u >> 1

			u[0] = u[0]>>1 | u[1]<<63
			u[1] = u[1]>>1 | u[2]<<63
			u[2] = u[2]>>1 | u[3]<<63
			u[3] = u[3]>>1 | u[4]<<63
			u[4] = u[4]>>1 | u[5]<<63
			u[5] = u[5]>>1 | u[6]<<63
			u[6] = u[6]>>1 | u[7]<<63
			u[7] = u[7]>>1 | u[8]<<63
			u[8] = u[8]>>1 | u[9]<<63
			u[9] = u[9]>>1 | u[10]<<63
			u[10] = u[10]>>1 | u[11]<<63
			u[11] >>= 1

			if r[0]&1 == 1 {

				// r = r + q
				r[0], carry = bits.Add64(r[0], 17626244516597989515, 0)
				r[1], carry = bits.Add64(r[1], 16614129118623039618, carry)
				r[2], carry = bits.Add64(r[2], 1588918198704579639, carry)
				r[3], carry = bits.Add64(r[3], 10998096788944562424, carry)
				r[4], carry = bits.Add64(r[4], 8204665564953313070, carry)
				r[5], carry = bits.Add64(r[5], 9694500593442880912, carry)
				r[6], carry = bits.Add64(r[6], 274362232328168196, carry)
				r[7], carry = bits.Add64(r[7], 8105254717682411801, carry)
				r[8], carry = bits.Add64(r[8], 5945444129596489281, carry)
				r[9], carry = bits.Add64(r[9], 13341377791855249032, carry)
				r[10], carry = bits.Add64(r[10], 15098257552581525310, carry)
				r[11], _ = bits.Add64(r[11], 81882988782276106, carry)

			}

			// r = r >> 1

			r[0] = r[0]>>1 | r[1]<<63
			r[1] = r[1]>>1 | r[2]<<63
			r[2] = r[2]>>1 | r[3]<<63
			r[3] = r[3]>>1 | r[4]<<63
			r[4] = r[4]>>1 | r[5]<<63
			r[5] = r[5]>>1 | r[6]<<63
			r[6] = r[6]>>1 | r[7]<<63
			r[7] = r[7]>>1 | r[8]<<63
			r[8] = r[8]>>1 | r[9]<<63
			r[9] = r[9]>>1 | r[10]<<63
			r[10] = r[10]>>1 | r[11]<<63
			r[11] >>= 1

		}

		// v >= u
		bigger = !(v[11] < u[11] || (v[11] == u[11] && (v[10] < u[10] || (v[10] == u[10] && (v[9] < u[9] || (v[9] == u[9] && (v[8] < u[8] || (v[8] == u[8] && (v[7] < u[7] || (v[7] == u[7] && (v[6] < u[6] || (v[6] == u[6] && (v[5] < u[5] || (v[5] == u[5] && (v[4] < u[4] || (v[4] == u[4] && (v[3] < u[3] || (v[3] == u[3] && (v[2] < u[2] || (v[2] == u[2] && (v[1] < u[1] || (v[1] == u[1] && (v[0] < u[0])))))))))))))))))))))))

		if bigger {

			// v = v - u
			v[0], borrow = bits.Sub64(v[0], u[0], 0)
			v[1], borrow = bits.Sub64(v[1], u[1], borrow)
			v[2], borrow = bits.Sub64(v[2], u[2], borrow)
			v[3], borrow = bits.Sub64(v[3], u[3], borrow)
			v[4], borrow = bits.Sub64(v[4], u[4], borrow)
			v[5], borrow = bits.Sub64(v[5], u[5], borrow)
			v[6], borrow = bits.Sub64(v[6], u[6], borrow)
			v[7], borrow = bits.Sub64(v[7], u[7], borrow)
			v[8], borrow = bits.Sub64(v[8], u[8], borrow)
			v[9], borrow = bits.Sub64(v[9], u[9], borrow)
			v[10], borrow = bits.Sub64(v[10], u[10], borrow)
			v[11], _ = bits.Sub64(v[11], u[11], borrow)

			// s = s - r
			s[0], borrow = bits.Sub64(s[0], r[0], 0)
			s[1], borrow = bits.Sub64(s[1], r[1], borrow)
			s[2], borrow = bits.Sub64(s[2], r[2], borrow)
			s[3], borrow = bits.Sub64(s[3], r[3], borrow)
			s[4], borrow = bits.Sub64(s[4], r[4], borrow)
			s[5], borrow = bits.Sub64(s[5], r[5], borrow)
			s[6], borrow = bits.Sub64(s[6], r[6], borrow)
			s[7], borrow = bits.Sub64(s[7], r[7], borrow)
			s[8], borrow = bits.Sub64(s[8], r[8], borrow)
			s[9], borrow = bits.Sub64(s[9], r[9], borrow)
			s[10], borrow = bits.Sub64(s[10], r[10], borrow)
			s[11], borrow = bits.Sub64(s[11], r[11], borrow)

			if borrow == 1 {

				// s = s + q
				s[0], carry = bits.Add64(s[0], 17626244516597989515, 0)
				s[1], carry = bits.Add64(s[1], 16614129118623039618, carry)
				s[2], carry = bits.Add64(s[2], 1588918198704579639, carry)
				s[3], carry = bits.Add64(s[3], 10998096788944562424, carry)
				s[4], carry = bits.Add64(s[4], 8204665564953313070, carry)
				s[5], carry = bits.Add64(s[5], 9694500593442880912, carry)
				s[6], carry = bits.Add64(s[6], 274362232328168196, carry)
				s[7], carry = bits.Add64(s[7], 8105254717682411801, carry)
				s[8], carry = bits.Add64(s[8], 5945444129596489281, carry)
				s[9], carry = bits.Add64(s[9], 13341377791855249032, carry)
				s[10], carry = bits.Add64(s[10], 15098257552581525310, carry)
				s[11], _ = bits.Add64(s[11], 81882988782276106, carry)

			}
		} else {

			// u = u - v
			u[0], borrow = bits.Sub64(u[0], v[0], 0)
			u[1], borrow = bits.Sub64(u[1], v[1], borrow)
			u[2], borrow = bits.Sub64(u[2], v[2], borrow)
			u[3], borrow = bits.Sub64(u[3], v[3], borrow)
			u[4], borrow = bits.Sub64(u[4], v[4], borrow)
			u[5], borrow = bits.Sub64(u[5], v[5], borrow)
			u[6], borrow = bits.Sub64(u[6], v[6], borrow)
			u[7], borrow = bits.Sub64(u[7], v[7], borrow)
			u[8], borrow = bits.Sub64(u[8], v[8], borrow)
			u[9], borrow = bits.Sub64(u[9], v[9], borrow)
			u[10], borrow = bits.Sub64(u[10], v[10], borrow)
			u[11], _ = bits.Sub64(u[11], v[11], borrow)

			// r = r - s
			r[0], borrow = bits.Sub64(r[0], s[0], 0)
			r[1], borrow = bits.Sub64(r[1], s[1], borrow)
			r[2], borrow = bits.Sub64(r[2], s[2], borrow)
			r[3], borrow = bits.Sub64(r[3], s[3], borrow)
			r[4], borrow = bits.Sub64(r[4], s[4], borrow)
			r[5], borrow = bits.Sub64(r[5], s[5], borrow)
			r[6], borrow = bits.Sub64(r[6], s[6], borrow)
			r[7], borrow = bits.Sub64(r[7], s[7], borrow)
			r[8], borrow = bits.Sub64(r[8], s[8], borrow)
			r[9], borrow = bits.Sub64(r[9], s[9], borrow)
			r[10], borrow = bits.Sub64(r[10], s[10], borrow)
			r[11], borrow = bits.Sub64(r[11], s[11], borrow)

			if borrow == 1 {

				// r = r + q
				r[0], carry = bits.Add64(r[0], 17626244516597989515, 0)
				r[1], carry = bits.Add64(r[1], 16614129118623039618, carry)
				r[2], carry = bits.Add64(r[2], 1588918198704579639, carry)
				r[3], carry = bits.Add64(r[3], 10998096788944562424, carry)
				r[4], carry = bits.Add64(r[4], 8204665564953313070, carry)
				r[5], carry = bits.Add64(r[5], 9694500593442880912, carry)
				r[6], carry = bits.Add64(r[6], 274362232328168196, carry)
				r[7], carry = bits.Add64(r[7], 8105254717682411801, carry)
				r[8], carry = bits.Add64(r[8], 5945444129596489281, carry)
				r[9], carry = bits.Add64(r[9], 13341377791855249032, carry)
				r[10], carry = bits.Add64(r[10], 15098257552581525310, carry)
				r[11], _ = bits.Add64(r[11], 81882988782276106, carry)

			}
		}
		if (u[0] == 1) && (u[11]|u[10]|u[9]|u[8]|u[7]|u[6]|u[5]|u[4]|u[3]|u[2]|u[1]) == 0 {
			z.Set(&r)
			return z
		}
		if (v[0] == 1) && (v[11]|v[10]|v[9]|v[8]|v[7]|v[6]|v[5]|v[4]|v[3]|v[2]|v[1]) == 0 {
			z.Set(&s)
			return z
		}
	}

}