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?