I've been doing some elliptic curve cryptography, and a library I'm using has this slightly bizarre algorithm for computing modular square roots:
Let $x$ be some quadratic residue modulo $p$ for some large prime $p$. Let $h$ be some element of $\mathbb{Z} \setminus p\mathbb{Z}$ such that $h^2-4x$ has no square root modulo $p$. Let $V_n$ be the Lucas sequence with $V_0=2$, $V_1=h$ and $V_n=hV_{n-1}+xV_{n-2}$. Let $k = \frac{p+1}{2}$. Then $V_k = 2\sqrt{x}$. This is obviously less efficient than the well known algorithm for $p \cong 3 \mod 4$, but apparently works in a more general case
Immediately, one might believe this definition to be contradictory; indeed the characteristic equation of this recurrence is solved by square rooting $h^2-4x$, but, being a Lucas sequence, this impossible term never appears in any particular value of $V_k$.
The only reference to this algorithm I've found is as an exercise in an undergraduate-level textbook, which suggests that this is solvable by some fairly simple maths, but nothing I've tried seems to result in a solution -- computing $V_{\frac{p+1}{2}}^2$ yields $V_{\frac{p+1}{2}}^2 = V_2 + 2x^{\frac{p+1}{2}} = h^2 - 2x + 2x^{\frac{p+1}{2}}$, which looks almost nothing like the $4x$ I would expect.