2
$\begingroup$

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.

  • 0
    @Yong Hao Ng: This does look promising. I would accept this as an answer if you want to anser the question.2012-11-28

1 Answers 1

3

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.