p384_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 *P384Element) Invert(x *P384Element) *P384Element {
  13  	// Inversion is implemented as exponentiation with exponent p − 2.
  14  	// The sequence of 15 multiplications and 383 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  	//	_110    = 2*_11
  20  	//	_111    = 1 + _110
  21  	//	_111000 = _111 << 3
  22  	//	_111111 = _111 + _111000
  23  	//	x12     = _111111 << 6 + _111111
  24  	//	x24     = x12 << 12 + x12
  25  	//	x30     = x24 << 6 + _111111
  26  	//	x31     = 2*x30 + 1
  27  	//	x32     = 2*x31 + 1
  28  	//	x63     = x32 << 31 + x31
  29  	//	x126    = x63 << 63 + x63
  30  	//	x252    = x126 << 126 + x126
  31  	//	x255    = x252 << 3 + _111
  32  	//	i397    = ((x255 << 33 + x32) << 94 + x30) << 2
  33  	//	return    1 + i397
  34  	//
  35  
  36  	var z = (&P384Element{}).Set(e)
  37  	var t0 = &P384Element{}
  38  	var t1 = &P384Element{}
  39  	var t2 = &P384Element{}
  40  	var t3 = &P384Element{}
  41  
  42  	z.Square(x)
  43  	z.Mul(x, z)
  44  	z.Square(z)
  45  	t1.Mul(x, z)
  46  	z.Square(t1)
  47  	for s := 1; s < 3; s++ {
  48  		z.Square(z)
  49  	}
  50  	z.Mul(t1, z)
  51  	t0.Square(z)
  52  	for s := 1; s < 6; s++ {
  53  		t0.Square(t0)
  54  	}
  55  	t0.Mul(z, t0)
  56  	t2.Square(t0)
  57  	for s := 1; s < 12; s++ {
  58  		t2.Square(t2)
  59  	}
  60  	t0.Mul(t0, t2)
  61  	for s := 0; s < 6; s++ {
  62  		t0.Square(t0)
  63  	}
  64  	z.Mul(z, t0)
  65  	t0.Square(z)
  66  	t2.Mul(x, t0)
  67  	t0.Square(t2)
  68  	t0.Mul(x, t0)
  69  	t3.Square(t0)
  70  	for s := 1; s < 31; s++ {
  71  		t3.Square(t3)
  72  	}
  73  	t2.Mul(t2, t3)
  74  	t3.Square(t2)
  75  	for s := 1; s < 63; s++ {
  76  		t3.Square(t3)
  77  	}
  78  	t2.Mul(t2, t3)
  79  	t3.Square(t2)
  80  	for s := 1; s < 126; s++ {
  81  		t3.Square(t3)
  82  	}
  83  	t2.Mul(t2, t3)
  84  	for s := 0; s < 3; s++ {
  85  		t2.Square(t2)
  86  	}
  87  	t1.Mul(t1, t2)
  88  	for s := 0; s < 33; s++ {
  89  		t1.Square(t1)
  90  	}
  91  	t0.Mul(t0, t1)
  92  	for s := 0; s < 94; s++ {
  93  		t0.Square(t0)
  94  	}
  95  	z.Mul(z, t0)
  96  	for s := 0; s < 2; s++ {
  97  		z.Square(z)
  98  	}
  99  	z.Mul(x, z)
 100  
 101  	return e.Set(z)
 102  }
 103