在这篇博客中，我们将探讨一种高效计算 BN254 椭圆曲线的 Frobenius 自同构的方法。BN254 曲线是一种适合配对的椭圆曲线，广泛应用于加密算法中 hackmd.io/@jpw。我们将利用 $(p−1)/2$ 是奇数的事实，高效地计算 Frobenius 自同构。
什么是 Frobenius 自同构？
Frobenius 自同构是一个端同构，它将定义在素域 $F_p$ 上的椭圆曲线上的点 $(x,y)$ 映射到 $(x^p,y^p)$。这是有限域上椭圆曲线的一个重要性质，并在加密中有多种应用 math.stackexchange.com。
使用平方指数法进行高效计算
为了高效计算 Frobenius 自同构，我们将使用平方指数法。这种方法通过利用 $(p−1)/2$ 是奇数的事实，使我们能够更高效地计算 $x^p$ 和 $y^p$。
我们将一步一步走过实现过程：
第一步：定义素数 $p$ 和曲线常数 $b$
我们首先定义素数 $p$ 和曲线常数 $b$，这是 BN254 椭圆曲线的参数。
p = 16798108731015832284940804142231733909889187121439069848933715426072753864723
b = 3
第二步：在 $F_p$ 上构造椭圆曲线 $E$
接下来，我们在有限域 $F_p$ 上构造椭圆曲线 $E$。
F_p = GF(p)
E = EllipticCurve(F_p, [0, b])
第三步：利用平方指数法定义 Frobenius 自同构
我们通过使用素域的性质和平方指数法来定义 Frobenius 自同构。exponentiation_by_squaring 函数高效地计算 $x^n % mod$ 的结果。
def exponentiation_by_squaring(x, n, mod):
result = 1
while n > 0:
if n % 2 == 1:
result = (result * x) % mod
x = (x * x) % mod
n //= 2
return result
def frobenius_on_curve_efficient(P):
x, y = P.xy()
x_frob = exponentiation_by_squaring(x, p, p)
y_frob = exponentiation_by_squaring(y, p, p)
return E.point([x_frob, y_frob])
第四步：对曲线上的一个点应用 Frobenius 自同构
最后，我们对椭圆曲线上的一个随机点 $P$ 应用 Frobenius 自同构。
P = E.random_point()
frob_P_efficient = frobenius_on_curve_efficient(P)
print(f"Point P: {P}")
print(f"Frobenius(P) (efficient): {frob_P_efficient}")
以下是高效计算 BN254 椭圆曲线上 Frobenius 自同构的完整代码 github.com/thogiti：
## BN254 曲线是定义在素域 $F_p$ 上的适合配对的曲线，$p$ 是一个 254 位的素数。
## 曲线方程是 $y^2=x^3+b$，其中 $b$ 是曲线常数。
## 定义素数 $p$ 和曲线常数 $b$
p = 16798108731015832284940804142231733909889187121439069848933715426072753864723
b = 3
## 在 $F_p$ 上构造椭圆曲线 $E$
F_p = GF(p)
E = EllipticCurve(F_p, [0, b])
## 使用素域的性质和平方指数法为椭圆曲线定义 Frobenius 自同构
def exponentiation_by_squaring(x, n, mod):
result = 1
while n > 0:
if n % 2 == 1:
result = (result * x) % mod
x = (x * x) % mod
n //= 2
return result
def frobenius_on_curve_efficient(P):
x, y = P.xy()
x_frob = exponentiation_by_squaring(x, p, p)
y_frob = exponentiation_by_squaring(y, p, p)
return E.point([x_frob, y_frob])
## 对曲线上的一个点应用 Frobenius 自同构
P = E.random_point()
frob_P_efficient = frobenius_on_curve_efficient(P)
print(f"Point P: {P}")
print(f"Frobenius(P) (efficient): {frob_P_efficient}")
以下是实现 BN254 椭圆曲线上 Frobenius 自同构高效计算的 GitHub 仓库链接，完整代码、解释和说明 github.com/thogiti。
