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$.

excerpt 1

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:

excerpt 2

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.