EXPLICITLY COMPUTING MATRICES OF FROBENIUS FOR E[3]

Simon Spicer

MATH581B/D Project

University of Washington, Fall 2010

This Sage worksheet is intended to be read in conjunction with the text of the project.

Source code:

{{{id=1| %hide # Computes the action of Frobenius for elements of an elliptic curve over a finite field def frobenius(P): """ If P = (x,y) is defined over field of characteristic P, returns the point (x^p, y^p). EXAMPLES:: sage: F = EllipticCurve(GF(3001^3,'a'), [-5,9]); F Elliptic Curve defined by y^2 = x^3 + 2996*x + 9 over Finite Field in a of size 3001^3 sage: P = F.an_element(); P (1637*a^2 + 1297*a + 1392 : 1394*a^2 + 2454*a + 1142 : 1) sage: frobenius(P) (1187*a^2 + 1221*a + 792 : 2582*a^2 + 611*a + 2726 : 1) """ if P.is_zero(): return P E = P.curve() x, y = P.xy() return E(x.frobenius(),y.frobenius()) # Double discrete log def ddl(R, r, basis): """ For R in E[r] with basis (P, Q), returns (a,b), where R = a*P + b*Q. EXAMPLES:: sage: F = EllipticCurve(GF(10009^2,'a'), [3,7]); F Elliptic Curve defined by y^2 = x^3 + 3*x + 7 over Finite Field in a of size 10009^2 sage: F(0).division_points(3) [(0 : 1 : 0), (1760 : 4880*a + 249 : 1), (1760 : 5129*a + 9760 : 1), (448 : 2911*a + 4187 : 1), (448 : 7098*a + 5822 : 1), (8614 : 342*a + 9325 : 1), (8614 : 9667*a + 684 : 1), (9196 : 4314*a + 1381 : 1), (9196 : 5695*a + 8628 : 1)] sage: P = F(0).division_points(3)[1] sage: Q = F(0).division_points(3)[3] sage: ddl(P + 2*Q, 3, (P,Q)) (1,2) sage: ddl(2*P, 3, (P,Q)) (2,0) """ P, Q = basis[0], basis[1] a, b = 0, 0 while R != 0: R = R - P a += 1 if a == r: R = R - Q a = 0 b += 1 if b == r: raise ValueError("Basis not basis.") return (a, b) # Compute Frobenius matrix with given two-element basis def frob_matrix(r, basis): """ If basis = (P,Q) for E[r], returns the matrix [[a,c],[b,d]], where frobenius(P) = a*P + b*Q, and frobenius(Q) = c*P + d*Q EXAMPLES:: sage: F = EllipticCurve(GF(10009^2,'a'), [3,7]); F Elliptic Curve defined by y^2 = x^3 + 3*x + 7 over Finite Field in a of size 10009^2 sage: P = F(0).division_points(3)[1] sage: Q = F(0).division_points(3)[3] sage: frob_matrix(3, (P,Q)) [2 0] [0 2] """ row1 = ddl(frobenius(basis[0]), r, basis) row2 = ddl(frobenius(basis[1]), r, basis) return matrix(Integers(r),[row1, row2]).transpose() # Compute the matrix of Frobenius def matrix_of_Frobenius(E, p, x_root_choices, zeta_choice, gbar_choice): """ Returns the matrix representing the action of Frobenius w.r.t p on E[3], given the choices specified by x_root_choices, zeta_choice and gbar_choice. INPUT: - ``E`` - The elliptic curve for which the Frobenius matrix is being computed - ``p`` - A prime of good reduction for E whose Frobenius element we are considering - ``x_root_choices`` - A tuple (a1, a2) of a pair of integers between 0 and 3 representing our choice of the two x-values of the r-division polynomial which constitute the x-values of our basis - ``zeta_choice`` - An integer either 0 or 1, representing which of the two primitive third roots of unity we are choosing - ``gbar_choice`` - An integer between 0 and some divisor of 24 representing our choice of irreducible divisor of the defining polynomial of QQ(xE[r]) reduced modulo p OUTPUT: - An invertible 2x2 matrix over the finite field GF(3). The returned matrix will always have the same trace in GF(3), regardless of the values specified in x_root_choices, zeta_choice and gbar_choice. EXAMPLES:: sage: E = EllipticCurve([-5,9]); E Elliptic Curve defined by y^2 = x^3 - 5*x + 9 over Rational Field sage: p = 3001 sage: x_root_choices = (0,1) sage: zeta_choice = 0 sage: gbar_choice = 0 sage: matrix_of_Frobenius(E, p, x_root_choices, zeta_choice, gbar_choice) [1 2] [1 0] sage: zeta_choice = 1; gbar_choice = 4 sage: matrix_of_Frobenius(E, p, x_root_choices, zeta_choice, gbar_choice) [2 0] [1 2] sage: x_root_choices = (3,1) sage: matrix_of_Frobenius(E, p, x_root_choices, zeta_choice, gbar_choice) [2 0] [2 2] sage: zeta_choice = 2 sage: matrix_of_Frobenius(E, r, x_root_choices, zeta_choice, gbar_choice) Traceback (most recent call last) ... IndexError: list index out of range sage: zeta_choice = 1; x_root_choices = (2,4) sage: matrix_of_Frobenius(E, r, x_root_choices, zeta_choice, gbar_choice) Traceback (most recent call last) ... IndexError: list index out of range sage: x_root_choices = (3,1); gbar_choice = 13 sage: matrix_of_Frobenius(E, r, x_root_choices, zeta_choice, gbar_choice) Traceback (most recent call last) ... IndexError: list index out of range """ # Compute the 3-division polynomial for E and make it monic, so that we can construct # a Number field with it h = E.division_polynomial(3) h = sage.schemes.elliptic_curves.heegner.make_monic(h)[0] # Construct K, the number field containing all the roots of h factor_list = [] for j in h.factor(): factor_list.append(j[0]) variables = ['a1','a2','a3','a4'] variables = variables[:len(factor_list)] K = NumberFieldTower(factor_list,variables) K. = K.galois_closure() # Compute the x-values of our basis corresponding to the values in x_root_choices root_list = K[x](E.division_polynomial(3)).roots() xP = root_list[x_root_choices[0]][0] xQ = root_list[x_root_choices[1]][0] # Compute the primitive 3rd root of unity correspoding to the value specified # in zeta_choice z = K[x](x^2 + x + 1) zeta = z.roots()[zeta_choice][0] # Compute the irreducible factor of f reduced modulo p, corresponding to the # value specified in gbar_choice f = K.defining_polynomial() fbar = GF(p)[x](f) gbar = fbar.factor()[gbar_choice][0] # Construct the finite field k = GF(p)[x]/(gbar), and reduce xP, xQ and zeta into # this field k. = GF(p^(gbar.degree()),modulus=gbar) xPbar = k(xP.polynomial()) xQbar = k(xQ.polynomial()) zetabar = k(zeta.polynomial()) # Construct E over k F = E.change_ring(k) # Look for points in F corresponding to xPbar and xQbar. If none exist in E(k), # construct a quadratic extension k' of k for which corresponding points in # E(k') do exist. Pick two respective points arbitrarily. try: Pbar = F.lift_x(xPbar) Qbar = F.lift_x(xQbar) except ValueError: # No points exist. The following is a hack to construct a quadratic extension # of k such that the finite field is of the right type R = GF(p)[x] hbar = R(x^2) lbar = gbar(hbar) # It's possible that gbar(x^2) isn't reducible over GF(p). # If it's not, gbar(x^2 + tx) will be for some t in GF(p). while not lbar.is_irreducible(): hbar = hbar + R(x) lbar = gbar(hbar) k. = GF(p^(lbar.degree()),modulus=lbar) # Coerce xPbar, xQbar and zetabar into the new k and try lift again xPbar = k(xPbar.polynomial()(hbar)) xQbar = k(xQbar.polynomial()(hbar)) zetabar = k(zetabar.polynomial()(hbar)) F = E.change_ring(k) Pbar = F.lift_x(xPbar) Qbar = F.lift_x(xQbar) # The Weil Pairing: if != zetabar, we have chosen the wrong Qbar; # So instead set Qbar to -Qbar if -(Pbar._miller_(Qbar,3)/Qbar._miller_(Pbar,3)) != zetabar: Qbar = -Qbar # Finally, return the matrix of Frobenius acting on the basis (Pbar, Qbar) return frob_matrix(3, (Pbar, Qbar)) # A second function that computes the matrix of Frobenius for each different reduction to the finite case def matrix_of_Frobenius2(E, p, x_root_choices, zeta_choice): """ Returns the matrix representing the action of Frobenius w.r.t p on E[3], given the choices specified by x_root_choices, zeta_choice and gbar_choice. INPUT: - ``E`` - The elliptic curve for which the Frobenius matrix is being computed - ``p`` - A prime of good reduction for E whose Frobenius element we are considering - ``x_root_choices`` - A tuple (a1, a2) of a pair of integers between 0 and 3 representing our choice of the two x-values of the r-division polynomial which constitute the x-values of our basis - ``zeta_choice`` - An integer either 0 or 1, representing which of the two primitive third roots of unity we are choosing OUTPUT: - A list of pairs, with first entry an invertible 2x2 matrix over the finite field GF(3), and second entry a irreducible factor of the defining polynomial of Q(xE[3]) reduced mod p used to compute this matrix. The returned matrix will always have the same trace in GF(3), regardless of the values specified in x_root_choices and zeta_choice. EXAMPLES:: sage: E = EllipticCurve([-5,9]); E Elliptic Curve defined by y^2 = x^3 - 5*x + 9 over Rational Field sage: p = 3001 sage: x_root_choices = (0,1) sage: zeta_choice = 0 sage: S = matrix_of_Frobenius2(E, p, x_root_choices, zeta_choice) sage: for s in S: print(s[0].trace(), s[1]) ....: (1, x^3 + 560*x^2 + 2061*x + 1738) (1, x^3 + 560*x^2 + 2061*x + 1820) (1, x^3 + 1053*x^2 + 306*x + 1299) (1, x^3 + 1053*x^2 + 306*x + 2948) (1, x^3 + 1814*x^2 + 1972*x + 1539) (1, x^3 + 1814*x^2 + 1972*x + 2133) (1, x^3 + 2575*x^2 + 840*x + 184) (1, x^3 + 2575*x^2 + 840*x + 2509) """ # Compute the 3-division polynomial for E and make it monic, so that we can construct # a Number field with it h = E.division_polynomial(3) h = sage.schemes.elliptic_curves.heegner.make_monic(h)[0] # Construct K, the number field containing all the roots of h factor_list = [] for j in h.factor(): factor_list.append(j[0]) variables = ['a1','a2','a3','a4'] variables = variables[:len(factor_list)] K = NumberFieldTower(factor_list,variables) K. = K.galois_closure() # Compute the x-values of our basis corresponding to the values in x_root_choices root_list = K[x](E.division_polynomial(3)).roots() xP = root_list[x_root_choices[0]][0] xQ = root_list[x_root_choices[1]][0] # Compute the primitive 3rd root of unity correspoding to the value specified # in zeta_choice z = K[x](x^2 + x + 1) zeta = z.roots()[zeta_choice][0] # Compute the irreducible factors of f reduced modulo p, corresponding to the # primes lying over p in K f = K.defining_polynomial() fbar = GF(p)[x](f) gbar_list = fbar.factor() # Iterate through the factors of fbar S = [] for gbar in gbar_list: # Construct the finite field k = GF(p)[x]/(gbar), and reduce xP, xQ and zeta into # this field gbar = gbar[0] k. = GF(p^(gbar.degree()),modulus=gbar) xPbar = k(xP.polynomial()) xQbar = k(xQ.polynomial()) zetabar = k(zeta.polynomial()) # Construct E over k F = E.change_ring(k) # Look for points in F corresponding to xPbar and xQbar. If none exist in E(k), # construct a quadratic extension k' of k for which corresponding points in # E(k') do exist. Pick two respective points arbitrarily. try: Pbar = F.lift_x(xPbar) Qbar = F.lift_x(xQbar) except ValueError: # No points exist. The following is a hack to construct a quadratic extension # of k such that the finite field is of the right type R = GF(p)[x] hbar = R(x^2) lbar = gbar(hbar) # It's possible that gbar(x^2) isn't reducible over GF(p). # If it's not, gbar(x^2 + tx) will be for some t in GF(p). while not lbar.is_irreducible(): hbar = hbar + R(x) lbar = gbar(hbar) k. = GF(p^(lbar.degree()),modulus=lbar) # Coerce xPbar, xQbar and zetabar into the new k and try lift again xPbar = k(xPbar.polynomial()(hbar)) xQbar = k(xQbar.polynomial()(hbar)) zetabar = k(zetabar.polynomial()(hbar)) F = E.change_ring(k) Pbar = F.lift_x(xPbar) Qbar = F.lift_x(xQbar) # The Weil Pairing: if != zetabar, we have chosen the wrong Qbar; # So instead set Qbar to -Qbar # This is another hack. E.weil_pairing(Q,3) sometimes hangs, and has a lot of unnecessary overhead. # The following bypasses all of that by just executing the algorithmic part of E.weil_pairing(Q,3) if -(Pbar._miller_(Qbar,3)/Qbar._miller_(Pbar,3)) != zetabar: Qbar = -Qbar # Append the pair of gbar and its associated Frobenius matrix to the list S S.append((frob_matrix(3, (Pbar, Qbar)), gbar)) # ...and return S return S /// }}}

Fixed objects for this worksheet:

{{{id=34| E = EllipticCurve([-6,7]) p = 3001 print(E) /// Elliptic Curve defined by y^2 = x^3 - 6*x + 7 over Rational Field }}}

If there's any justice in this world, we should have that $a_p$ is equivalent to the trace of our Frobenius matrix modulo $3$. We compute $mod(E.ap(p),3)$ here for checking against later.

{{{id=59| print(E.ap(p), mod(E.ap(p),3)) /// (6, 0) }}}

A better idea:

Let's try our algorithm now.

{{{id=20| h = E.division_polynomial(3) h = sage.schemes.elliptic_curves.heegner.make_monic(h)[0] K. = NumberField(h) f = E.defining_polynomial().subs(x = a, z = 1) f = f.univariate_polynomial() f = K[x](f) K = K.extension(f,'b') L = K.galois_closure('c') L /// Number Field in c with defining polynomial x^48 + 1680*x^46 + 1267788*x^44 + 568914080*x^42 + 169510802490*x^40 + 35502267039120*x^38 + 5407082139505164*x^36 + 612697415789612160*x^34 + 52584900570783085815*x^32 + 3474524201476510464800*x^30 + 179916723139991600440920*x^28 + 7491761615925474075948480*x^26 + 262048470358705173301880908*x^24 + 8132812403711010614505678240*x^22 + 232449573425550239949812739000*x^20 + 6144205835975390314540081706880*x^18 + 143965018375909870934343740064255*x^16 + 2775605278171293998429348367723600*x^14 + 45340769224863212300531330067855324*x^12 + 667243498285618617003487369665559200*x^10 + 7822578094172787659757932246735010330*x^8 + 74530056891464787281398620231452544720*x^6 + 656572152505911721437224199805173441468*x^4 + 3137530358083789988185072461284002855680*x^2 + 16983464863842839359715414077072437459561 }}}

If there's any justice in this world, we should have that ap is equivalent to the trace of our Frobenius matrix modulo 3. We compute mod(E.ap(p),3) here for checking against later.

Holy hand grenades, Batman! That's a degree 48 extension over $\QQ$. There's no way we can do anything useful in that field.

{{{id=38| timeit('L[x](E.division_polynomial(3)).factor()') /// 5 loops, best of 3: 2.08 s per loop }}}

Compute $K$, the number field over $\QQ$ obtained by adjoining all the roots of the $n$-division polynomial to $\QQ$. This is typically a degree 24 extension over $\QQ$.

{{{id=41| show(L[x](E.division_polynomial(3)).factor()) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(3\right) \cdot (x - \frac{2593529952635800103746663324185571809467433909207011555300791002742963346408382020454330016145493773505930037}{1178087725104796028534909068227415794419686340129844891108463425703699902761261176515409191993158328115889824795309102719629052853131246015873024000} c^{46} - \frac{956357364847098357890007079860140171383870615439855359556576954681998241044812593090180262990558396764126610259}{261797272245510228563313126272759065426596964473298864690769650156377756169169150336757598220701850692419961065624245048806456189584721336860672000} c^{44} - \frac{5125223656332324735321780745123461523683908105879114300730882986469704948264133878646085373030835905744632798021}{1887961097924352609831585045236243260287958878413212966519973438627724203143046757236232679476215269416490103838636382563508097521043663486976000} c^{42} - \frac{216563447795255587136038255386310828216134746769089322667199674769731695451771314527472778766416499661039220812272653}{181244265400737850543832164342679352987644052327668444785917450108261523501732488694678337229716665863983049968509092726096777362020191694749696000} c^{40} - \frac{27280087788128327363023460330486271523229427313630765910012807034426620273033385500315552844670033956472442018844242659}{78539181673653068568993937881827719627979089341989659407230895046913326850750745101027279466210555207725988319687273514641936856875416401058201600} c^{38} - \frac{22145971696309892490588520520585773126195194513404340432943694805386908944327199480612533073316248756057362077994871889}{314282439670480466462560775837645936886671025778269945607166446766359851343540396562734211549462005633157216165215180130619995425671934377984000} c^{36} - \frac{155475589210866127738324476609728676264096436832692838834614497139311848973140758495094723426489374123708024893266194421623}{15103688783394820878652680361889946082303671027305703732159787509021793625144374057889861435809722155331920830709091060508064780168349307895808000} c^{34} - \frac{1307821847086896353201995473554505915743634723899395699225963632131301078689834374432780410229833921021895416471046634976247}{1184603041834887912051190616618819300572836943318094410365473530119356362756421494736459720455664482771131045545811063569259982758301906501632000} c^{32} - \frac{5765032091870927790400975465531839335697958302570210921459504013715686516723374262744597401956559033758993134609432637354554301}{65449318061377557140828281568189766356649241118324716172692412539094439042292287584189399555175462673104990266406061262201614047396180334215168000} c^{30} - \frac{248894522233603468559462600406981107452570403972358684313857991881542565344923618261080246841899067679432717805487372822507108151}{47123509004191841141396362729096631776787453605193795644338537028147996110450447060616367679726333124635592991812364108785162114125249840634920960} c^{28} - \frac{145759385806438215765472476835846078901018488777584362863784787854932916457394079656269119536813232330483054849137205044761870581}{606012204272014417970632236742497836635641121465969594191596412399022583724928588742494440325698728454675835800056122798163093031446114205696000} c^{26} - \frac{3339862830055986331947348337467784492629756333835577935175073367456148807141636729349443299035370112267420858210553752117728092743927}{392695908368265342844969689409138598139895446709948297036154475234566634253753725505136397331052776038629941598436367573209684284377082005291008000} c^{24} - \frac{146214639452300099041156542738906965245902365929972325669335598335483154463920132667487927964813561673648486936105100352045042976826481}{589043862552398014267454534113707897209843170064922445554231712851849951380630588257704595996579164057944912397654551359814526426565623007936512000} c^{22} - \frac{30386874187976084893081124770796319700151481601173694617004228216175089162805941875225046989981173164842170553618745815411588123764383}{4619951863156062856999643404813395272234064078940568200425346767465489814750043829472192909777091482807411077628663147920113932757377435356364800} c^{20} - \frac{6238844123851984628027792865396411503658327795981168504899058695111525697549934302063525651253948047733463199195125545392870178696553}{37744704764346918766336955921678065949624706527292223859684205616548119401552645665622491092950093813786038215920450554902891607494913687552000} c^{18} - \frac{564474617918192747410924304435513798689416378690522445242242492312263127803171816169156771216231918917948441294930677678704340723031313}{150978819057387675065347823686712263798498826109168895438736822466192477606210582662489964371800375255144152863681802219611566429979654750208000} c^{16} - \frac{13877097486418642777504899087623088592300850629022973492649684286586389324032795454730333823845678656953621576389883804416685905142501}{227720692394249886976391890930184409952486917208399540631578917746896647973168299641764652144495286961001738859248570466985771387601289216000} c^{14} - \frac{633263091289635218618382132606374269266420828566332934055438962699688574690301095618397525416555190798241977799801587334016092396059}{2976741077049018130410351515427247188921397610567314256621946637214335267623115027996923557444382836091525998160112032248180018138578944000} c^{12} + \frac{3384518391368053482967242106508434825764002358927494182493819619776042323237540456479085540744480864412168321437872710484327024133201}{345514589300332461565487229469234048714090794083706119072190234676663914991968708606785770060508722046337839072155860885949466391085056000} c^{10} + \frac{169060111425292895268322234540981065289312689274191426218842279173427028350443438654245364581757268509277793995844105334655241831773049}{758777137287004621477148425501063008940748410536766379138927574191889381943146967920784436211313271944898783844734439592673337956892672000} c^{8} + \frac{16339781217126401748628137289412110922596470553309844576492151737864603888711694099247169765513230918769572500710361691535201430262597}{2479663847343152357768458906866218983466498073649563330519371157489834581513552182747661556246121803741499293610243266642723326656512000} c^{6} + \frac{5905311082194653953104530389915907093328088271032574145218923784126121619953257839795540558243975761480850423774650574336897537213897}{61226267835633391549838491527560962554728347497520082235046201419502088432433387228337322376447451944234550459512179423277119176704000} c^{4} + \frac{574054895783038458763346488113738865642589719385374558923613413439016245258749569787620299274751174892371642510662125708014933624853}{900386291700491052203507228346484743451887463198824738750679432639736594594608635710842976124227234474037506757532050342310576128000} c^{2} + \frac{52469510799871631798126277263675663524517939842984471591324047169264048401962964117044642967116267743548358441492076242909025955163}{6156487464618742237288938313480237562064187782556066589748235436852899792099888107424567358114374252813931670136971284391867187200}) \cdot (x - \frac{1302995450579073304649062178315950055357970193096444816157968006984956309688370471628060815316509}{1548169831807679034689795532924515730468044644714685193047187985906650889264232900196704156056928324469605547031713806712671759467806720} c^{46} - \frac{145215976375934483235648208253513809327149153387844360385445653371336096431484403199610117217461651}{103211322120511935645986368861634382031202976314312346203145865727110059284282193346446943737128554964640369802114253780844783964520448} c^{44} - \frac{61620109660607728561431973661763364138373428813722881418797948581640100769459831016898957533515949371}{58377444638298606134607674695494559972399873480945897173725037175967228101969566372424741932765019776380299661829329061563791835136000} c^{42} - \frac{1400441910420006512344730676979671582507541146148643794666569767479282536698140903573400703602689659351001}{2977249676553228912864991409470222558592393547528240755859976895974328633200447884993661838571016008595395282753295782139753383591936000} c^{40} - \frac{1793255523317014621623774530416032503294185439789133446783535606037415597725884000459299018707068320005391609}{12901415265063991955748296107704297753900372039289043275393233215888757410535274168305867967141069370580046225264281722605597995565056000} c^{38} - \frac{123974546729009539217363315139558972740154121730304543583430271048366320086961000091590398171623046113127886563}{4300471755021330651916098702568099251300124013096347758464411071962919136845091389435289322380356456860015408421427240868532665188352000} c^{36} - \frac{615415119414683688830269640669936626196158303346111611353284827877711259311873776306024958069672776068817574203}{141773794121582329184047209974772502790113978453725750279046518855920411104783232618745801836715048028352156321585513435226351599616000} c^{34} - \frac{7648451379256317147543639731317859978983930236103957342712618794886305791544302760919370339267764135322503180027}{15752643791286925464894134441641389198901553161525083364338502095102267900531470290971755759635005336483572924620612603914039066624000} c^{32} - \frac{88335789346358747147867697247152257440676890378111325808214484080446231861490251307332629341438184723338109515681393}{2150235877510665325958049351284049625650062006548173879232205535981459568422545694717644661190178228430007704210713620434266332594176000} c^{30} - \frac{51752292702016322857215188433700668854932655841106398622333017389434016012723471247521308668146677506981499553074290137}{19352122897595987933622444161556446630850558058933564913089849823833136115802911252458801950711604055870069337896422583908396993347584000} c^{28} - \frac{176010746763009913778202153099568963228849504302385285897451164439341459542891160917283632178685648370799982686814968687}{1290141526506399195574829610770429775390037203928904327539323321588875741053527416830586796714106937058004622526428172260559799556505600} c^{26} - \frac{425096907925221646976456774850616180944459526094888121151288701370160032296746657705034619940266036850976580270145073671}{75890678029788187974989977104142927964119835525229666325842548328757396532560436284152164512594525709294389560378127780032929385676800} c^{24} - \frac{3743539405892515779013670158510330212235706203230594788533721814764476201784626214271040189113360841967476000579056156500203}{19352122897595987933622444161556446630850558058933564913089849823833136115802911252458801950711604055870069337896422583908396993347584000} c^{22} - \frac{38203511878898608727442911388363677189626491136170514385636724474893859062483034720923403480629252386612684080002191225893641}{6450707632531995977874148053852148876950186019644521637696616607944378705267637084152933983570534685290023112632140861302798997782528000} c^{20} - \frac{56144992534484093000601000889458385419592189139867123240693806687291914183240911890123316788279099500354626053397365740581}{337291902354614168777733231573968568729421491223242961448189103683366206811379716818454064500420114263530620268347234577924130603008} c^{18} - \frac{2144004848852018834012591576083633584160116983875801836589801053636171655743040509672525667165364463397099821319435380248149}{496017503462667895261372399373483189307972781210651413894395740710832657075558407085961859559441344505192088629922403791064897945600} c^{16} - \frac{12567920165717024261308966043920664194771539902720845914185684731654033006538860284006785535985034402569276524605265014822237}{127183975246837921861890358813713638284095584925808054844716856592521194121938053098964579374215729360305663751262154818221768704000} c^{14} - \frac{29831597741604964772578831005464419417829082898777043873633820375702367899289269643855618524106113546262708329718877710279}{16299368864134040992168442754544872265038521712906325111459292143088708717408439459049670559299721819852065071288242319392768000} c^{12} - \frac{18104978359005058763716737578251765017651320567060249029333296879488118921941362782255703818288017560333784198139007176524681}{635675385701227598694569267427250018336502346803346679346912393580459639978929138902937151812689150974230537780241450456317952000} c^{10} - \frac{77061691368303062989968924178651548988590350901095961907014393562084861978649081224108759868946908916034607653664619271655947}{211891795233742532898189755809083339445500782267782226448970797860153213326309712967645717270896383658076845926747150152105984000} c^{8} - \frac{4811520292871718585003188484974923456627529715958003291770138619900245879087092183084267064763803356913237505690491486971797}{1384913694338186489530651998752178689186279622665243310123992142876818387753658254690494884123505775542985921089850654588928000} c^{6} - \frac{93228282787452063002597714676255981549003693173217592795523876995180837660858112853592025163859791858800597481381333444143}{3017241164135482547997063178109321762933071073344756666936802054197861411228013626776677307458618247370339697363509051392000} c^{4} - \frac{146148688969228408747713061754323955458692283941492681482417220699808729590304477218820653479958111982372377576578078678549}{1005747054711827515999021059369773920977690357781585555645600684732620470409337875592225769152872749123446565787836350464000} c^{2} - \frac{665174840451205324161214101424264042824505258728654218339533734302555892859009620267862566008021456830241382341591326361}{505654627808862501759186052976256370526742261328097313044545341745912755359144231066981281625375942244065643935563776000}) \cdot (x + \frac{5193239252131223475377741963082763947753784381418450866996321251303930361901830264707908612971885757}{7174917320041811337381914366769166467776727294589187430437771018658930315223614345357997094129335567706527340054819572588206615655612416000} c^{46} + \frac{2789095860495452056885482164436056536487805328009161280855957525833993579530768507526439949451428176703}{2391639106680603779127304788923055489258909098196395810145923672886310105074538115119332364709778522568842446684939857529402205218537472000} c^{44} + \frac{1994956379049868114094312264244592398566776396738646609217927799554463118412569516724895405427567320602023}{2391639106680603779127304788923055489258909098196395810145923672886310105074538115119332364709778522568842446684939857529402205218537472000} c^{42} + \frac{2503658630947521516399068480498472163234293981619328532806132821864452110467032098521746134038699301763152749}{7174917320041811337381914366769166467776727294589187430437771018658930315223614345357997094129335567706527340054819572588206615655612416000} c^{40} + \frac{45245735134027052898862798504363467237219863525060316055719916107279647541129769361228422650989668301436216013}{478327821336120755825460957784611097851781819639279162029184734577262021014907623023866472941955704513768489336987971505880441043707494400} c^{38} + \frac{116302773464375940838319190276078857974320617148172374096200476170288609099888062488802622766313597711739812189}{6699269206388245879908416775694833303246243972538923837943763789597507297127557745432303542604421631845497049537646659746224664477696000} c^{36} + \frac{744031641122643509990012725604266344838436196917956732359634814411715313501701979029447210926710845997197751690039}{341662729525800539875329255560436498465558442599485115735131953269472872153505445017047480672825503224120349526419979647057457888362496000} c^{34} + \frac{2830097919767439093460857229076938059707563007640339100931174880327351303434121448585186665609408156140550857406769}{15631628148239240386452972476621277707574569269257488955202115509060850359964301406008708266076983807639493115587842206074524217114624000} c^{32} + \frac{3434929379100648074925410651777963689684150567248532843052404661538583423592869129946776383165240483356665315805676601}{398606517780100629854550798153842581543151516366065968357653945481051684179089685853222060784963087094807074447489976254900367536422912000} c^{30} + \frac{73918785827981429825962001488144153833825881520331620662991655692989232392834962901628355649635682919496683625999506017}{3587458660020905668690957183384583233888363647294593715218885509329465157611807172678998547064667783853263670027409786294103307827806208000} c^{28} - \frac{38011985763095716405769096701266409327257791172266775032505696362845949222007474494387691567228780848890948711506658775101}{1195819553340301889563652394461527744629454549098197905072961836443155052537269057559666182354889261284421223342469928764701102609268736000} c^{26} - \frac{3329001176910015153422827904307504505900882490099707465192751677401339525505808731210784898523239973838861686700328691456597}{1195819553340301889563652394461527744629454549098197905072961836443155052537269057559666182354889261284421223342469928764701102609268736000} c^{24} - \frac{512960494092211419430856767927638895983863441728010708931405877721241139156407808594134523339419844436567125126859748341023229}{3587458660020905668690957183384583233888363647294593715218885509329465157611807172678998547064667783853263670027409786294103307827806208000} c^{22} - \frac{381429756723616699870009475201073664075620377698697518670249310064746572136339597812738147292308985824076893730221932661810687}{70342326667076581739038376144795749684085561711658700298409519790773826619839356327039187197346427134377719020145289927335358977015808000} c^{20} - \frac{1362638037239978086469038482790457398440498952560742559749367820305237730764709685279157052441691132626121172153232038326289063}{7815814074119620193226486238310638853787284634628744477601057754530425179982150703004354133038491903819746557793921103037262108557312000} c^{18} - \frac{2375800714229775660006917351443382410323527580734793422314588336149049745142289533189105300963598711960951745060329724105958863}{459753769065860011366263896371214050222781449095808498682415162031201481175420629588491419590499523754102738693760064884544829915136000} c^{16} - \frac{2621090957254640241872668735956997266980066989034738903683343676740522729567163687291754771411257564397922302763373633527094607}{18029559571210196524167211622400550989128684278266999948330006354164763967663554101509467434921549951141283870343531956256659996672000} c^{14} - \frac{7320351259340720229673397218117691205169816448335581778874027161153162543866887474699105256635176182182008074705001348508631767}{2003284396801132947129690180266727887680964919807444438703334039351640440851506011278829714991283327904587096704836884028517777408000} c^{12} - \frac{100741277210042466884397198659769884428567793011455276122201610299334431962604418504189379205836052728531247537737745922324671}{1454818007843960019702026274703506091271579462460017747787461175999738882245102404705032472760554341252423454397121920136904704000} c^{10} - \frac{3603628617592884746037432594463348728625138393592647743389015178280076870788862342299270181170124029642304502380937300175759}{3423101194926964752240061822831779038286069323435335877146967472940562075870829187541252877083657273535114010346169223851540480} c^{8} - \frac{149711088138722869606446082751561896530015637653774859475244234958393215197136142202862360103067533477499755998217438576177337}{9508614430352679867333505063421608439683525898431488547630465202612672432974525520947924658565714648708650028739358955143168000} c^{6} - \frac{92005502843521799801421431233165021447349003260296813287322597076820802457981407132950072385925952769355394125573182828582681}{559330260608981168666676768436565202334325052848911091037086188388980731351442677702819097562689096982861766396432879714304000} c^{4} - \frac{37875782441650211064694720480646021817710522864306490847721578449009627383897096001681329334051924225499925472617512315045113}{32901780035822421686275104025680306019666179579347711237475658140528278314790745747224652797805240998991868611554875277312000} c^{2} - \frac{243405338535062057488679343641219572339506831584180020788096845440722733932370477438707404946627928405304499206041633006584129}{32901780035822421686275104025680306019666179579347711237475658140528278314790745747224652797805240998991868611554875277312000}) \cdot (x + \frac{31975711906745287246554721638213423172972097184633563086264564632298125418488820447767279737}{13786760808042944248946793909709754494306674064116810251007482008535388280433121740063664655432818874877366244925624478274158592000} c^{46} + \frac{7669056728947200300933934089678516492733107406314322335030444273294571901382581869172037864863}{1969537258291849178420970558529964927758096294873830035858211715505055468633303105723380665061831267839623749275089211182022656000} c^{44} + \frac{4497694706180053645245301529323191194993397944606854419052308566839565282781056768098463386759849}{1531862312004771583216310434412194943811852673790756694556386889837265364492569082229296072825868763875262916102847164252684288000} c^{42} + \frac{3629518386532762599124215129882827766355935848398648870195507457730448694732693273055199105478702933}{2757352161608588849789358781941950898861334812823362050201496401707077656086624348012732931086563774975473248985124895654831718400} c^{40} + \frac{5400949787296472251895559446794805863616074903496833864732774911483061754744475624649804302924710839303}{13786760808042944248946793909709754494306674064116810251007482008535388280433121740063664655432818874877366244925624478274158592000} c^{38} + \frac{13945529877320801373193622427498812536327708396246536171180311218727578592100999280431405928426264778567}{170206923556085731468478937156910549312428074865639632728487432204140596054729898025477341425096529319473657344760796028076032000} c^{36} + \frac{11449470553483949323282705432808217183685774710483960410303419218968445075631593458462970428654956128574889}{919117387202862949929786260647316966287111604274454016733832133902359218695541449337577643695521258325157749661708298551610572800} c^{34} + \frac{6472893169113122837001183124177295271175960713446425993478052108843380371548124301560437136429258559193953557}{4595586936014314749648931303236584831435558021372270083669160669511796093477707246687888218477606291625788748308541492758052864000} c^{32} + \frac{30777278017527606745166335305312946744764616929852065678455367677253993129777606453213367587874870347287845271}{255310385334128597202718405735365823968642112298459449092731148306210894082094847038216012137644793979210486017141194042114048000} c^{30} + \frac{54701644034274913931748788826458294539449700735167852669219010289740386610999840182487760034620642612076390255149}{6893380404021472124473396954854877247153337032058405125503741004267694140216560870031832327716409437438683122462812239137079296000} c^{28} + \frac{2817580039395206043985772711020943386034138323508236769318455865186379689745653824484205570837090891797905034746037}{6893380404021472124473396954854877247153337032058405125503741004267694140216560870031832327716409437438683122462812239137079296000} c^{26} + \frac{12936778772246885549094857842326389596083511916703523509072163483573978373053200851186345755146678365195802091553029}{765931156002385791608155217206097471905926336895378347278193444918632682246284541114648036412934381937631458051423582126342144000} c^{24} + \frac{4030243698097494591462754713382717312242970255475572131496912362192846138413105412644376743288337353502789634190580103}{6893380404021472124473396954854877247153337032058405125503741004267694140216560870031832327716409437438683122462812239137079296000} c^{22} + \frac{123544321106515674740741542836811889491701186231371419198102372873996339494916327648369241361321500852295746633404035991}{6893380404021472124473396954854877247153337032058405125503741004267694140216560870031832327716409437438683122462812239137079296000} c^{20} + \frac{844514124970672106789095295265189328551479210440747794162333778272683545926324498531816140048462313693382496119181533}{1668695328981232661455675854479515189337530145741565026749876786315103882889508804171346484559769895288957424948635255177216000} c^{18} + \frac{11686638624025429599371743281625414469890333013996464695249061514375686261954424008144671416505691339610378376314437213}{883426938872417291358887217077390394355163018333769720044052416284466761529739955149536374178701709270624519090453958623232000} c^{16} + \frac{107825223965518053700355028432292969902760681312543753122738962667076610934880625363358907721706744438955118596574941211}{353370775548966916543554886830956157742065207333507888017620966513786704611895982059814549671480683708249807636181583449292800} c^{14} + \frac{65790963958602646470971163404787806604267008666118649923986663419634499341281370105323675712113190037472165829666459519}{11548064560423755442599832902972423455623045991291107451556240735744663549408365426791325152662767441446072144973254361088000} c^{12} + \frac{2212311012565225224830322547770991176701171826380354872516025841883495005995117500485200857280009087831463129980062517}{25159182048853497696295932250484582691989206952703937802954772844759615576053083718499619068982064142584035174233669632000} c^{10} + \frac{270273648741224534027939149909457591310521542862051600453111350444551113987198909818664361512928050506045421578599103733}{226432638439681479266663390254361244227902862574335440226592955602836540184477753466496571620838577283256316568103026688000} c^{8} + \frac{18691064988467453395565597271221509538334649841172697968503148990936237096432621549664616232489486053001939925595535467}{1479951885226676335076231308852034275999365114864937517820868990868212680944299042264683474646003773093178539660804096000} c^{6} + \frac{12760496342814679117456341470964756874865958113226517027826184454709205879999356634039569088384896122740915769801049}{128971841849819288459802292710416930370315042689754903513801219247774525572487933966421217834074402883937127639285760} c^{4} + \frac{101170079917985641135616752153841084325696420521126213365117005707027915630142496978013218570636563277068080259301021}{153537906964070581499764634179067774250375050821136789897382403866398244729152302340977640278660003433258485284864000} c^{2} + \frac{1340109333853851873901814144767925489497778145866715399154724349975475414128940273775377707496184308462995865769083}{7024610122539176931361780648715519083350492521228480583540371418724102700026575924097016221899477281260192137216000})
}}}

The potential bottleneck of the algorithm: factor the division polynomial over $K$ and choose two roots $xP$ and $xQ$; then factor the $n$th cyclotomic polynomial over $K$ and choose a primitive $n$th root of unity $\zeta$. These are typically hideous.

{{{id=35| x_root_choices = (0,1) zeta_choice = 0 gbar_choice = 0 /// }}} {{{id=64| matrix_of_Frobenius(E, p, x_root_choices, zeta_choice, gbar_choice) /// [1 1] [1 2] }}}

Muuuch better. How long does this take?

{{{id=5| timeit('T = matrix_of_Frobenius(E, p, x_root_choices, zeta_choice, gbar_choice)') /// 5 loops, best of 3: 499 ms per loop }}}

Let's test our second algorithm:

{{{id=15| S = matrix_of_Frobenius2(E, p, x_root_choices, zeta_choice) for s in S: show(s) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 1 & 1 \\ 1 & 2 \end{array}\right), x^{2} + 321 x + 352\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 2 & 2 \\ 2 & 1 \end{array}\right), x^{2} + 321 x + 1938\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 0 & 2 \\ 1 & 0 \end{array}\right), x^{2} + 658 x + 1355\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 0 & 1 \\ 2 & 0 \end{array}\right), x^{2} + 658 x + 1526\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 2 & 1 \\ 1 & 1 \end{array}\right), x^{2} + 1332 x + 483\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 1 & 2 \\ 2 & 2 \end{array}\right), x^{2} + 1332 x + 1898\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 1 & 2 \\ 2 & 2 \end{array}\right), x^{2} + 1669 x + 682\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 2 & 1 \\ 1 & 1 \end{array}\right), x^{2} + 1669 x + 2097\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 0 & 1 \\ 2 & 0 \end{array}\right), x^{2} + 2343 x + 1995\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 0 & 2 \\ 1 & 0 \end{array}\right), x^{2} + 2343 x + 2166\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 1 & 1 \\ 1 & 2 \end{array}\right), x^{2} + 2680 x + 1109\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rr} 2 & 2 \\ 2 & 1 \end{array}\right), x^{2} + 2680 x + 2524\right)
}}}

The Nuts & Bolts:

Compute the division polynomial for the $x$-coordinates of $E[n]$, and obtain the monic integral polynomial which will produce the same number field:

{{{id=43| h = E.division_polynomial(3) h = sage.schemes.elliptic_curves.heegner.make_monic(h)[0] h /// x^4 - 12*x^2 + 28*x - 12 }}}

The Weil Pairing. If $\langle \overline{P},\overline{Q} \rangle = \overline{\zeta}$, we are done. Otherwise set $\overline{Q} = -\overline{Q}$.

This is another hack. E.weil_pairing(Q,3) sometimes hangs, and has a lot of unnecessary overhead.
        # The following bypasses all of that by just executing the algorithmic part of E.weil_pairing(Q,3)

This is another hack. E.weil_pairing(Q,3) sometimes hangs, and has a lot of unnecessary overhead. The following bypasses all of that by just executing the algorithmic part of E.weil_pairing(Q,3)

{{{id=45| factor_list = [] for j in h.factor(): factor_list.append(j[0]) variables = ['a1','a2','a3','a4'] variables = variables[:len(factor_list)] K = NumberFieldTower(factor_list,variables) K. = K.galois_closure() print(K) /// Number Field in a with defining polynomial x^24 - 1800*x^22 + 5880*x^21 + 1360296*x^20 - 8820000*x^19 - 532225200*x^18 + 5342450400*x^17 + 103387239792*x^16 - 1594770464000*x^15 - 5080036377600*x^14 + 218449184889600*x^13 - 1295032905675264*x^12 - 5563908661248000*x^11 + 143989834128883200*x^10 - 1105355481581460480*x^9 + 3950642240579319552*x^8 + 13361519046661632000*x^7 - 275234336433051084800*x^6 + 1033462006065432115200*x^5 + 3981994742086927865856*x^4 - 50708716073968167936000*x^3 + 339307941768238298419200*x^2 - 758663077099896131788800*x + 2532393920611852253761536 }}}

The hard part: factor the division polynomial over $K$ and choose two roots $xP$ and $xQ$; then factor the $n$th cyclotomic polynomial over $K$ and choose a primitive $n$th root of unity $\zeta$:

{{{id=69| root_list = K[x](E.division_polynomial(3)).roots() xP = root_list[x_root_choices[0]][0] xQ = root_list[x_root_choices[1]][0] z = K[x](x^2 + x + 1) zeta = z.roots()[zeta_choice][0] show(xP) show(xQ) show(zeta) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\frac{36150522279043447101924827101323764463239554642027814033080364523623863358374154860691674088999821}{4009178214965790395782403489522555613201674220430459828078929910271061289170379781847426736930850239008655706110992737280} a^{23} - \frac{17339214673858027509097773416982348232988492111232473959710629925192409411229719268887302386747381}{19810057062183905485042464301170274794643566736244625032860594850751126370018347157363755641305377651572181136077846466560} a^{22} - \frac{98910082654185429564600266948452061720938073290593953687389936763410271674037770381489981662888188377}{6013767322448685593673605234283833419802511330645689742118394865406591933755569672771140105396275358512983559166489105920} a^{21} + \frac{1008393046630996655001035325317555923230035544669585533356190787612395939507625305018634449470817389291}{18709498336507021846984549617771926194941146362008812531035006247931619349461772315287991439010634448707059961851299440640} a^{20} + \frac{76089915807158588512548894775321922358532171466347470672432044850663895129758141873160593413893121082343}{6013767322448685593673605234283833419802511330645689742118394865406591933755569672771140105396275358512983559166489105920} a^{19} - \frac{399686406059772131603295413532751885126987104740780035163975858831993076311271067994458851953231727782923}{4952514265545976371260616075292568698660891684061156258215148712687781592504586789340938910326344412893045284019461616640} a^{18} - \frac{17866893519364157931586575012098774812720405538033955788372007238127787621523658232838927129971785116294703}{3508030938095066596309603053332236161551464942876652349569063671487178628024082309116498394814493959132573742847118645120} a^{17} + \frac{596016830011564194664192308346203560408370137157477656172143031365220890939748656454740471787809987370974681}{12027534644897371187347210468567666839605022661291379484236789730813183867511139345542280210792550717025967118332978211840} a^{16} + \frac{86412186860008301783286851889810955384731181272619121745560572899936364569192946211793494588189085877254469}{82219475111603123351006321562474285036362459598671539443024929800480749094314429119917931128464702167169697097979343245} a^{15} - \frac{7633226379666467916878790832306504872077347558998761113859599599615637214648935217060487191011794737190635321}{501147276870723799472800436190319451650209277553807478509866238783882661146297472730928342116356279876081963263874092160} a^{14} - \frac{46877234279009093422628197764990689845280090323605226392981872922962932527881606515499945615381234841656284321}{657755800892824986808050572499794280290899676789372315544199438403845992754515432959343449027717617337357576783834745960} a^{13} + \frac{1473856731635459224338990974147509978092209324178485471378957655329686297275525372363393198884374524284051012689}{657755800892824986808050572499794280290899676789372315544199438403845992754515432959343449027717617337357576783834745960} a^{12} - \frac{106739410944425675585255316044280777470886961896552525444997212769621814653089308032156945062001378932863879581}{11243688904150854475351291837603321030613669688707219069131614331689675089820776631783648701328506279271069688612559760} a^{11} - \frac{241932331879811007275502253755910906847178545560506728317332284436004355463249373164093174600827928770153237602033}{2631023203571299947232202289999177121163598707157489262176797753615383971018061731837373796110870469349430307135338983840} a^{10} + \frac{463875058924039906918850982435624337511117340187912155328316187572527367893827186279413087657204887285652837659163}{328877900446412493404025286249897140145449838394686157772099719201922996377257716479671724513858808668678788391917372980} a^{9} - \frac{7016859290783684945735525057375179689692441000602759896844686473454127172951017767975299583793927685063589097114783}{877007734523766649077400763333059040387866235719163087392265917871794657006020577279124598703623489783143435711779661280} a^{8} + \frac{3513991676900207297594872128031168424450167379309363115589188487087318054444670091114580616675515577491543460824141}{328877900446412493404025286249897140145449838394686157772099719201922996377257716479671724513858808668678788391917372980} a^{7} + \frac{328996961395051261433596582125986220751496059640850670979791791287412249970131521032846257595017426958221932171666843}{1315511601785649973616101144999588560581799353578744631088398876807691985509030865918686898055435234674715153567669491920} a^{6} - \frac{6774936075130972096064373005503083570777879946086362437564149989432398539204337701218630120753133257492333447698243}{2610142067035019788920835605157913810678173320592747283905553326999388860136966003806918448522688957687926891999344230} a^{5} + \frac{10271602752462784741614134711448479561923052375959834684734851392614068147305502043655995597599428045158284767126313}{2409361908032325959003848250914997363702929219008689800528203071076358947818737849667924721713251345558086361845548520} a^{4} + \frac{86043776064581492557397022229926501670876232820092127257281765566132805469710650871500739606540971473922378462191017}{1074764380543831677790932308006199804396894896714660646314051369940924824762280119214613478803460159047969896705612330} a^{3} - \frac{1871489596712030393065253819501854455656823409708380713824756420910134023014911442974069283118672494011687769213040431}{4060220993165586338321299830245643705499380720922051330519749619776827115768613783699650919924182823070108498665646580} a^{2} + \frac{1868644077604162451938669087265231038022417231688591303367046937430158404060324050685871575629299447613195026162241102}{1015055248291396584580324957561410926374845180230512832629937404944206778942153445924912729981045705767527124666411645} a - \frac{213785557893019390106518976225275420678285675646081873281803764484362583971675893579699281361747004638795884724999843}{79612176336580124280809800593051837362732955312197084912151953328957394426835564386267665096552604373923696052267580}
\newcommand{\Bold}[1]{\mathbf{#1}}\frac{6487256720234460744398408868540697175935790828343216345489572242337047009265810387}{4314601851663691104229035244961287244645872764911791055384718612096945134852746265336327824512509206130688} a^{23} + \frac{67481780072896491591818856707024107184944425244183445704640663257948813022133696231689}{5436398333096250791328584408651221928253799683788856729784745451242150869914460294323773058885761599724666880} a^{22} - \frac{260576535038981623569455274666201352440953482175303300662512916714828321458380503591441}{97078541662433049845153293011628963004532137210515298746156168772181265534186790970067376051531457137940480} a^{21} - \frac{12069782967740927423912365445169599316061420921174910984632857861825289663703460073581677}{906066388849375131888097401441870321375633280631476121630790908540358478319076715720628843147626933287444480} a^{20} + \frac{1617062045003396367685213314277720693962826697540661759608947017560369670838560530509938971}{776628333299464398761226344093031704036257097684122389969249350177450124273494327760539008412251657103523840} a^{19} + \frac{4727056365317920948488314330347877225133642410175286434084470163813798511559426518737109783}{1359099583274062697832146102162805482063449920947214182446186362810537717478615073580943264721440399931166720} a^{18} - \frac{160362977410485279472061364164223896271572524759706799786918532760629871437343841982475751041}{181213277769875026377619480288374064275126656126295224326158181708071695663815343144125768629525386657488896} a^{17} + \frac{1097881871191980686324113052991905091123610857160171846286375144693394701053199806380915131003}{776628333299464398761226344093031704036257097684122389969249350177450124273494327760539008412251657103523840} a^{16} + \frac{14481458461610708127992642718126303412219960236256486242734889534918919884313194158446168513445}{67954979163703134891607305108140274103172496047360709122309318140526885873930753679047163236072019996558336} a^{15} - \frac{5730119863656523952136581755600990612490376221458838537605525704650237364054174176852599243717}{5393252314579613880286294056201609055807340956139738819230898265121181418565932831670409780640636507663360} a^{14} - \frac{8859374815727559344098076375606987550004432675855710149147409355069761464602438032751893787217891}{339774895818515674458036525540701370515862480236803545611546590702634429369653768395235816180360099982791680} a^{13} + \frac{82801496410841685124790507414141278631013025396066710300815915391019944741484352012353620689188463}{339774895818515674458036525540701370515862480236803545611546590702634429369653768395235816180360099982791680} a^{12} + \frac{3449711437619064041162461057864560033724562961146000566349504672777153571311191261703521761277049}{4356088407929688134077391353085915006613621541497481353994187060290184991918638056349177130517437179266560} a^{11} - \frac{3574804238144936676029167908301565305935311536887370871738875560502597486607603228336594046331998319}{169887447909257837229018262770350685257931240118401772805773295351317214684826884197617908090180049991395840} a^{10} + \frac{936031177084518466600504489989158931104623276464713153178283047045749534389801685074891102555132301}{8494372395462891861450913138517534262896562005920088640288664767565860734241344209880895404509002499569792} a^{9} + \frac{3193749804565815920567993649061438672353487639449439402311828823498621577812990441120739614059788221}{56629149303085945743006087590116895085977080039467257601924431783772404894942294732539302696726683330465280} a^{8} - \frac{19073216951770507249330724890814657367876291286499058644605068078408943274567190017143166910964129285}{4247186197731445930725456569258767131448281002960044320144332383782930367120672104940447702254501249784896} a^{7} + \frac{942056374834270285571544277421832890548808764118355955081445413589392838865888055198626997326573653279}{21235930988657229653627282846293835657241405014800221600721661918914651835603360524702238511272506248924480} a^{6} - \frac{59393207426116130558746835515945136346164382926708214195767849572419517072046092882500046328548418657}{337078269661225867517893378512600565987958809758733676201931141570073838660370801979400611290039781728960} a^{5} - \frac{54702799177955988552230087451884952052665253049045735776808514038259176561378567474355808301177226397}{38893646499372215482833851366838526844764478049084654946376670181162365999273554074546224379619974814880} a^{4} + \frac{29292764570781027742781936395128016981981478541718975207454757009072653136545700836798347523702732340313}{2359547887628581072625253649588203961915711668311135733413517990990516870622595613855804279030278472102720} a^{3} + \frac{678309069948578951580748631233969119172692695264655787913315203315791995835457399454576819704237395671}{131085993757143392923625202754900220106428426017285318522973221721695381701255311880878015501682137339040} a^{2} - \frac{5581883578513776186998347531268006827194355055973538452529226013827868648831721263194750673507039213377}{26217198751428678584725040550980044021285685203457063704594644344339076340251062376175603100336427467808} a + \frac{12518591592835601560792604750403666460340673589737897289312266965049228672840055687869190143909035720111}{5140627206162485997004909911956871376722683373226875236195028302811583596127659289446196686340475974080}
\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1514465884928175030775670173089447534995}{3658111787984720088946092207096001741646512061280596223702191616} a^{23} - \frac{2187798023171205681841979854593315172669277}{234119154431022085692549901254144111465376771921958158316940263424} a^{22} - \frac{120866631772322672097473906501015660450123875}{156079436287348057128366600836096074310251181281305438877960175616} a^{21} + \frac{2264110139535392580914774173636212906251355925}{117059577215511042846274950627072055732688385960979079158470131712} a^{20} + \frac{65661493361969325419878362511091829420124376885}{117059577215511042846274950627072055732688385960979079158470131712} a^{19} - \frac{1303691786895514937291861540214762884567283981889}{78039718143674028564183300418048037155125590640652719438980087808} a^{18} - \frac{20797853204696506690089619531080795024085455639125}{117059577215511042846274950627072055732688385960979079158470131712} a^{17} + \frac{887804925323571985940121226822753568622195275713625}{117059577215511042846274950627072055732688385960979079158470131712} a^{16} + \frac{13323836531136384344622704980995799051829623087265}{1625827461326542261753818758709334107398449805013598321645418496} a^{15} - \frac{26996185756590245811449161907475069845210535048239129}{14632447151938880355784368828384006966586048245122384894808766464} a^{14} + \frac{146300709058580718637084669042150820249254637513727875}{14632447151938880355784368828384006966586048245122384894808766464} a^{13} + \frac{1948996544101236079152265028941203114845194873400853175}{9754964767959253570522912552256004644390698830081589929872510976} a^{12} - \frac{2301083188589772529406063318098719927988200715321037225}{914527946996180022236523051774000435411628015320149055925547904} a^{11} + \frac{1443977678582674828138393329389768027271906324237946025}{914527946996180022236523051774000435411628015320149055925547904} a^{10} + \frac{404950804531584122544205736046551315104843694815134452375}{2438741191989813392630728138064001161097674707520397482468127744} a^{9} - \frac{11653032216592275560722915079814419917253726667190013470075}{7316223575969440177892184414192003483293024122561192447404383232} a^{8} + \frac{369569238275491928966190055488302388911031172256866801235}{57157996687261251389782690735875027213226750957509315995346744} a^{7} + \frac{498749835526204822883228423698145706203133665889025288717}{67742810888605927573075781612888921141602075208899930068559104} a^{6} - \frac{7871690936852146816094018234636937473911324266453273340375}{22580936962868642524358593870962973713867358402966643356186368} a^{5} + \frac{178055649954830664665697897605619500902081999648703562200525}{67742810888605927573075781612888921141602075208899930068559104} a^{4} + \frac{2111482414618921349882025750855203492846254272444080876905}{2822617120358580315544824233870371714233419800370830419523296} a^{3} - \frac{13341403993307262833251198015436605704976717674755290962779}{139388499770794089656534530067672677246094804956584218248064} a^{2} + \frac{127666136027480749092071129778075795515408582371036213113125}{313624124484286701727202692652263523803713311152314491058144} a - \frac{204010889947112889394729016183556539156222308878231936742649}{104541374828095567242400897550754507934571103717438163686048}
}}}

Reduce and factor the defining polynomial of $K$ modulo $p$ and choose one factor $\overline{g}$; this corresponds to choosing a prime lying over $p$ in $K$:

{{{id=51| f = K.defining_polynomial() fbar = GF(p)[x](f) gbar = fbar.factor()[gbar_choice][0] k. = GF(p^(gbar.degree()),modulus=gbar) show(fbar) print(gbar) print(k) ///
\newcommand{\Bold}[1]{\mathbf{#1}}x^{24} + 1201 x^{22} + 2879 x^{21} + 843 x^{20} + 2940 x^{19} + 2150 x^{18} + 1177 x^{17} + 1863 x^{16} + 17 x^{15} + 599 x^{14} + 1681 x^{13} + 2365 x^{12} + 1345 x^{11} + 1185 x^{10} + 59 x^{9} + 2407 x^{8} + 2690 x^{7} + 1713 x^{6} + 2154 x^{5} + 1419 x^{4} + 1258 x^{3} + 1379 x^{2} + 498 x + 2929
x^2 + 321*x + 352 Finite Field in abar of size 3001^2 }}}

Compute the reductions $\overline{xP}$, $\overline{xQ}$ and $\overline{\zeta}$ in k; and define $F = E(k)$.

{{{id=53| xPbar = k(xP.polynomial()) xQbar = k(xQ.polynomial()) zetabar = k(zeta.polynomial()) F = E.change_ring(k) print(xPbar) print(xQbar) print(zetabar) print(F) /// 1971*abar + 2075 44*abar + 1726 934 Elliptic Curve defined by y^2 = x^3 + 2995*x + 7 over Finite Field in abar of size 3001^2 }}}

Choose elements in $E(k)$ (arbitrarily) with $x$-coordinates equal to $\overline{xP}$ and $\overline{xQ}$. If not, create a quadratic extension $k'$ of $k$ such that we do get corresponding points in $E(k')$.

{{{id=55| try: Pbar = F.lift_x(xPbar) Qbar = F.lift_x(xQbar) except ValueError: # No points exist. The following is a hack to construct a quadratic extension # of k such that the finite field is of the right type R = GF(p)[x] hbar = R(x^2) lbar = gbar(hbar) # It's possible that gbar(x^2) isn't reducible over GF(p). # If it's not, gbar(x^2 + tx) will be for some t in GF(p). while not lbar.is_irreducible(): hbar = hbar + R(x) lbar = gbar(hbar) k. = GF(p^(lbar.degree()),modulus=lbar) # Coerce xPbar, xQbar and zetabar into the new k and try lift again xPbar = k(xPbar.polynomial()(hbar)) xQbar = k(xQbar.polynomial()(hbar)) zetabar = k(zetabar.polynomial()(hbar)) F = E.change_ring(k) Pbar = F.lift_x(xPbar) Qbar = F.lift_x(xQbar) show(Pbar) show(Qbar) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(1971 \mbox{abar}^{2} + 2912 \mbox{abar} + 2075 : 502 \mbox{abar}^{3} + 2259 \mbox{abar}^{2} + 1954 \mbox{abar} + 1043 : 1\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(44 \mbox{abar}^{2} + 132 \mbox{abar} + 1726 : 1755 \mbox{abar}^{3} + 395 \mbox{abar}^{2} + 2438 \mbox{abar} + 1564 : 1\right)
}}}

The Weil Pairing. If $\langle \overline{P},\overline{Q} \rangle = \overline{\zeta}$, we are done. Otherwise set $\overline{Q} = -\overline{Q}$.

{{{id=32| if -(Pbar._miller_(Qbar,3)/Qbar._miller_(Pbar,3)) != zetabar: Qbar = -Qbar print(Qbar) /// (44*abar^2 + 132*abar + 1726 : 1755*abar^3 + 395*abar^2 + 2438*abar + 1564 : 1) }}}

Finally, we calculate the matrix of Frobenius with respect to the basis $(\overline{P},\overline{Q})$.

{{{id=57| show(frob_matrix(3, (Pbar, Qbar))) ///
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rr} 1 & 1 \\ 1 & 2 \end{array}\right)
}}}