Factorization of Hilbert class polynomials over prime fields

Abstract

Let $D$ be a negative integer congruent to $0$ or $1\mathrm{mod}4$ and $\mathcal{O}={\mathcal{O}}_D$ be the corresponding order of $K=\mathbb{Q}(\sqrt{D})$. The Hilbert class polynomial $H_D(x)$ is the minimal polynomial of the $j$-invariant $j_D=j(\mathbb{C}/\mathcal{O})$ of $\mathcal{O}$ over $K$. Let $n_D=({\mathcal{O}}_{\mathbb{Q}(j_D)}:\mathbb{Z}[j_D])$ denote the index of $\mathbb{Z}[j_D]$ in the ring of integers of $\mathbb{Q}(j_D)$. Suppose $p$ is any prime. We completely determine the factorization of $H_D(x)$ in ${\mathbb{F}}_p[x]$ if either $p\nmid n_D$ or $p\nmid D$ is inert in $K$ and the $p$-adic valuation $v_p(n_D)\le 3$. As an application, we analyze the key space of Oriented Supersingular Isogeny Diffie-Hellman (OSIDH) protocol proposed by Colò and Kohel in 2019 which is the roots set of the Hilbert class polynomial in ${\mathbb{F}}_{p^2}$.