Quadratic congruence with composite; $ x^2\equiv\ 31\ ({\rm mod}\ 11^4)$ This is an exercise in Burton I want to know the existence of shorter solution : 
Solve $$ x^2\equiv 31\ (11^4)$$ 
Note that we have a algorithm (or program) : If $$ x_k^2\equiv a\ (p^k)$$ then $$ x_k^2 =a+b_kp^k,\ 2x_ky_k = -b_k\ (p),\ x_{k+1} = x_k + y_k p^k $$
Here we have $$ x_{k+1}^2\equiv a\ (p^{k+1})$$ 
So $3^2\equiv -2\ (11) \equiv 31\ (11)$ so that $x_1=3,\ x_2=x_1+y_1 p=3+4\cdot 11=47$
To find solution of original problem we must do this twice more. $47$ is large. Is there more simple calculation ?
[Add] I will add diect computation : 
$$x_1=3,\ b_1=-2,\ y_1=4,\ x_2=47$$
$$ b_2=18,\ y_2=-36,\ x_3=-4309 $$
$$ b_3=13950,\ y_3=48825,\ x_4=64981766$$
And $$ x_4=5008 + 11^4 s,\ 11^4\cdot 1713= 5008^2-31$$
[Add 2] From several helps, I can give shorter : 
$
f(r)\equiv 0 \ (p^k)$ and $f'(r)\neq 0\ (p)$ Then 
$$
f(s)\equiv 0 \ (p^{2k}),\ r\equiv s\ (p^k),\ s=r+tp^k,\ t=-\frac{f(r)}{p^k} f'(r)^{-1} $$where $a^{-1}$ is inversion in ${\bf Z}_{p^k}$
If $r=47,\ k=2,\ f(x)=x^2-31$ we have $$ s= 47+162\cdot 121,\ t=162$$ 
 A: Simple is quite relative, there is an algorithm with fewer steps:
In Algorithm 2.3.11 from Crandall/Pomerance 'Prime numbers' the Hensel lifting is done for $p^{2^i}$ and not for $p^i\;$i.e. this gives an algorithm with $\lceil \log_2(k)\rceil$ steps instead of $k$.
For a polynomial $f(x) \in \mathbb{Z}[x]$, a prime p, and a simple zero $r=r_0$
with $f(r) \equiv 0 \pmod p\;$ and $f'(r) \not \equiv 0 \pmod p,\;$ the algorithm constructs a sequence
$r_i$ with 
$r_i \equiv r_j \pmod {p^{2^j}}$ and $f(r_i) \equiv 0 \pmod {p^{2^i}}\;$ for all $i<j$. 
You are done if $2^i \ge k$.
In your case you get for $k=4\;$ the intermediate roots $r_i=47, 5008\;$ and e.g. for $k=16\;$ they are
$47, 5008, 193837207,4851544439048935.$
Edit: Here is their function newr which computes $r_{i+1}$ from $r_i$
$$x = f(r_i)p^{−2^i}$$
$$z = \left(f'(r)\right)^{−1} \pmod {p^{2^i}}  \quad (*)$$
$$y = −xz \pmod {p^{2^i}}$$
$$r_{i+1} = r_i + yp^{2^i}$$
Note that the $r$ in $(*)$ must actually be $r_i!\;$ The notation is from the book, in my seven year old implementation and the given example values I use $r_i.$
