p521_invert.go

     1  // Copyright 2021 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Code generated by addchain. DO NOT EDIT.
     6  
     7  package fiat
     8  
     9  // Invert sets e = 1/x, and returns e.
    10  //
    11  // If x == 0, Invert returns e = 0.
    12  func (e *P521Element) Invert(x *P521Element) *P521Element {
    13  	// Inversion is implemented as exponentiation with exponent p − 2.
    14  	// The sequence of 13 multiplications and 520 squarings is derived from the
    15  	// following addition chain generated with github.com/mmcloughlin/addchain v0.4.0.
    16  	//
    17  	//	_10       = 2*1
    18  	//	_11       = 1 + _10
    19  	//	_1100     = _11 << 2
    20  	//	_1111     = _11 + _1100
    21  	//	_11110000 = _1111 << 4
    22  	//	_11111111 = _1111 + _11110000
    23  	//	x16       = _11111111 << 8 + _11111111
    24  	//	x32       = x16 << 16 + x16
    25  	//	x64       = x32 << 32 + x32
    26  	//	x65       = 2*x64 + 1
    27  	//	x129      = x65 << 64 + x64
    28  	//	x130      = 2*x129 + 1
    29  	//	x259      = x130 << 129 + x129
    30  	//	x260      = 2*x259 + 1
    31  	//	x519      = x260 << 259 + x259
    32  	//	return      x519 << 2 + 1
    33  	//
    34  
    35  	var z = new(P521Element).Set(e)
    36  	var t0 = new(P521Element)
    37  
    38  	z.Square(x)
    39  	z.Mul(x, z)
    40  	t0.Square(z)
    41  	for s := 1; s < 2; s++ {
    42  		t0.Square(t0)
    43  	}
    44  	z.Mul(z, t0)
    45  	t0.Square(z)
    46  	for s := 1; s < 4; s++ {
    47  		t0.Square(t0)
    48  	}
    49  	z.Mul(z, t0)
    50  	t0.Square(z)
    51  	for s := 1; s < 8; s++ {
    52  		t0.Square(t0)
    53  	}
    54  	z.Mul(z, t0)
    55  	t0.Square(z)
    56  	for s := 1; s < 16; s++ {
    57  		t0.Square(t0)
    58  	}
    59  	z.Mul(z, t0)
    60  	t0.Square(z)
    61  	for s := 1; s < 32; s++ {
    62  		t0.Square(t0)
    63  	}
    64  	z.Mul(z, t0)
    65  	t0.Square(z)
    66  	t0.Mul(x, t0)
    67  	for s := 0; s < 64; s++ {
    68  		t0.Square(t0)
    69  	}
    70  	z.Mul(z, t0)
    71  	t0.Square(z)
    72  	t0.Mul(x, t0)
    73  	for s := 0; s < 129; s++ {
    74  		t0.Square(t0)
    75  	}
    76  	z.Mul(z, t0)
    77  	t0.Square(z)
    78  	t0.Mul(x, t0)
    79  	for s := 0; s < 259; s++ {
    80  		t0.Square(t0)
    81  	}
    82  	z.Mul(z, t0)
    83  	for s := 0; s < 2; s++ {
    84  		z.Square(z)
    85  	}
    86  	z.Mul(x, z)
    87  
    88  	return e.Set(z)
    89  }
    90
View as plain text