Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

This is Cipolla's algorithm, I believe.

The integers mod $p$ we call $\mathbf{F}_p$, and since $h^2 -4x$ is a quadratic nonresidue mod $p$, the polynomial $P(Y) := Y^2-(h^2-4x) \in \mathbf{F}_p[Y]$ has no roots. We can then mod out the polynomial ring $\mathbf{F}_p[Y]$ to get $\mathbf{K} := \mathbf{F}_p[Y]/(Y^2-(h^2-4x))$ (which by some algebra we know is isomorphic to $\mathbf{F}_{p^2}$). It is in this field $\mathbf{K}$ that $h^2-4x$ has a square root (one can think of it as the indeterminate $Y = \sqrt{h^2-4x}$)

In this extension field $\mathbf{K}$ (which is still characteristic $p$, so $(m+n)^p = m^p+n^p$ for all $m,n\in \mathbf{K}$) we have that $\left(h + \sqrt{h^2-4x}\right)^p = h^p + (\sqrt{h^2-4x})^p$.

By Euler's criterion, $(h^2-4x)^{\frac{p-1}{2}} \cong -1 \pmod p$ and Fermat's little theorem $h^p \cong h \pmod p$, and all field operations in $\mathbf{F}_p$ are the same in $\mathbf{K}$ on $\mathbf{F}_p$ elements. Therefore $h^p + (\sqrt{h^2-4x})^p = h + (h^2-4x)^{\frac{p-1}{2}} \sqrt{h^2-4x} = h - \sqrt{h^2-4x}$.

By now, with all that math we conclude that $\left(h + \sqrt{h^2-4x}\right)^p = h - \sqrt{h^2-4x}$. The same argument also yields $\left(h - \sqrt{h^2-4x}\right)^p = h + \sqrt{h^2-4x}$.

Finally we get to the square root of $x$. Clearly $$4x = h^2 - (h^2 - 4x) = (h + \sqrt{h^2-4x})(h - \sqrt{h^2-4x}) = (h+\sqrt{h^2-4x})(h+\sqrt{h^2-4x})^p = (h+\sqrt{h^2-4x})^{p+1}$$

Now, the $k$th term of the Lucas sequence $V_k := hV_{k-1} + xV_{k-2}$ is $V_k = a^k + b^k$ where $a = \frac{h + \sqrt{h^2-4x}}{2}$ and $b = \frac{h - \sqrt{h^2-4x}}{2}$. So $$V_{\frac{p+1}{2}} = \left(\frac{h + \sqrt{h^2-4x}}{2}\right)^{\frac{p+1}{2}} + \left(\frac{h - \sqrt{h^2-4x}}{2}\right)^{\frac{p+1}{2}}$$

$$V_{\frac{p+1}{2}} = \left(\frac{1}{2}\right)^{\frac{p+1}{2}} \left( (h + \sqrt{h^2-4x})^{\frac{p+1}{2}} + (h - \sqrt{h^2-4x})^{\frac{p+1}{2}} \right)$$

$$V_{\frac{p+1}{2}} = \left(\frac{1}{2}\right)^{\frac{p+1}{2}} ( \sqrt{4x} + \sqrt{4x}) = \left(\frac{2}{2^{\frac{p-1}{2}}}\right) \sqrt{x} = \pm 2 \sqrt{x}$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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