src/crypto/elliptic/internal/fiat/p521_invert.go

// Copyright 2021 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Code generated by addchain. DO NOT EDIT.

package fiat

// Invert sets e = 1/x, and returns e.
//
// If x == 0, Invert returns e = 0.
func (e *P521Element) Invert(x *P521Element) *P521Element {
	// Inversion is implemented as exponentiation with exponent p − 2.
	// The sequence of 13 multiplications and 520 squarings is derived from the
	// following addition chain generated with github.com/mmcloughlin/addchain v0.3.0.
	//
	//	_10       = 2*1
	//	_11       = 1 + _10
	//	_1100     = _11 << 2
	//	_1111     = _11 + _1100
	//	_11110000 = _1111 << 4
	//	_11111111 = _1111 + _11110000
	//	x16       = _11111111 << 8 + _11111111
	//	x32       = x16 << 16 + x16
	//	x64       = x32 << 32 + x32
	//	x65       = 2*x64 + 1
	//	x129      = x65 << 64 + x64
	//	x130      = 2*x129 + 1
	//	x259      = x130 << 129 + x129
	//	x260      = 2*x259 + 1
	//	x519      = x260 << 259 + x259
	//	return      x519 << 2 + 1
	//

	var z = new(P521Element).Set(e)
	var t0 = new(P521Element)

	z.Square(x)
	z.Mul(x, z)
	t0.Square(z)
	for s := 1; s < 2; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	t0.Square(z)
	for s := 1; s < 4; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	t0.Square(z)
	for s := 1; s < 8; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	t0.Square(z)
	for s := 1; s < 16; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	t0.Square(z)
	for s := 1; s < 32; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	t0.Square(z)
	t0.Mul(x, t0)
	for s := 0; s < 64; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	t0.Square(z)
	t0.Mul(x, t0)
	for s := 0; s < 129; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	t0.Square(z)
	t0.Mul(x, t0)
	for s := 0; s < 259; s++ {
		t0.Square(t0)
	}
	z.Mul(z, t0)
	for s := 0; s < 2; s++ {
		z.Square(z)
	}
	z.Mul(x, z)

	return e.Set(z)
}