43.2 MODULAR ARITHMETIC 275 0 5 u < m and 0 2 u < m, then we can tell if u < u by first doing the conversion to (VI,. . . , v,) and (vi,. . . , v:), then testing if w, < vi, or if v, = vi and q-1 < VI-~, etc. It is not necessary to convert all the way to binary or decimal notation if we only want to know whether (ul, . . . , u,) is less than (u;,...,u;). The operation of comparing two numbers, or of deciding if a modular number is negative, is intuitively very simple, so we would expect to have a much easier method for making this test than the conversion to mixed-radix form. But the following theorem shows that there is little hope of finding a substantially better method, since the range of a modular number depends essentially on all bits of all the residues (~1, . . . , u,): Theorem S (Nicholas Szab6, 1961). In terms of the notation above, assume that ml < fi, and let L be any value in the range ml u, and IJ -u is a multiple of m2 . . . m, = pm/ml, so v 2 TJ -u 2 m/m1 > ml. Therefore, if (28) does not hold for (u, v), it will be satisfied for the pair (u , 2) ) = (v - ml, u + m -ml). 1 Of course, a similar result can be proved for any my in place of ml; and we could also replace (28) by the condition a 2 u < a + L 5 v < a + m with only minor changes in the proof. Therefore Theorem S shows that many simple functions cannot be used to determine the range of a modular number. Let us now reiterate the main points of the discussion in this section: Mod- ular arithmetic can be a significant advantage for applications in which the predominant calculations involve exact multiplication (or raising to a power) of large integers, combined with addition and subtraction, but where there is very little need to divide or compare numbers, or to test whether intermediate results overflow out of range. (It is important not to forget the latter restric- tion; methods are available to test for overflow, as in exercise 12, but they are in general so complicated that they nullify the advantages of modular arith- metic.) Several applications of modular computations have been discussed by H. Takahasi and Y. Ishibashi, Information Proc. in Japan 1 (1961), 28-42.
This entry was posted
on Thursday, December 20th, 2007 at 12:23 am and is filed under J2EE.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.