I try to understand the General Number Field Sieve, based on Michal Case paper "A beginner's guide to the general number field sieve". I was able to reproduce some results from the example, i.e. $$\prod_{(a,b)\in V} (a+bm) = 459997127517955195582606376960000$$ and $$\prod_{(a,b)\in V}(a+b\theta)=58251363820606365*\theta^{2}+149816899035790332*\theta+75158930297695972$$
Now I need to compute square roots in $\mathbb{Z}$ and $\mathbb{Z}[\theta]$. But the next step result from the paper seems to be incorrect, since $$459997127517955195582606376960000 \neq 2553045317222400^{2}$$
How should I compute both square roots to get the results presented in the paper? How to calculate square root in $\mathbb{Z}[\theta]$? Next, how can I find the mapping $\phi$ required in the next step of the algorithm?
Let $$ h(x):=58251363820606365x^2+149816899035790332x+75158930297695972 $$
What you want to solve is $$ (u+vx+wx^2)^2 \equiv h(x) \pmod{x^3+15x^2+29x+8} $$ so a necessary condition is $$ (u+vx+wx^2)^2 \equiv h(x) \pmod{x^3+15x^2+29x+8,p} $$ for any prime $p$.
The reason for introducing modulo $p$ is because the equation is much easier to solve to get an initial solution (for small $p$'s), plus you can then use lifting to lift the equations to larger modulus (from modulo $p^k$ to $p^{k+1}$ in the example below, but in practice it should be $p^k$ to $p^{2k}$ for efficiency).
One important note here is the the absolute values of $u,v,w$ are bounded, so once you have lifted the solutions to large enough values they will be correct even without the modulus $p^k$ (If one of $u,v,w$ is too large then after modulo $f(x)$ you must have an overly huge coefficient). This answer is kind of incomplete since I will not touch upon how to bound it efficiently.
This $p$-adic lifting method is how some of the more modern methods solve the squareroot step (For example this.)
It is much simpler to work with $p$ such that $f(x):= x^3+15x^2+29x+8$ is irreducible modulo $p$, but not strictly necessary. For example if you chose a $p$ such that $x^3+15x^2+29x+8$ splits into $3$ factors $(x-r_1)(x-r_2)(x-r_3)$, you can still solve $$ (u+vx+wx^2)^2 \equiv 58251363820606365x^2+149816899035790332x+75158930297695972 \pmod{x-r_i,p} $$ for each of the $r_i$.
Then you can combine the results (modulo large enough $p^k$) via CRT to get a solution modulo $(f(x),p^k)$. The problem with this method is there are $2^3$ way to form the final CRT, since each $x-r_i$ has two possibilities (if $g(x)$ is a squareroot then $-g(x)$ also is one). This can be resolve by simply trying each one of them, so the method can still work. In particular since the linear form $\pmod{x-r_i,p^k}$ is simpler so there could be some advantages (which is why the paper earlier proposes it).
As an example, I chose $p=5$ so that $x^3+15x^2+29x+8$ is irreducible. So start by solving $$ (u+vx+wx^2)^2 \equiv h(x)\equiv 2x+2 \pmod{x^3+15x^2+29x+8,5} $$ By trying all values, we find that $1+x+4x^2$ works. A better solution would have been to treat it as a squareroot problem in a finite field of size $5^3$.
Next, we lift the solution to modulo $5^2$. $$ ((1+5u)+(1+5v)x+(4+5w)x^2)^2 \equiv h(x) \equiv 15x^2+7x+22 \pmod{x^3+15x^2+29x+8,5^2} $$ Since $0\leq u,v,w < 5$ it's still easy to bruteforce them, though not exactly the best way. Notice that this part is also incomplete since I did not really justify why there is only one solution for the lift.
After some bruteforcing, we get $(u,v,w)= (3,2,0)$. Hence $$ (16+11x+4x^2)^2 \equiv h(x) \pmod{x^3+15x^2+29x+8,5^2} $$
Continuing in this manner: $$ \begin{align} (16+36 x+29 x^2)^2 &\equiv h(x) \pmod{f(x),5^3}\\ (141+161 x+154 x^2)^2 &\equiv h(x) \pmod{f(x),5^4}\\ (766+1411 x+779 x^2)^2 &\equiv h(x) \pmod{f(x),5^5}\\ (13266 + 7661 x + 779 x^2)^2 &\equiv h(x) \pmod{f(x),5^6}\\ (44516 + 7661 x + 63279 x^2)^2 &\equiv h(x) \pmod{f(x),5^7}\\ (122641 + 7661 x + 375779 x^2)^2 &\equiv h(x) \pmod{f(x),5^8}\\ (903891 + 398286 x + 1547654 x^2)^2 &\equiv h(x) \pmod{f(x),5^9}\\ (8716391 + 4304536 x + 9360154 x^2)^2 &\equiv h(x) \pmod{f(x),5^{10}}\\ (8716391 + 14070161 x + 19125779 x^2)^2 &\equiv h(x) \pmod{f(x),5^{11}}\\ (8716391 + 62898286 x + 214438279 x^2)^2 &\equiv h(x) \pmod{f(x),5^{12}} \end{align} $$
At each step, if $g(x)=u+vx+wx^2$ is a solution modulo $(f(x),5^k)$, then so is $(-u-vx-wx^2)$ and hence $\overline g(x)=(5^k-u)+(5^k-v)x+(5^k-w)x^2$ is also a solution.
If $h(x)$ is indeed a square $r(x)^2$, then after sufficient steps we ought to arrive at the solution via either $g(x)$ or $\overline g(x)$ (once our solutions are "large enough"). Indeed, at step $12$, we have $$ \begin{align*} \overline g(x) &= 5^{12}-8716391 + (5^{12}-62898286) x + (5^{12}-214438279) x^2\\ &= 235424234 + 181242339 x + 29702346 x^2 \end{align*} $$ and we can check that $$ \overline g(x)^2 \equiv h(x) \pmod{f(x)} $$
i.e. the squareroot we want is $235424234 + 181242339 x + 29702346 x^2$. (Remark again that there is a way to know when we have done enough lifting.)
Now taking the homomorphism $x\mapsto m=31 \pmod n$, $$ \phi((235424234 + 181242339 x + 29702346 x^2)^2) \equiv 34397891249^2 \pmod n $$ For the rational side we have $$ 45999712751795195582606376960000 = 6782308806873600^2 $$ Therefore this gives $$ 6782308806873600^2 \equiv 34397891249^2 \pmod{n = 45113} $$ which is correct since both sides is $\equiv 27005$. Finally we take the gcd: $$ \gcd(6782308806873600+34397891249,45113) = 229 $$ which solves the problem.