Number Field Sieve for factorization with non-monic non-linear polynomial. Can't understand calculating ideal valuations

Question

There is a paper "Factoring integers with the number field sieve" (download it here, for example).

I can't understand how they reason the correctness of computing ideal valuations in the case of using non-monic non-linear polynomials, which is given on pages 50-51 of the PDF above.

Here are the excerpts I don't understand:

Assume that $f(X,Y) = c_d X^d + c_{d-1} X^{d-1} Y^1 + ... + c_{1} X Y^{d-1} + c_{0} Y^d$.

Actually this one is pretty good. I was able to prove that $A$ is closed under multiplication and that $A=\mathbb{Z}[\alpha]\cap\mathbb{Z}[\alpha^{-1}]$.

The real problems emerge when it comes to the next excerpt:

I have the following questions:

1. How do first degree prime ideals of $A$ look like (what are their generators)? And how do I deduce it from that mappings of $\alpha$ and $\alpha^{-1}$?

2. How do I test if a number belongs to a first degree prime ideal of $A$?

3. Why do we use $A + \alpha A$ instead of just $A$? How $A + \alpha A$ is related to $A$ and its first degree prime ideals?

So, technically, I don't understand the last excerpt at all.

I would be very grateful if someone explains it to me or gives a good literature reference.

Answer 1

Katja Schmidt-Samoa's diploma thesis is the best reference on this topic. It is available on her website.

Answer 2

I want to write an additional question in stead of an answer because I have the same problem. Having read Katja Schmidt-Samoa's thesis, most of the things are explained, except for one part - why is it true that if $ p\nmid b$ then

$$ l_{\mathfrak{p}_{p,\infty},A}(a-b\alpha) = -\operatorname{ord}_p(c_d). $$

For the case when $p\mid b$, it is not hard to see that $l_{\mathfrak{p}_{p,\infty},A}(a-b\alpha)= e_p(F(a,b)) -\operatorname{ord}_p(c_d)$, where $F$ is the homogenized polynomial, and the other cases are simply roots at $\mathbb{F}_p$ that behave the same way as if $F(x,1)$ were monic.

The only step required to prove the abovementioned is to show that $$ l_{\mathfrak{p}_{p,\infty},A}(\alpha) = -\operatorname{ord}_p(c_d), $$ but here I can only show that $$ l_{\mathfrak{p}_{p,0},A}(\alpha) - l_{\mathfrak{p}_{p,\infty},A}(\alpha) = \operatorname{ord}_p(c_0)-\operatorname{ord}_p(c_d). $$ Equivalently it would be enough to prove that $l_{\mathfrak{p}_{p,0},A}(\alpha) = \operatorname{ord}_p(c_0)$, that is, that the valuation of $\mathfrak{p}_{p,0}$ in $\alpha$ is simply the degree to which $p$ divides the leading coefficient of $F(x,1)$ whose root is $\alpha$. This seems natural, but I can't find a way to prove it. Any help would be welcome.