# How quickly can we calculate $k^2 \bmod p$?

If we are working with a residue number system and start with $k$ such that $0 \le k < p$, how quickly can we find $n$ such that $0 \le n < p$ and $n \equiv k^2 \bmod p$? We know, additionally, that $p$ is prime.

I'd prefer to use as little "memory" or space as possible, but I won't reject something that seems to use it efficiently. Sorry I can't be more precise than this, but I'm just trying to get a good algorithm.

SOME IDEAS

We know that $k^2$ is equal to the sum of the first $k$ odd naturals.

There are (at most) two such numbers that, when squared, equal $n$ for some $k$, as shown in this question.

-
Multiplication is pretty efficient. Are you sure that you want to find the square of $k$? Maybe you are trying to find the square roots of $n$ modulo $p$, when they exist. – André Nicolas Nov 27 '12 at 0:34
@André Nicolas: I am trying to find the square of a big number, $k$, modulo another big number, $p$. I'm looking into speeding up integer operations for large integers, and I have some ideas on how to speed things up using squares. – Matt Groff Nov 27 '12 at 0:39
Interestingly, in the very old days, there were tables of half squares or quarter squares, and people would find $xy$ by using $(x+y)^2-x^2-y^2$, or $(x+y)^2-(x-y)^2$. – André Nicolas Nov 27 '12 at 0:46
That's sort of an idea that I have. I'm trying to find results of larger multiplications via constructions of squares. I guess there are more efficient routes nowadays, but I am really interested in the approach with squares anyways. I'm trying to match it up with some new techniques. – Matt Groff Nov 27 '12 at 0:52
How fast of an algorithm are you looking for? Standard multiplication, then reduction $\mod p$ will give something like $O(\log^2 p)$ time. Using Karatsuba or Toom-Cook will get that a bit faster, but you can't hope for better than $O(\log p)$. – Michael Biro Nov 27 '12 at 1:10

Converting comment into a proper answer:

In modular arithmetic, Montgomery Multiplication (ref. 2), is a commonly used way to reduce the times one has to do modular reduction (a "mod $n$" operation).
The original paper can be found here.

This applies when many mod $n$ operations are done on the same $n$.
A typical example would be modular exponentiation: $x^k\equiv y(\text{mod }n)$.
This is usually done using a Binary Exponentiation method, involving approximately $log_2(k)$ modular reductions.
In such cases, using Montgomery Multiplication only 1 modular reduction is needed instead.

One may find actual applications in multi-precision libraries like GMP and MPIR.
The function is mpz_powm(), which does an exponentiation modulo $n$.
This is typically referred to as the "Montgomery's REDC" method.

The REDC algorithm requires some precomputation, which is why the method is only beneficial if multiple modular reduction is involved.

In this question, many squarings are done based on the same modulo reduction (mod $p$) and hence this suggestion.

-