CRT representation of integers, and multiplication in (almost) linear time

From the section Open Problems in the article Connect the Stars by Kenneth Regan:

Finally, we offer an intriguing open problem about how fast we can multiply integers. It is possible to multiply integers very fast if they are represented via the Chinese Remainder Theorem—though perhaps still not in linear time. Alas while addition and multiplication are fast in this representation, it seems to make it harder to compare two numbers. Thus a natural question is:

Does there exist a representation of integers so that addition, multiplication, and comparison are all doable in linear time? Basically, is there a linear time discretely ordered ring?

I found this very intriguing.

• How can integers be represented via the Chinese Remainder Theorem?
• How can they be multiplied?
-

1 Answer

See the Wikipedia entry on CRT for an introduction.

Essentially, a number is represented in a set of rings, usually by computing modulo a set of primes. See my answer here about representing the numbers and combining them to get the original number.

To multiply a number, simply multiply the residue (which is the number modulo a prime) by another number modulo the same prime, and calculate the remainder modulo the prime. To give a concrete example, we have, for two number $a$ and $b$ to be multiplied together modulo another number $p$, the result $r$ is:

$$((a \bmod p)\cdot(b \bmod p))\bmod p \equiv (a \cdot b) \bmod p$$

Then simply perform this calculate with a sufficient set of $p$s.

NOTES ON LINEAR OPERATIONS

The following is a further illustration of trying to find the ring that K. Regan talks about in his statement. As pointed out by the OP in the comments below, finding the square root may be impossible, as values in RNS for squares are not necessarily unique. Thus we may require some sort of overdetermined system to do so.

We can note that

$$\text{Max}(a,b) = \frac{(a+b) + \sqrt{(a-b)^2}}{2}$$ $$\text{Min}(a,b) = \frac{(a+b) - \sqrt{(a-b)^2}}{2}$$

So if we can determine the square root shown above, we can effectively perform a comparison using the formulas above and responding accordingly.

-
@RealzSlaw: Let us know if you'd like more explanation. I've enjoyed the article and talking with you in the past. – Matt Groff Nov 8 '12 at 3:17
I found the name of this number system, its called the residue number system. As for your comparison scheme, I think it fails because $\sqrt x \mod M$ has many possible answers. If $M$ is prime, then it has two answers, and if $M$ is made of $n$ coprime numbers, then it will have up to $2^n$ possible answers, I think. – Realz Slaw Nov 13 '12 at 21:05
@RealzSlaw: You are correct. I'll remove the error, keeping in mind Regan's and your other question. – Matt Groff Nov 13 '12 at 21:23