2016-02-01.sagews

%md
# Feb 1, 2016: Factoring Primes

Our goal today is to more deeply understand the problem of "factoring primes".

Recall our motivation is that to explicitly compute $\rho_{E,3}(\text{Frob}_P)$ for primes $P\mid 2$,
we need to explicitly compute the reduction map from $\mathcal{O}_K$ to the residue class
field $F_P = \mathcal{O}_K/P$.  Since $K=\QQ(E[3])$ has degree $48$, this is more challenging!

First recall the easy case...

Feb 1, 2016: Factoring Primes

Our goal today is to more deeply understand the problem of "factoring primes".

Recall our motivation is that to explicitly compute $\rho_{E,3}(\text{Frob}_P)$ for primes $P\mid 2$, we need to explicitly compute the reduction map from $\mathcal{O}_K$ to the residue class field $F_P = \mathcal{O}_K/P$. Since $K=\QQ(E[3])$ has degree $48$, this is more challenging!

First recall the easy case...

Sketch of the Easy case.

Warm up: Everybody knows the easy case of prime factorization.

Theorem: Suppose $K = \QQ(\alpha) = \QQ[x]/(f)$, with $\alpha=[x]$ integral, and that $p\nmid \text{disc}(f)$.

Suppose $\bar{f} \prod_{i=1}^m f_i \in \FF_p[x]$ is the prime factorization of $f$ modulo $p$ (note that there are no exponents since $p$ is unramified by hypothesis)

Then the prime factorization of $p$ in $R=\mathcal{O}_K$ is $\prod (p, f_i(\alpha))$, which is of course relatively easy to compute.

Proof: Our hypothesis that $p\nmid \text{disc}(f)$ implies that $p\nmid [R:\ZZ[\alpha]]$. Thus $(R\otimes \FF_p) \cong \FF_p[x]/(\bar{f})$. By the Chinese Remainder Theorem, $$R / (\prod (p, f_i(\alpha))) \cong R\otimes \FF_p \cong R/pR \cong R / (\prod P_i),$$ where $pR = \prod P_i$ is the prime ideal factorization of $pR$ in $R$.

To be completely convinced, make sure you think about the map $R \to R/P_i$ for each $i$.

How to do something more general.

Now suppose that $p\mid \text{disc}(f)$. We may still consider (in the abstract) the ring homomorphism $$S = \ZZ[\alpha] \hookrightarrow R$$ and $$R \to R/pR.$$ Our goal is to either show that $p \nmid [R:S]$ or to find a ring $S'$ with $S \subset S' \subset R$ and $p\mid [S': S]$.

If we can do that, then we can compute $R/pR$, by just repeatedly finding bigger and bigger $S'$, then use that $R/pR \cong S'/pS'$. More generally, if we do this for all $p \mid \text{disc}(f)$, which we can (in theory!) find by factoring, then we can add together all such $S'$'s to compute $R$ itself.

So, how do we approach this problem?

WARNING: I explained this is in great detail in a previous computational number theory course with about 10 students. We then had one exercise which was to carry out the algorithm very explicitly in one single interesting example, and everybody got it wrong except Robert Miller... The point is that either the algorithm seems easy but is confusing to implement, or I (and the literature) is bad at explaining it.

The key idea (called the "Round 2 Algorithm")

Suppose $S\subset R$ is a subring and $p$ is a prime that might divide $R/S$.

GOAL: Define a ring $S'$ with $S \subset S' \subset R$ such that (1) $S'=S$ when $p\nmid [R:S]$ and (2) $p\mid [S':S]$ when $p\mid [R:S]$.

Here's the definition of $S'$.

Let $I_p = \{ x \in S : x^m \in pS \text{ for some } m\geq 1\}$, which we call the $p$-radical of $S$. It's the inverse image of the nilradical of $S/pS$.

Let $\varphi: S\to \text{End}(I_p/p I_p)$ be the homomorphism that sends $\alpha\in S$ to left multiplication by $\alpha$.

Let $U = \ker(\varphi)$.

Define $S' = \frac{1}{p} U \subset R$.

Next up:

• Why does $S'$ have the properties we want?

• How can we compute $S'$?

︠da329637-9b59-4c97-9208-58ffdcc29260︠