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)