p521_invert.mx raw

   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 = (&P521Element{}).Set(e)
  36  	var t0 = &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