blob: d0101e1d4fe3b954ab0de5a4ee6c5e4dd93b8153 [file] [log] [blame]
// 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 *P256Element) Invert(x *P256Element) *P256Element {
// Inversion is implemented as exponentiation with exponent p − 2.
// The sequence of 12 multiplications and 255 squarings is derived from the
// following addition chain generated with github.com/mmcloughlin/addchain v0.4.0.
//
// _10 = 2*1
// _11 = 1 + _10
// _110 = 2*_11
// _111 = 1 + _110
// _111000 = _111 << 3
// _111111 = _111 + _111000
// x12 = _111111 << 6 + _111111
// x15 = x12 << 3 + _111
// x16 = 2*x15 + 1
// x32 = x16 << 16 + x16
// i53 = x32 << 15
// x47 = x15 + i53
// i263 = ((i53 << 17 + 1) << 143 + x47) << 47
// return (x47 + i263) << 2 + 1
//
var z = new(P256Element).Set(e)
var t0 = new(P256Element)
var t1 = new(P256Element)
z.Square(x)
z.Mul(x, z)
z.Square(z)
z.Mul(x, z)
t0.Square(z)
for s := 1; s < 3; s++ {
t0.Square(t0)
}
t0.Mul(z, t0)
t1.Square(t0)
for s := 1; s < 6; s++ {
t1.Square(t1)
}
t0.Mul(t0, t1)
for s := 0; s < 3; s++ {
t0.Square(t0)
}
z.Mul(z, t0)
t0.Square(z)
t0.Mul(x, t0)
t1.Square(t0)
for s := 1; s < 16; s++ {
t1.Square(t1)
}
t0.Mul(t0, t1)
for s := 0; s < 15; s++ {
t0.Square(t0)
}
z.Mul(z, t0)
for s := 0; s < 17; s++ {
t0.Square(t0)
}
t0.Mul(x, t0)
for s := 0; s < 143; s++ {
t0.Square(t0)
}
t0.Mul(z, t0)
for s := 0; s < 47; 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)
}