Problem with ideal arithmetic in free relations of NFS I am studying the number field sieve on Crandall and Pomerance - "Prime numbers: a computational perspective" (2001). Now I am at the free relations chapter and there is something I cannot understand...
Let's take $f$ a monic irreducible polynomial in $\mathbb{Z}[x]$ (with degree $d$ and with a root $\alpha$), let $p\in\mathbb{Z}$ be a prime and let's consider
$$R(p):=\{r\in\mathbb{Z}_p : f(r)\equiv 0 \pmod{p}\}$$
Pomerance asserts that if $R(p)$ is a set of exactly $d$ elements, then the product of the prime ideals $(p,\alpha-r)$ for $r\in R(p)$ in the ring $I$ of algebraic integer of $\mathbb{Q}[\alpha]$ is equal to $(p)$.
My attempt: $R(p)$ has $d$ elements iff $f=(x-r_1)\cdots(x-r_d) \pmod{p}$ with $r_i$ all the distinct elements of $R(p)$, so we have $(\alpha-r_1)\cdots(\alpha-r_d)=kp$ for some integer $k$. Now
$$(p,\alpha-r_1)\cdots(p,\alpha-r_d)=\left(p^d,p^{d-1}(\alpha-r_i),\ldots,(\alpha-r_1)\cdots(\alpha-r_d)\right)=\left(p^d,p^{d-1}(\alpha-r_i),\ldots,kp\right)$$
Now I cannot understand why this ideal should be equal to $(p)$ in $I$...
The inclusion $\left(p^d,p^{d-1}(\alpha-r_i),\ldots,kp\right)\subseteq(p)$ looks quiet easy. In fact, $\alpha\in I$ and $z\in I$ for all $z\in \mathbb{Z}$, so $\alpha-r_i\in I$ and $p\in I$, thus all the generators on the left are in $(p)$.
 A: Let $f(x) \in \mathbb{Z}[x]$ be monic irreducible of degree $d$, and let $p\ge d$ be a rational (integer) prime such that $f(x)$ has $d$ distinct roots mod $p$.
For convenience we define the set $R(p) = \{r\in [0,\ldots,p-1] \mid f(r) \equiv 0 \bmod p\}$. By assumptions $|R(p)| = d$.  This slight departure from the notation in the Question has the advantage that each $r_i \in R(p)$ is distinct as both an integer and as a residue mod $p$.  Henceforth we will use the index $1\le i\le d$ to indicate the $r_i \in R(p)$ without explicit mention.
Let $\alpha$ be a root of $f(x)$ in a simple field extension $\mathbb Q(\alpha)$, and let $I$ be the integral closure of $\mathbb{Z}$ in $\mathbb{Q}(\alpha)$.  Certainly $\mathbb Z[\alpha] \subseteq I$, but the containment will sometimes be proper.
The goal is to show that the product of the $d$ ideals $(p,\alpha - r_i)$ in $I$ is equal to the principal ideal $pI$.  A one-line summary of the proof is:
$$ pI \subseteq \bigcap_i (p,\alpha - r_i) \subseteq \prod_i (p,\alpha - r_i) \subseteq pI $$
We will establish each link in this chain of subsets in the sections below.
$\underline{\;pI \subseteq \bigcap_i (p,\alpha - r_i)\;}$
This is the easy part since $p\in (p,\alpha - r_i)$ for each $i$.
$\underline{\;\bigcap_i (p,\alpha - r_i) \subseteq \prod_i (p,\alpha - r_i)\;}$
In fact we have equality of these ideals (since for any finite collection the product of ideals is contained in their intersection) because here the ideal factors are pairwise coprime, as the authors Crandall and Pomerance already observed the earlier proof of Lemma 6.2.1 (p.284 of 2nd ed.).  This coprimality also follows from the Comment above by the OP that $\gcd(p,r_i - r_j) = 1$ whenever $i\neq j$, so $(p,\alpha - r_i) + (p,\alpha - r_j) = I$.
The equality of the product and intersection of a finite collection of (pairwise) coprime ideals is often connected with the Chinese remainder theorem for ideals.  For computational aspects of this, see William Stein's notes.
$\underline{\;\prod_i (p,\alpha - r_i) \subseteq pI\;}$
Consider the typical product of elements, one from each factor, and it should be seen that the inclusion above will follow once we establish:
$$ \prod_i \alpha - r_i \in pI $$
since all the other terms in the implied products contain (at least) one factor $p$.
Let $g(x) = \prod_i x - r_i$, so that $f(x),g(x)$ are both monic polynomials of degree $d$ over the integers.  Considering $f(x)$ instead as a polynomial over finite field $\mathbb Z/p\mathbb Z$, the distinctness of roots $r_i$ as residues mod $p$ establish (by polynomial remainder theorem and agreement in degree) that:
$$ f(x) \equiv g(x) \bmod p $$
Since $f(\alpha) = 0$ and by the last observation $f(\alpha) - g(\alpha) \in pI$, it follows that $g(\alpha) = f(\alpha) - (f(\alpha) - g(\alpha)) \in pI$ as desired.
