Could you think of a way to simplify the calculation? (Modular arithmetic)?

2008-07-17 1:00 am

With the following three congruences,

x≡12(mod31)
x≡87(mod127)
x≡91(mod255)

We can use the chinese remainder theorem to find x,
However, one of the steps involve calculate the product of the moduli like this:

M=31*127*255=1003935

As you can seen, such a large number can quick complicate any further calculation, so, can you think of a way to simplify these three congruences so that the x can be more easily solved?

Thanks in advance.

回答 (1)

simplicitus

2008-07-19 7:16 am

✔ 最佳答案

You never have to compute the product of all three, only the three products of 31, 127, and 255 taken two at a time.

The result is a value k such that all the solutions have the form k mod M, but if you are only interested in one solution, k is it.
http://en.wikipedia.org/wiki/Chinese_remainder_theorem

But, in fact, you are right. Going from the modular form to the "integer" form is painful. But modular arithmetic can be executed much faster than ordinary integer arithmetic, so if you need computation speed, you use it and convert to integer form as rarely as possible.
http://en.wikipedia.org/wiki/Residue_number_system
http://en.wikipedia.org/wiki/Modular_arithmetic

👍 0 👎 0