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 goldilocks

// expBySqrtExp is equivalent to z.Exp(x, 7fffffff)
//
// 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
	//	_11      = 1 + _10
	//	_110     = 2*_11
	//	_111     = 1 + _110
	//	_111000  = _111 << 3
	//	_111111  = _111 + _111000
	//	_1111110 = 2*_111111
	//	_1111111 = 1 + _1111110
	//	x12      = _1111110 << 5 + _111111
	//	x24      = x12 << 12 + x12
	//	return     x24 << 7 + _1111111
	//
	// Operations: 30 squares 7 multiplies

	// Allocate Temporaries.
	var (
		t0 = new(Element)
		t1 = new(Element)
	)

	// var t0,t1 Element
	// Step 1: z = x^0x2
	z.Square(&x)

	// Step 2: z = x^0x3
	z.Mul(&x, z)

	// Step 3: z = x^0x6
	z.Square(z)

	// Step 4: z = x^0x7
	z.Mul(&x, z)

	// Step 7: t0 = x^0x38
	t0.Square(z)
	for s := 1; s < 3; s++ {
		t0.Square(t0)
	}

	// Step 8: t0 = x^0x3f
	t0.Mul(z, t0)

	// Step 9: t1 = x^0x7e
	t1.Square(t0)

	// Step 10: z = x^0x7f
	z.Mul(&x, t1)

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

	// Step 16: t0 = x^0xfff
	t0.Mul(t0, t1)

	// Step 28: t1 = x^0xfff000
	t1.Square(t0)
	for s := 1; s < 12; s++ {
		t1.Square(t1)
	}

	// Step 29: t0 = x^0xffffff
	t0.Mul(t0, t1)

	// Step 36: t0 = x^0x7fffff80
	for s := 0; s < 7; s++ {
		t0.Square(t0)
	}

	// Step 37: z = x^0x7fffffff
	z.Mul(z, t0)

	return z
}

// expByLegendreExp is equivalent to z.Exp(x, 7fffffff80000000)
//
// 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
	//	_11       = 1 + _10
	//	_1100     = _11 << 2
	//	_1111     = _11 + _1100
	//	_11110000 = _1111 << 4
	//	_11111111 = _1111 + _11110000
	//	x16       = _11111111 << 8 + _11111111
	//	x32       = x16 << 16 + x16
	//	return      x32 << 31
	//
	// Operations: 62 squares 5 multiplies

	// Allocate Temporaries.
	var (
		t0 = new(Element)
	)

	// var t0 Element
	// Step 1: z = x^0x2
	z.Square(&x)

	// Step 2: z = x^0x3
	z.Mul(&x, z)

	// Step 4: t0 = x^0xc
	t0.Square(z)
	for s := 1; s < 2; s++ {
		t0.Square(t0)
	}

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

	// Step 9: t0 = x^0xf0
	t0.Square(z)
	for s := 1; s < 4; s++ {
		t0.Square(t0)
	}

	// Step 10: z = x^0xff
	z.Mul(z, t0)

	// Step 18: t0 = x^0xff00
	t0.Square(z)
	for s := 1; s < 8; s++ {
		t0.Square(t0)
	}

	// Step 19: z = x^0xffff
	z.Mul(z, t0)

	// Step 35: t0 = x^0xffff0000
	t0.Square(z)
	for s := 1; s < 16; s++ {
		t0.Square(t0)
	}

	// Step 36: z = x^0xffffffff
	z.Mul(z, t0)

	// Step 67: z = x^0x7fffffff80000000
	for s := 0; s < 31; s++ {
		z.Square(z)
	}

	return z
}