element_exp.go

// Copyright 2020 ConsenSys Software Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Code generated by consensys/gnark-crypto DO NOT EDIT

package fr

// expBySqrtExp is equivalent to z.Exp(x, 41cf7391def65d630ef0ff69c7b761ffd5cefe7b4128000265228)
//
// uses github.com/mmcloughlin/addchain v0.4.0 to generate a shorter addition chain
func (z *Element) expBySqrtExp(x Element) *Element {
	// addition chain:
	//
	//	_10       = 2*1
	//	_100      = 2*_10
	//	_101      = 1 + _100
	//	_1010     = 2*_101
	//	_1111     = _101 + _1010
	//	_10011    = _100 + _1111
	//	_10100    = 1 + _10011
	//	_11101    = _1010 + _10011
	//	_101100   = _1111 + _11101
	//	_1001001  = _11101 + _101100
	//	_1001101  = _100 + _1001001
	//	_1001111  = _10 + _1001101
	//	_1010011  = _100 + _1001111
	//	_1011100  = _1111 + _1001101
	//	_10101011 = _1001111 + _1011100
	//	_10111110 = _10011 + _10101011
	//	_11001000 = _1010 + _10111110
	//	i18       = 2*_11001000
	//	i19       = _10101011 + i18
	//	i20       = _1001001 + i19
	//	i21       = i18 + i20
	//	i22       = _1001101 + i21
	//	i23       = _1010011 + i22
	//	i24       = _1001001 + i23
	//	i25       = i20 + i24
	//	i26       = _1111 + i25
	//	i27       = i19 + i26
	//	i28       = i22 + i27
	//	i29       = i24 + i28
	//	i30       = _10111110 + i29
	//	i31       = _101100 + i30
	//	i32       = i25 + i31
	//	i33       = i30 + i32
	//	i34       = i28 + i33
	//	i35       = _10100 + i34
	//	i36       = i21 + i35
	//	i37       = i32 + i36
	//	i38       = i27 + i37
	//	i39       = i31 + i38
	//	i40       = i23 + i39
	//	i41       = 2*i36
	//	i42       = i38 + i40
	//	i43       = _1011100 + i42
	//	i92       = ((i41 << 16 + i42) << 14 + i33) << 17
	//	i129      = ((i37 + i92) << 20 + i26 + i43) << 14
	//	i168      = ((i34 + i129) << 17 + i35) << 19 + i40
	//	i209      = ((i168 << 17 + i43) << 17 + i39) << 5
	//	i248      = ((_101 + i209) << 30 + i29) << 6 + _101
	//	return      i248 << 3
	//
	// Operations: 200 squares 51 multiplies

	// Allocate Temporaries.
	var (
		t0  = new(Element)
		t1  = new(Element)
		t2  = new(Element)
		t3  = new(Element)
		t4  = new(Element)
		t5  = new(Element)
		t6  = new(Element)
		t7  = new(Element)
		t8  = new(Element)
		t9  = new(Element)
		t10 = new(Element)
	)

	// var t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10 Element
	// Step 1: t3 = x^0x2
	t3.Square(&x)

	// Step 2: t2 = x^0x4
	t2.Square(t3)

	// Step 3: z = x^0x5
	z.Mul(&x, t2)

	// Step 4: t9 = x^0xa
	t9.Square(z)

	// Step 5: t6 = x^0xf
	t6.Mul(z, t9)

	// Step 6: t8 = x^0x13
	t8.Mul(t2, t6)

	// Step 7: t4 = x^0x14
	t4.Mul(&x, t8)

	// Step 8: t0 = x^0x1d
	t0.Mul(t9, t8)

	// Step 9: t1 = x^0x2c
	t1.Mul(t6, t0)

	// Step 10: t0 = x^0x49
	t0.Mul(t0, t1)

	// Step 11: t5 = x^0x4d
	t5.Mul(t2, t0)

	// Step 12: t7 = x^0x4f
	t7.Mul(t3, t5)

	// Step 13: t3 = x^0x53
	t3.Mul(t2, t7)

	// Step 14: t2 = x^0x5c
	t2.Mul(t6, t5)

	// Step 15: t7 = x^0xab
	t7.Mul(t7, t2)

	// Step 16: t8 = x^0xbe
	t8.Mul(t8, t7)

	// Step 17: t9 = x^0xc8
	t9.Mul(t9, t8)

	// Step 18: t10 = x^0x190
	t10.Square(t9)

	// Step 19: t9 = x^0x23b
	t9.Mul(t7, t10)

	// Step 20: t7 = x^0x284
	t7.Mul(t0, t9)

	// Step 21: t10 = x^0x414
	t10.Mul(t10, t7)

	// Step 22: t5 = x^0x461
	t5.Mul(t5, t10)

	// Step 23: t3 = x^0x4b4
	t3.Mul(t3, t5)

	// Step 24: t0 = x^0x4fd
	t0.Mul(t0, t3)

	// Step 25: t7 = x^0x781
	t7.Mul(t7, t0)

	// Step 26: t6 = x^0x790
	t6.Mul(t6, t7)

	// Step 27: t9 = x^0x9cb
	t9.Mul(t9, t6)

	// Step 28: t5 = x^0xe2c
	t5.Mul(t5, t9)

	// Step 29: t0 = x^0x1329
	t0.Mul(t0, t5)

	// Step 30: t8 = x^0x13e7
	t8.Mul(t8, t0)

	// Step 31: t1 = x^0x1413
	t1.Mul(t1, t8)

	// Step 32: t7 = x^0x1b94
	t7.Mul(t7, t1)

	// Step 33: t8 = x^0x2f7b
	t8.Mul(t8, t7)

	// Step 34: t5 = x^0x3da7
	t5.Mul(t5, t8)

	// Step 35: t4 = x^0x3dbb
	t4.Mul(t4, t5)

	// Step 36: t10 = x^0x41cf
	t10.Mul(t10, t4)

	// Step 37: t7 = x^0x5d63
	t7.Mul(t7, t10)

	// Step 38: t9 = x^0x672e
	t9.Mul(t9, t7)

	// Step 39: t1 = x^0x7b41
	t1.Mul(t1, t9)

	// Step 40: t3 = x^0x7ff5
	t3.Mul(t3, t1)

	// Step 41: t10 = x^0x839e
	t10.Square(t10)

	// Step 42: t9 = x^0xe723
	t9.Mul(t9, t3)

	// Step 43: t2 = x^0xe77f
	t2.Mul(t2, t9)

	// Step 59: t10 = x^0x839e0000
	for s := 0; s < 16; s++ {
		t10.Square(t10)
	}

	// Step 60: t9 = x^0x839ee723
	t9.Mul(t9, t10)

	// Step 74: t9 = x^0x20e7b9c8c000
	for s := 0; s < 14; s++ {
		t9.Square(t9)
	}

	// Step 75: t8 = x^0x20e7b9c8ef7b
	t8.Mul(t8, t9)

	// Step 92: t8 = x^0x41cf7391def60000
	for s := 0; s < 17; s++ {
		t8.Square(t8)
	}

	// Step 93: t7 = x^0x41cf7391def65d63
	t7.Mul(t7, t8)

	// Step 113: t7 = x^0x41cf7391def65d6300000
	for s := 0; s < 20; s++ {
		t7.Square(t7)
	}

	// Step 114: t6 = x^0x41cf7391def65d6300790
	t6.Mul(t6, t7)

	// Step 115: t6 = x^0x41cf7391def65d630ef0f
	t6.Mul(t2, t6)

	// Step 129: t6 = x^0x1073dce477bd9758c3bc3c000
	for s := 0; s < 14; s++ {
		t6.Square(t6)
	}

	// Step 130: t5 = x^0x1073dce477bd9758c3bc3fda7
	t5.Mul(t5, t6)

	// Step 147: t5 = x^0x20e7b9c8ef7b2eb187787fb4e0000
	for s := 0; s < 17; s++ {
		t5.Square(t5)
	}

	// Step 148: t4 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb
	t4.Mul(t4, t5)

	// Step 167: t4 = x^0x1073dce477bd9758c3bc3fda71edd80000
	for s := 0; s < 19; s++ {
		t4.Square(t4)
	}

	// Step 168: t3 = x^0x1073dce477bd9758c3bc3fda71edd87ff5
	t3.Mul(t3, t4)

	// Step 185: t3 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb0ffea0000
	for s := 0; s < 17; s++ {
		t3.Square(t3)
	}

	// Step 186: t2 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb0ffeae77f
	t2.Mul(t2, t3)

	// Step 203: t2 = x^0x41cf7391def65d630ef0ff69c7b761ffd5cefe0000
	for s := 0; s < 17; s++ {
		t2.Square(t2)
	}

	// Step 204: t1 = x^0x41cf7391def65d630ef0ff69c7b761ffd5cefe7b41
	t1.Mul(t1, t2)

	// Step 209: t1 = x^0x839ee723bdecbac61de1fed38f6ec3ffab9dfcf6820
	for s := 0; s < 5; s++ {
		t1.Square(t1)
	}

	// Step 210: t1 = x^0x839ee723bdecbac61de1fed38f6ec3ffab9dfcf6825
	t1.Mul(z, t1)

	// Step 240: t1 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb0ffeae77f3da0940000000
	for s := 0; s < 30; s++ {
		t1.Square(t1)
	}

	// Step 241: t0 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb0ffeae77f3da0940001329
	t0.Mul(t0, t1)

	// Step 247: t0 = x^0x839ee723bdecbac61de1fed38f6ec3ffab9dfcf682500004ca40
	for s := 0; s < 6; s++ {
		t0.Square(t0)
	}

	// Step 248: z = x^0x839ee723bdecbac61de1fed38f6ec3ffab9dfcf682500004ca45
	z.Mul(z, t0)

	// Step 251: z = x^0x41cf7391def65d630ef0ff69c7b761ffd5cefe7b4128000265228
	for s := 0; s < 3; s++ {
		z.Square(z)
	}

	return z
}

// expByLegendreExp is equivalent to z.Exp(x, 1073dce477bd9758c3bc3fda71edd87ff573bf9ed04a00009948a20000000000)
//
// uses github.com/mmcloughlin/addchain v0.4.0 to generate a shorter addition chain
func (z *Element) expByLegendreExp(x Element) *Element {
	// addition chain:
	//
	//	_10       = 2*1
	//	_100      = 2*_10
	//	_101      = 1 + _100
	//	_1010     = 2*_101
	//	_1111     = _101 + _1010
	//	_10011    = _100 + _1111
	//	_10100    = 1 + _10011
	//	_11101    = _1010 + _10011
	//	_101100   = _1111 + _11101
	//	_1001001  = _11101 + _101100
	//	_1001101  = _100 + _1001001
	//	_1001111  = _10 + _1001101
	//	_1010001  = _10 + _1001111
	//	_1010011  = _10 + _1010001
	//	_1011100  = _1111 + _1001101
	//	_10101011 = _1001111 + _1011100
	//	_10111110 = _10011 + _10101011
	//	_11001000 = _1010 + _10111110
	//	i19       = 2*_11001000
	//	i20       = _10101011 + i19
	//	i21       = _1001001 + i20
	//	i22       = i19 + i21
	//	i23       = _1001101 + i22
	//	i24       = _1010011 + i23
	//	i25       = _1001001 + i24
	//	i26       = i21 + i25
	//	i27       = _1111 + i26
	//	i28       = i20 + i27
	//	i29       = i23 + i28
	//	i30       = i25 + i29
	//	i31       = _10111110 + i30
	//	i32       = _101100 + i31
	//	i33       = i26 + i32
	//	i34       = i31 + i33
	//	i35       = i29 + i34
	//	i36       = _10100 + i35
	//	i37       = i22 + i36
	//	i38       = i33 + i37
	//	i39       = i28 + i38
	//	i40       = i32 + i39
	//	i41       = i24 + i40
	//	i42       = 2*i37
	//	i43       = i39 + i41
	//	i44       = _1011100 + i43
	//	i93       = ((i42 << 16 + i43) << 14 + i34) << 17
	//	i130      = ((i38 + i93) << 20 + i27 + i44) << 14
	//	i169      = ((i35 + i130) << 17 + i36) << 19 + i41
	//	i210      = ((i169 << 17 + i44) << 17 + i40) << 5
	//	i253      = ((_101 + i210) << 30 + i30) << 10 + _1010001
	//	return      i253 << 41
	//
	// Operations: 242 squares 52 multiplies

	// Allocate Temporaries.
	var (
		t0  = new(Element)
		t1  = new(Element)
		t2  = new(Element)
		t3  = new(Element)
		t4  = new(Element)
		t5  = new(Element)
		t6  = new(Element)
		t7  = new(Element)
		t8  = new(Element)
		t9  = new(Element)
		t10 = new(Element)
		t11 = new(Element)
	)

	// var t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11 Element
	// Step 1: t3 = x^0x2
	t3.Square(&x)

	// Step 2: z = x^0x4
	z.Square(t3)

	// Step 3: t1 = x^0x5
	t1.Mul(&x, z)

	// Step 4: t10 = x^0xa
	t10.Square(t1)

	// Step 5: t7 = x^0xf
	t7.Mul(t1, t10)

	// Step 6: t9 = x^0x13
	t9.Mul(z, t7)

	// Step 7: t5 = x^0x14
	t5.Mul(&x, t9)

	// Step 8: t0 = x^0x1d
	t0.Mul(t10, t9)

	// Step 9: t2 = x^0x2c
	t2.Mul(t7, t0)

	// Step 10: t0 = x^0x49
	t0.Mul(t0, t2)

	// Step 11: t6 = x^0x4d
	t6.Mul(z, t0)

	// Step 12: t8 = x^0x4f
	t8.Mul(t3, t6)

	// Step 13: z = x^0x51
	z.Mul(t3, t8)

	// Step 14: t4 = x^0x53
	t4.Mul(t3, z)

	// Step 15: t3 = x^0x5c
	t3.Mul(t7, t6)

	// Step 16: t8 = x^0xab
	t8.Mul(t8, t3)

	// Step 17: t9 = x^0xbe
	t9.Mul(t9, t8)

	// Step 18: t10 = x^0xc8
	t10.Mul(t10, t9)

	// Step 19: t11 = x^0x190
	t11.Square(t10)

	// Step 20: t10 = x^0x23b
	t10.Mul(t8, t11)

	// Step 21: t8 = x^0x284
	t8.Mul(t0, t10)

	// Step 22: t11 = x^0x414
	t11.Mul(t11, t8)

	// Step 23: t6 = x^0x461
	t6.Mul(t6, t11)

	// Step 24: t4 = x^0x4b4
	t4.Mul(t4, t6)

	// Step 25: t0 = x^0x4fd
	t0.Mul(t0, t4)

	// Step 26: t8 = x^0x781
	t8.Mul(t8, t0)

	// Step 27: t7 = x^0x790
	t7.Mul(t7, t8)

	// Step 28: t10 = x^0x9cb
	t10.Mul(t10, t7)

	// Step 29: t6 = x^0xe2c
	t6.Mul(t6, t10)

	// Step 30: t0 = x^0x1329
	t0.Mul(t0, t6)

	// Step 31: t9 = x^0x13e7
	t9.Mul(t9, t0)

	// Step 32: t2 = x^0x1413
	t2.Mul(t2, t9)

	// Step 33: t8 = x^0x1b94
	t8.Mul(t8, t2)

	// Step 34: t9 = x^0x2f7b
	t9.Mul(t9, t8)

	// Step 35: t6 = x^0x3da7
	t6.Mul(t6, t9)

	// Step 36: t5 = x^0x3dbb
	t5.Mul(t5, t6)

	// Step 37: t11 = x^0x41cf
	t11.Mul(t11, t5)

	// Step 38: t8 = x^0x5d63
	t8.Mul(t8, t11)

	// Step 39: t10 = x^0x672e
	t10.Mul(t10, t8)

	// Step 40: t2 = x^0x7b41
	t2.Mul(t2, t10)

	// Step 41: t4 = x^0x7ff5
	t4.Mul(t4, t2)

	// Step 42: t11 = x^0x839e
	t11.Square(t11)

	// Step 43: t10 = x^0xe723
	t10.Mul(t10, t4)

	// Step 44: t3 = x^0xe77f
	t3.Mul(t3, t10)

	// Step 60: t11 = x^0x839e0000
	for s := 0; s < 16; s++ {
		t11.Square(t11)
	}

	// Step 61: t10 = x^0x839ee723
	t10.Mul(t10, t11)

	// Step 75: t10 = x^0x20e7b9c8c000
	for s := 0; s < 14; s++ {
		t10.Square(t10)
	}

	// Step 76: t9 = x^0x20e7b9c8ef7b
	t9.Mul(t9, t10)

	// Step 93: t9 = x^0x41cf7391def60000
	for s := 0; s < 17; s++ {
		t9.Square(t9)
	}

	// Step 94: t8 = x^0x41cf7391def65d63
	t8.Mul(t8, t9)

	// Step 114: t8 = x^0x41cf7391def65d6300000
	for s := 0; s < 20; s++ {
		t8.Square(t8)
	}

	// Step 115: t7 = x^0x41cf7391def65d6300790
	t7.Mul(t7, t8)

	// Step 116: t7 = x^0x41cf7391def65d630ef0f
	t7.Mul(t3, t7)

	// Step 130: t7 = x^0x1073dce477bd9758c3bc3c000
	for s := 0; s < 14; s++ {
		t7.Square(t7)
	}

	// Step 131: t6 = x^0x1073dce477bd9758c3bc3fda7
	t6.Mul(t6, t7)

	// Step 148: t6 = x^0x20e7b9c8ef7b2eb187787fb4e0000
	for s := 0; s < 17; s++ {
		t6.Square(t6)
	}

	// Step 149: t5 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb
	t5.Mul(t5, t6)

	// Step 168: t5 = x^0x1073dce477bd9758c3bc3fda71edd80000
	for s := 0; s < 19; s++ {
		t5.Square(t5)
	}

	// Step 169: t4 = x^0x1073dce477bd9758c3bc3fda71edd87ff5
	t4.Mul(t4, t5)

	// Step 186: t4 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb0ffea0000
	for s := 0; s < 17; s++ {
		t4.Square(t4)
	}

	// Step 187: t3 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb0ffeae77f
	t3.Mul(t3, t4)

	// Step 204: t3 = x^0x41cf7391def65d630ef0ff69c7b761ffd5cefe0000
	for s := 0; s < 17; s++ {
		t3.Square(t3)
	}

	// Step 205: t2 = x^0x41cf7391def65d630ef0ff69c7b761ffd5cefe7b41
	t2.Mul(t2, t3)

	// Step 210: t2 = x^0x839ee723bdecbac61de1fed38f6ec3ffab9dfcf6820
	for s := 0; s < 5; s++ {
		t2.Square(t2)
	}

	// Step 211: t1 = x^0x839ee723bdecbac61de1fed38f6ec3ffab9dfcf6825
	t1.Mul(t1, t2)

	// Step 241: t1 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb0ffeae77f3da0940000000
	for s := 0; s < 30; s++ {
		t1.Square(t1)
	}

	// Step 242: t0 = x^0x20e7b9c8ef7b2eb187787fb4e3dbb0ffeae77f3da0940001329
	t0.Mul(t0, t1)

	// Step 252: t0 = x^0x839ee723bdecbac61de1fed38f6ec3ffab9dfcf682500004ca400
	for s := 0; s < 10; s++ {
		t0.Square(t0)
	}

	// Step 253: z = x^0x839ee723bdecbac61de1fed38f6ec3ffab9dfcf682500004ca451
	z.Mul(z, t0)

	// Step 294: z = x^0x1073dce477bd9758c3bc3fda71edd87ff573bf9ed04a00009948a20000000000
	for s := 0; s < 41; s++ {
		z.Square(z)
	}

	return z
}