cocks-pinch-derive-elements.py

D = -3572
k = 6
q = 447231129305840782240237212949663229744995012174421358105320171206333968505891497257173296273883152751267692209531558911549014331037613855148689298263886841953
# log2(q) 527.025659602
t = 678535529027017531887434617617827405828167042133406771522385895475121806814108
r_torsion = 21888242871839275222246405745257275088696311157297823662689037894645226208583
a4 = 42712243339421257868660507567123354675510133075791388004452184727050960820502924907704571467862154994392063936591279133153055638947148552957928421434686670171
a6 = 131738226030767995270565871104903809777878096841386516668655049559644995686736483226876210759529899795643641377453253635430103115971908064841330245626213375876
point_count = 447231129305840782240237212949663229744995012174421358105320171206333968505891496578637767246865620863833074591704153083381972197630842332762793823142080027846
h = point_count // r_torsion

Fq = GF(q)
E = EllipticCurve(Fq, [0, 0, 0, a4, a6])
g1_zero = E(0)
base_field = E.base_field()


# Deterministically find the generator point G1
# Using 'try and increment'
for g1_x in range(2, 2**10):
    g1_ysq = base_field(g1_x**3 + (g1_x*E.a4()) + E.a6())
    g1_y = int(g1_ysq.sqrt())
    assert g1_y**2 == g1_ysq
    try:
        G1 = E((g1_x, g1_y))
    except TypeError as ex:
        # Not a valid point on the curve
        continue
    assert G1*h != g1_zero
    assert G1*h*r_torsion == g1_zero
    G1 = G1*h
    break
print 'Found point of order r', G1
#print 'G1 order', G1.order()


# Deterministically find a non-residue to construct the twist field
gen = base_field.multiplicative_generator()
for x in range(1, 2**10):
    if x % 3 == 0:
        continue
    non_residue = gen ** x
    R.<y> = base_field[]
    twist_field.<u> = base_field.extension((y**3) - non_residue)
    if not u.is_square():
        twist = u
        break
print 'Found extension generator'

twisted_curve = EllipticCurve(twist_field, [E.a4() * (twist**2), E.a6() * (twist**3)])

g2_n = 89453239795993145562479008195938709094342983884681295745744409354709755941248761195895503785466992665703591280546935034259756292551172570057664587637552748874245745916198534608714950583043173593027267019743133567194163391851901819572673822279218068873028846955517790990625727796450265037970914757559687481887840909090899848282224484452135708895660966979071782739033640801091111561632461280508140767774552050467753596369433992300921959439025109579374506188537882560690578559118

assert g2_n % r_torsion == 0
g2_h = g2_n // r_torsion

G2_zero = twisted_curve(0)
g2_x = twist_one = twist**2 + twist + 1
while True:
    try:
        G2 = g2_h * twisted_curve.lift_x(g2_x)
        if G2 == G2_zero or G2*r_torsion != G2_zero:
            g2_x += twist_one
            continue
    except ValueError:
        g2_x += twist_one
        continue
    break
# Ensure G2 is of the same order as G1
assert G2 * r_torsion == G2_zero
assert G2 * (r_torsion+1) == G2

K.<a> = GF(q^(k//2), modulus=y^(k//2)-non_residue)
EK = E.base_extend(K)
b2, b4, b6, b8 = EK.b_invariants()
# new params = EllipticCurve(K, [0, b2*D, 0, 8*b4*D**2, 16*b6*D**3])
# need to make:
# 	8*b4*D**2 == E.a4() * (twist**2)
#	16*b6*D**3 == E.a6() * (twist**3)
EKQ = EK.quadratic_twist(a)

EK = E.base_extend(K).quadratic_twist(a)
assert (EK.random_element() * g2_h * r_torsion) == EK(0)


G2_zero = EK(0)
g2_x = twist_one = a**2 + a + 1
while True:
    try:
        G2 = g2_h * EK.lift_x(g2_x)
        if G2 == EK(0) or G2*r_torsion != EK(0):
            g2_x += twist_one
            continue
    except ValueError:
        g2_x += twist_one
        continue
    break
assert G2 * r_torsion = EK(0)

s = Integer(randrange(1, r_torsion))
derp1 = (s*G1).ate_pairing(G2, r_torsion, k, t)

# E.base_extend(K).quadratic_twist(a) == E.base_extend(twist_field).quadratic_twist(134169338791752234672071163884898968923498503652326407431596051361900190551767449177151988882164945825380307662859467673464704299311284156544606789479166052586*u^3

"""
sage: p = 2213; A = 1; B = 49; n = 1093; k = 7; t = 28
sage: F = GF(p); E = EllipticCurve(F, [A, B])
sage: R.<x> = F[]; K.<a> = GF(p^k, modulus=x^k+2)
sage: EK = E.base_extend(K)
sage: P = EK(1583, 1734)
sage: Qx = 1729*a^6+1767*a^5+245*a^4+980*a^3+1592*a^2+1883*a+722
sage: Qy = 1299*a^6+1877*a^5+1030*a^4+1513*a^3+1457*a^2+309*a+1636
sage: Q = EK(Qx, Qy)
sage: P.ate_pairing(Q, n, k, t)
1665*a^6 + 1538*a^5 + 1979*a^4 + 239*a^3 + 2134*a^2 + 2151*a + 654
sage: s = Integer(randrange(1, n))
sage: (s*P).ate_pairing(Q, n, k, t) == P.ate_pairing(s*Q, n, k, t)
True
sage: P.ate_pairing(s*Q, n, k, t) == P.ate_pairing(Q, n, k, t)^s
True
"""