# This file was *autogenerated* from the file endomorphism.sage
from sage.all_cmdline import * # import sage library
_sage_const_21888242871839275222246405745257275088696311157297823662689037894645226208583 = Integer(21888242871839275222246405745257275088696311157297823662689037894645226208583); _sage_const_21888242871839275222246405745257275088548364400416034343698204186575808495617 = Integer(21888242871839275222246405745257275088548364400416034343698204186575808495617); _sage_const_2 = Integer(2); _sage_const_1 = Integer(1); _sage_const_0 = Integer(0); _sage_const_3 = Integer(3); _sage_const_11 = Integer(11)# Defining prime field Fp for scalar field and Fq for base field
p = _sage_const_21888242871839275222246405745257275088696311157297823662689037894645226208583
Fp = GF(p)
q = _sage_const_21888242871839275222246405745257275088548364400416034343698204186575808495617
Fq = GF(q)
# Defining a polynomial ring over Fq
# and finding the roots of the polynomial X^2+X+1:
R = PolynomialRing(Fq, names=('x',)); (x,) = R._first_ngens(1)
f = x**_sage_const_2 + x + _sage_const_1
f_roots = f.roots()
lambdas = [root[_sage_const_0 ] for root in f_roots]
print('Roots of x^2 + x + 1 are', lambdas)
# Output: [21888242871839275217838484774961031246154997185409878258781734729429964517155, 4407920970296243842393367215006156084916469457145843978461]
# Picking one lambda out of roots
lambd = lambdas[_sage_const_1 ] # 4407920970296243842393367215006156084916469457145843978461
print('Picked lambda =', hex(lambd))
# Verifying that lambd is the root of the polynomial...
assert lambd**_sage_const_2 + lambd + _sage_const_1 == _sage_const_0 , 'lambd is incorrect since it is not a root of X^2+X+1'
# Finding beta parameter
# Beta should satisfy beta*3 = 1 in Fp, thus
# it is one of the roots of the polynomial Y^3 - 1
Q = PolynomialRing(Fp, names=('y',)); (y,) = Q._first_ngens(1)
g = y**_sage_const_3 - _sage_const_1
g_roots = g.roots()
betas = [root[_sage_const_0 ] for root in g_roots]
print('Roots of y^3 - 1 are', betas)
# Output: [21888242871839275220042445260109153167277707414472061641714758635765020556616, 2203960485148121921418603742825762020974279258880205651966, 1]
# Picking one beta out of roots
beta = betas[_sage_const_1 ] # 2203960485148121921418603742825762020974279258880205651966
print('Picked beta =', hex(beta))
# Verifying that beta is the root of the polynomial Y^3-1...
assert beta**_sage_const_3 == _sage_const_1 , 'beta is incorrect since beta^3 != 1'
# Then, we need to verify that (beta, lambda) pair is valid.
# For that, define the BN254 curve.
# Parameters can be found in section 5.4.9 of the paper
# https://zips.z.cash/protocol/protocol.pdf
a = Fp(_sage_const_0 )
b = Fp(_sage_const_3 )
E = EllipticCurve(Fp, (a, b))
G = E(_sage_const_1 , _sage_const_2 ) # Base point
E.set_order(q)
# Taking some random point on the curve
Q = _sage_const_11 * G
# Applying endomorphism to the point
R = lambd * Q
# If lambda1 and beta are valid, then R should be equal (beta*x, y)
x_1 = beta * Q[_sage_const_0 ]
y_1 = Q[_sage_const_1 ]
assert x_1 == R[_sage_const_0 ], 'beta is invalid since (beta*x, y) != lambda*(x, y)'
assert y_1 == R[_sage_const_1 ], 'beta is invalid since (beta*x, y) != lambda*(x, y)'