2016-01-29-mod2.sagews

January 29, 2016: Explicitly compute the mod-2 representation attached to 11a

As a warm-up before returning to $\rho_{E,3}$, let's compute $\rho_{E,2}:G_{\QQ} \to \text{GL}_2(\FF_2)$ for $E=11a$.

This is more straightforward to do without getting stuck with really difficult computations that force us to learn things more deeply.

E = EllipticCurve('11a')
E.galois_representation().is_surjective(2)

True

E.galois_representation().non_surjective()

[5]

groups.matrix.GL(2,GF(2)).cardinality()

6

# Compute random points over QQbar...
%time
f = E.division_polynomial(2)
Ebar = E.change_ring(QQbar)
v = f.roots(ring=QQbar, multiplicities=False)
P = Ebar.lift_x(v[0])
Q = Ebar.lift_x(v[1])
P, Q

((4.346308158205395? : -1/2 : 1), (-1.673154079102698? - 1.320848922269076?*I : -1/2 : 1)) CPU time: 0.06 s, Wall time: 0.06 s

# ... and try some random linear combinations and get something of degree 6.
(P[0] + P[1] - Q[0] + Q[1]).minpoly()

x^6 + 6*x^5 - 47*x^4 - 228*x^3 + 604*x^2 + 1680*x + 175451/16

# Or just take the Galois closure of field defined by f (which luckily has degree 6).
f = E.division_polynomial(2)
K.<a> = NumberField(f,'b').galois_closure()
K

Number Field in a with defining polynomial x^6 - 68*x^4 - 120*x^3 + 1552*x^2 + 8568*x + 16316

R = K.maximal_order(); R

Maximal Order in Number Field in a with defining polynomial x^6 - 68*x^4 - 120*x^3 + 1552*x^2 + 8568*x + 16316

EK = E.change_ring(K)
T = EK.torsion_subgroup()
T

Torsion Subgroup isomorphic to Z/10 + Z/2 associated to the Elliptic Curve defined by y^2 + y = x^3 + (-1)*x^2 + (-10)*x + (-20) over Number Field in a with defining polynomial x^6 - 68*x^4 - 120*x^3 + 1552*x^2 + 8568*x + 16316

# Basis
P0 = (T.0*5).element()
P1 = T.1.element()
P0.order(); P1.order()
P0, P1

2 2 ((105/67573*a^5 - 2085/270292*a^4 - 5046/67573*a^3 + 12011/67573*a^2 + 157524/67573*a + 352835/67573 : -1/2 : 1), (723/540584*a^5 - 2931/540584*a^4 - 21585/270292*a^3 + 54779/270292*a^2 + 381035/270292*a + 504485/135146 : -1/2 : 1))

def frob(X):
    p = X[0].parent().characteristic()
    return X.parent()([X[0]^p, X[1]^p])

def in_terms_of_basis(X, P0mod, P1mod):
    for i in range(2):
        for j in range(2):
            if X == i*P0mod + j*P1mod:
                return [i,j]
    raise ValueError

def rhoFrob(prime):
    """
    Compute the matrix of Frob_P, where P is a prime of the ringer of integers of K.
    The 2-torsion points P0, P1 in E(K) above must be defined.

    INPUT:
       - P = prime ideal of R.
    """
    F = prime.residue_field()
    EF = E.change_ring(F)
    P0mod = EF(P0)
    P1mod = EF(P1)
    return matrix(GF(2), 2, [in_terms_of_basis(frob(Q), P0mod, P1mod) for Q in [P0mod, P1mod]]).transpose()

K.discriminant().factor()

-1 * 2^4 * 11^3

K.factor(3)

(Fractional ideal (3, -9/5324*a^5 + 51/5324*a^4 + 323/5324*a^3 - 597/2662*a^2 - 3601/2662*a - 9277/2662)) * (Fractional ideal (3, -9/5324*a^5 + 51/5324*a^4 + 323/5324*a^3 - 597/2662*a^2 - 3601/2662*a - 11939/2662))

def frob_report(p):
    R.<X> = GF(2)[]
    for P, e in K.factor(p):
        A = rhoFrob(P)
        print '-'*30
        print "p = %s"%p
        print A
        print A.charpoly()
        print X^2 - E.ap(p)*X + p

for p in primes(10):
    if 2*11%p == 0: continue
    frob_report(p)

------------------------------ p = 3 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 3 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 5 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 5 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 7 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 7 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 7 [1 0] [1 1] x^2 + 1 X^2 + 1

%time
frob_report(next_prime(10^40))

------------------------------ p = 10000000000000000000000000000000000000121 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 10000000000000000000000000000000000000121 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 CPU time: 0.81 s, Wall time: 0.83 s

for p in primes(100):
    if 2*11%p == 0: continue
    frob_report(p)

------------------------------ p = 3 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 3 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 5 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 5 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 7 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 7 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 7 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 13 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 13 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 13 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 17 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 17 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 17 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 19 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 19 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 19 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 23 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 23 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 29 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 29 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 29 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 31 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 31 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 37 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 37 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 41 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 41 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 41 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 43 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 43 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 43 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 47 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 47 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 47 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 47 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 47 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 47 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 53 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 53 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 53 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 53 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 53 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 53 [1 0] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 59 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 59 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 61 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 61 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 61 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 67 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 67 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 71 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 71 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 73 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 73 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 73 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 79 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 79 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 79 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 83 [1 0] [1 1] x^2 + 1 X^2 + 1 ------------------------------ p = 83 [1 1] [0 1] x^2 + 1 X^2 + 1 ------------------------------ p = 83 [0 1] [1 0] x^2 + 1 X^2 + 1 ------------------------------ p = 89 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 89 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 97 [0 1] [1 1] x^2 + x + 1 X^2 + X + 1 ------------------------------ p = 97 [1 1] [1 0] x^2 + x + 1 X^2 + X + 1

Remark: Suppose $\ell$ is very small, e.g., $\ell=2$ or $\ell=3$ so we can explicitly compute $\rho_{E,\ell}$ (I hope). Here's a reflection of "something deep". Suppose $p$ is a HUGE PRIME. Consider the quantities:

A: $p + 1 - \#E(\FF_p) \mod \ell \in \FF_{\ell}$

B: $\text{Tr}(\rho_{E,\ell}(\text{Frob}_p)) \in \FF_\ell$.

These two quantities are equal (by the theorem I mentioned -- it is more generally called the "Eichler-Shimura relation".) In particular, $\#E(\FF_p) \equiv p + 1 - \text{Tr}(\rho_{E,\ell}(\text{Frob}_p)) \pmod{\ell}$.

The first is hard to compute, since for $p$ HUGE, computing $\#E(\FF_p)$ is VERY difficult. Even computing anything at all in $E(\FF_p)$ is at least pretty hard.

On the other hand, to compute $\rho_{E,\ell}(\text{Frob}_p)$, after doing some big initial computation, you just need to find a small prime $q$ such that $\text{Frob}_p = \text{Frob}_q$, and you're done. Finding $q$ is purely a computation in the number field $K=\QQ(E[\ell])$. It's a lot like quadratic reciprocity, except the "congruence" there is replaced by "defining the same element of $\text{Gal}(K/\QQ)$".

Schoof: Incidentally, a key idea used in Schoof's groundbreaking algorithm for computing $E(\text{Frob}_p)$ for large $p$, which is at the foundation of elliptic curve cryptograph, is the relation above, which reduces computing $\#E(\FF_p)$ to the problem of computing $\text{Tr}(\rho_{E,\ell}(\text{Frob}_p)) \pmod{\ell}$ for sufficiently many primes $\ell$.

︠3887a504-6b1c-4044-a977-125de2312366︠