Revision history [back]

You want $h$ in $\mathbb{Z}[x]$ such that both $h$ and the reduction $h\text{ mod }p \in \mathbb{F}_p[t]$ are irreducible. For example, like this:

n = 5
p = 3
R.<t> = PolynomialRing(ZZ)
h = t^n
while not h.is_irreducible() or not h.change_ring(GF(p)).is_irreducible():
    h = t^n + R.random_element(degree=n-1)
print(h)

Example output:

t^5 - 23*t^4 - t^3 - t^2 - 1

You want $h$ in $\mathbb{Z}[x]$ such that both $h$ is irreducible and the reduction $h\text{ mod }p \in \mathbb{F}_p[t]$ are irreducible. ideal $(p)$ in the ring of algebraic integers of $\mathbb{Q}[t]/h(t)$ is prime. For example, like this:

n = 5
p = 3
R.<t> = PolynomialRing(ZZ)
h = t^n
while not h.is_irreducible() or not h.change_ring(GF(p)).is_irreducible():
NumberField(h, name='m').ideal(p).is_prime():
    h = t^n + R.random_element(degree=n-1)
print(h)

Example output:

t^5 + t^4 - 23*t^4 - t^3 - t^2 - 1
5*t^3 + 2*t^2 + t + 2

You want $h$ in $\mathbb{Z}[x]$ $\mathbb{Z}[t]$ such that $h$ is irreducible and the ideal $(p)$ in the ring of algebraic integers of $\mathbb{Q}[t]/h(t)$ is prime. For example, like this:

n = 5
p = 3
R.<t> = PolynomialRing(ZZ)
h = t^n
while not h.is_irreducible() or not NumberField(h, name='m').ideal(p).is_prime():
    h = t^n + R.random_element(degree=n-1)
print(h)

Example output:

t^5 + t^4 - 5*t^3 + 2*t^2 + t + 2

(In a previous version of this answer I said you want $h$ $h \in \mathbb{Z}[t]$ such that both $h$ and $h\text{ mod }p \in \mathbb{F}_p$ \mathbb{F}_p[t]$ are irreducible, but this only works—by the Kummer-Dedekind theorem—if the ring of integers of $K = \mathbb{Q}[t]/h(t)$ is generated by a root of $h$, which is already not the case e.g. for $h = t^2 + 3$ and $p=2$.)