Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We can consider a Residue Number System (R.N.S.) that has efficient operations for add, multiply, and compare between two numbers.

A more rigorous definition

We can suppose that we can perform the operations above between two non-negative integers $x$ and $y$ with $x \ge y$ in time proportional to $O(x\log(x))$ with $O(\log(x^2))$ memory. Or further, if it would possibly allow even more uses, if we could perform these operations in time linear with respect to $x$ and $y$.

What are the potential uses of this system?

For example, cryptology often uses fairly large numbers, and makes use of such a system. Also, linear programming and systems of linear equations can make use of an efficient R.N.S. Also, specialized processors can have R.N.S.'s built in, and could potentially compete with standarized Boolean processors.

What additional uses would this efficient system allow?

share|cite|improve this question
I asked if a system like this potentially exists here:… – Matt Groff Nov 15 '12 at 1:45

Your Answer


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

Browse other questions tagged or ask your own question.