{
		Element:  "P521Element",
		Prime:    "2^521 - 1",
		Prefix:   "p521",
		FiatType: "[9]uint64",
		BytesLen: 66,
	},
}

func main() {
	t := template.Must(template.New("montgomery").Parse(tmplWrapper))

	tmplAddchainFile, err := os.CreateTemp("", "addchain-template")
	if err != nil {
		log.Fatal(err)
	}
	defer os.Remove(tmplAddchainFile.Name())

	"errors"
)

// P256Element is an integer modulo 2^256 - 2^224 + 2^192 + 2^96 - 1.
//
// The zero value is a valid zero element.
type P256Element struct {
	// Values are represented internally always in the Montgomery domain, and
	// converted in Bytes and SetBytes.
	x p256MontgomeryDomainFieldElement
}

const p256ElementLen = 32

type p256UntypedFieldElement = [4]uint64

// One sets e = 1, and returns e.

	"errors"
)

// P384Element is an integer modulo 2^384 - 2^128 - 2^96 + 2^32 - 1.
//
// The zero value is a valid zero element.
type P384Element struct {
	// Values are represented internally always in the Montgomery domain, and
	// converted in Bytes and SetBytes.
	x p384MontgomeryDomainFieldElement
}

const p384ElementLen = 48

type p384UntypedFieldElement = [6]uint64

// One sets e = 1, and returns e.

import (
	"crypto/subtle"
	"errors"
)

// P521Element is an integer modulo 2^521 - 1.
//
// The zero value is a valid zero element.
type P521Element struct {
	// Values are represented internally always in the Montgomery domain, and
	// converted in Bytes and SetBytes.
	x p521MontgomeryDomainFieldElement
}

const p521ElementLen = 66

type p521UntypedFieldElement = [9]uint64

// One sets e = 1, and returns e.

//
// Bounds: [[0x0 ~> 0xffffffffffffffff], [0x0 ~> 0xffffffffffffffff], [0x0 ~> 0xffffffffffffffff], [0x0 ~> 0xffffffffffffffff], [0x0 ~> 0xffffffffffffffff], [0x0 ~> 0xffffffffffffffff]]
type p384MontgomeryDomainFieldElement [6]uint64

// The type p384NonMontgomeryDomainFieldElement is a field element NOT in the Montgomery domain.
//

		k0 := Word(new(Int).ModInverse(k, _B).Uint64())
		if k0 != Word(test.k0) {
			t.Errorf("#%d: k0 in table=%#x, computed=%#x\n", i, test.k0, k0)
		}

		// check montgomery with correct k0 produces correct output
		z := nat(nil).montgomery(x, y, m, k0, len(m))
		z = z.norm()
		if z.cmp(out) != 0 {
			t.Errorf("#%d: got 0x%s want 0x%s", i, z.utoa(16), out.utoa(16))
		}
	}
}

var expNNTests = []struct {

//
//
//
// NOTE: In addition to the bounds specified above each function, all
//
//   functions synthesized for this Montgomery arithmetic require the
//
//   input to be strictly less than the prime modulus (m), and also
//
//   require the input to be in the unique saturated representation.
//

	expected := &Nat{[]uint{1}}
	if out.Equal(expected) != 1 {
		t.Errorf("%+v != %+v", out, expected)
	}
}

// TestMulReductions tests that Mul reduces results equal or slightly greater
// than the modulus. Some Montgomery algorithms don't and need extra care to
// return correct results. See https://go.dev/issue/13907.
func TestMulReductions(t *testing.T) {
	// Two short but multi-limb primes.

// Divisibility x%c == 0 can be checked more efficiently than directly computing
// the modulus x%c and comparing against 0.
//
// The same "Division by invariant integers using multiplication" paper
// by Granlund and Montgomery referenced above briefly mentions this method
// and it is further elaborated in "Hacker's Delight" by Warren Section 10-17
//
// The first thing to note is that for odd integers, exact division can be computed

	// and is implemented by this package without CRT optimizations to limit
	// complexity.
	CRTValues []CRTValue

	n, p, q *bigmod.Modulus // moduli for CRT with Montgomery precomputed constants
}

// CRTValue contains the precomputed Chinese remainder theorem values.
type CRTValue struct {
	Exp   *big.Int // D mod (prime-1).
	Coeff *big.Int // R·Coeff ≡ 1 mod Prime.