How to reduce Hilbert class polynomial roots and complex j-invariants into finite fields

Question

In PhD thesis "Cryptographic Schemes Based on Isogenies" by Anton Stolbunov on page 16, there are reductions of $\eta_i$, where $\{\eta_1, \dots, \eta_6\}$ are the roots of the Hilbert polynomial over the field $H$. These reductions $\bar{\eta}_i$ are made in the fields $\cal O$$_H/\mathfrak{p}_j$, $i \in [1,6], j \in [1,12]$ above $47$ (see Table 1.4). There is a statement also:

"Since the roots $\eta_i$ of the Hilbert class polynomial $B(X)$ lie in $\cal O$$_H$, their images $\bar{\eta}_i$ in $F$ are well-defined."

I have the following questions:

1. How it is possible to reduce such $\eta$ modulo prime ideals $\mathfrak{p}$ in the field over $\mathbb{F}_p; p=47$? It would be great if someone gives the same example as it is in the thesis, for instance, what should be my steps when I reduce $\eta_2$ in the field $\cal O$$_H/\mathfrak{p}_3$? According to the table, $\bar{\eta}_2$ must be $12$.

2. If I have a complex value of $j$-invariant of an elliptic curve, how could I find a bijection between it and its reduction in a finite field (page 17)?

Answer 1

You should not think of $\eta_i$ as a complex number. You should think of $\eta_i$ as a root of $B(X)$. Since $B(X)$ has integer coefficients, you can reduce $B(X)$ mod $p$ (or equivalently mod $\mathfrak{p}$), simply by reducing each coefficient mod $p$. The roots of $B(X) \bmod p$ then yield the values of $\eta_i \bmod \mathfrak{p}$.

The following magma code, which is a slight elaboration of the magma code given in page 16 of Stolbunov's thesis, reconstructs Table 1.4 on page 16 of the thesis.

> D := -152;
> K<t> := QuadraticField(D);
> H<n> := ext< K | HilbertClassPolynomial(D) >;
> p := Factorization(47*RingOfIntegers(H));
> eta := Roots(PolynomialRing(H)!HilbertClassPolynomial(D));
> for j in [1..12] do
for>     F, phi := ResidueClassField(Order(p[j][1]), p[j][1]);
for>     [phi(eta[i][1]) : i in [1..6]];
for> end for;
[ 12, 41, 19, 15, 27, 24 ]
[ 19, 15, 24, 27, 41, 12 ]
[ 27, 24, 41, 12, 19, 15 ]
[ 15, 19, 27, 24, 12, 41 ]
[ 24, 27, 12, 41, 15, 19 ]
[ 41, 12, 15, 19, 24, 27 ]
[ 15, 19, 41, 12, 24, 27 ]
[ 24, 27, 19, 15, 41, 12 ]
[ 41, 12, 27, 24, 19, 15 ]
[ 12, 41, 24, 27, 15, 19 ]
[ 19, 15, 12, 41, 27, 24 ]
[ 27, 24, 15, 19, 12, 41 ]
> 

Note that the columns above appear in a different order than the order of the columns in Table 1.4 on page 16. This is simply because there is no canonical ordering to tell you which root of the polynomial is $\eta_1$, which one is $\eta_2$, etc.