p = 2130706433, 7 次扩域 F_{p^7} = F_p[z]/(z^7 + 2z - 8),椭圆曲线方程 y^2 = x^3 + 3z * x - 3
计算 z^p
p = 2130706433
R.<z> = PolynomialRing(GF(p))
f = z^7 + 2*z - 8
Q.<x> = R.quotient(f)
x^p
判断多项式是否不可约
p = 2130706433
R.<z> = GF(p)[]
f = z^7 + 2*z - 8
f.is_irreducible()
输出:
True
p = 2130706433
R.<z> = GF(p)[]
f = z^7 - 2*z - 5
f.is_irreducible()
输出:
False
计算可约多项式的因子
p = 2130706433
R.<z> = GF(p)[]
f = z^7 - 2*z -5
f.roots()
输出:
[(1593200390, 1), (1236676234, 1)]
寻找一个不可约多项式
p = 2130706433
for a in range(10):
for b in range(10):
for c in range(6):
f = z^7 - b*z^c - a
if f.is_irreducible():
print(f"不可约多项式: {f}")
break
输出:
不可约多项式: z^7 + 2130706430*z^2 + 2130706432
不可约多项式: z^7 + 2130706429*z^3 + 2130706432
不可约多项式: z^7 + 2130706428*z^3 + 2130706432
不可约多项式: z^7 + 2130706427*z + 2130706432
不可约多项式: z^7 + 2130706426*z^4 + 2130706432
...
求元素的逆
p = 2130706433
Fp = GF(p)
R.<z> = PolynomialRing(Fp)
m = z^7 + 2*z - 8
if not m.is_irreducible():
raise ValueError("模多项式必须是不可约的")
K.<alpha> = GF(p^7, modulus=m)
a_coeffs = [3, 5, 17, 91, 37, 35, 33]
a = K(a_coeffs)
a_inv = a^-1
print("逆元系数(升幂排列 z^0 到 z^6):")
print(a_inv._vector_()) # 直接获取向量形式的系数
输出:
逆元系数(升幂排列 z^0 到 z^6):
(160999759, 1072290039, 1965672728, 284498232, 360286207, 995856082, 1407068673)
求元素的平方根
p = 2130706433
Fp = GF(p)
R.<z> = PolynomialRing(Fp)
m = z^7 + 2*z - 8
if not m.is_irreducible():
raise ValueError("模多项式必须是不可约的")
K.<alpha> = GF(p^7, modulus=m, impl='pari_ffelt')
a_coeffs = [Fp(c) for c in [66569, 54284, 51184, 12894, 12749, 7840, 7979]]
a = K(a_coeffs)
if a == 0:
print("平方根为 0")
else:
try:
if a.is_square():
sqrt_a = a.sqrt()
print("平方根系数(升幂排列 z^0 到 z^6):")
print(sqrt_a._vector_()) # 输出向量形式的系数
else:
print("该元素不是二次剩余,无平方根")
except AttributeError:
q = p^7
exponent = (q + 1) // 4
sqrt_a = a^exponent
print("尝试通过幂运算得到平方根:")
print(sqrt_a._vector_())
输出:
平方根系数(升幂排列 z^0 到 z^6):
(3, 6, 17, 91, 37, 35, 33)
计算椭圆曲线的阶和生成元
p = 2130706433
Fp = GF(p)
R.<z> = PolynomialRing(Fp)
m = z^7 + 2*z - 8
if m.is_irreducible():
K.<a> = GF(p^7, modulus=m)
A = 3 * a # 3z ∈ K
B = K(-3)
E = EllipticCurve(K, [A, B])
try:
order = E.order()
print(f"椭圆曲线的阶为: {order}")
except:
print("无法直接计算阶,尝试随机寻找生成元...")
order = None
if order:
if order.is_prime():
x = K.random_element()
while True:
rhs = x^3 + A * x + B
if rhs.is_square():
y = rhs.sqrt()
P = E(x, y)
print("生成元坐标:", P.xy())
break
x = K.random_element()
else:
found = False
attempts = 0
while not found and attempts < 100:
x = K.random_element()
rhs = x^3 + A * x + B
if rhs.is_square():
y = rhs.sqrt()
P = E(x, y)
if P.order() == order:
print("生成元坐标:", P.xy())
found = True
attempts += 1
if not found:
print("未找到生成元,请增加尝试次数。")
else:
found = False
while not found:
x = K.random_element()
rhs = x^3 + A * x + B
if rhs.is_square():
y = rhs.sqrt()
P = E(x, y)
print("候选点坐标:", P.xy())
# 假设候选点为生成元(需进一步验证)
found = True
else:
print("模多项式可约,无法构造域。")
输出:
椭圆曲线的阶为: 199372529839252601278447397890875723011140055175072723225727394951
生成元坐标: (1893878130*a^6 + 1132837244*a^5 + 1200083975*a^4 + 997350568*a^3 + 1282823043*a^2 + 927502736*a + 2028879995, 1266676682*a^6 + 1494991430*a^5 + 193878861*a^4 + 70257646*a^3 + 856104656*a^2 + 141370201*a + 1417312439)
没有评论