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

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.

## 2 Answers

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

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.