Cryptography Reference
In-Depth Information
TABLE 16.3
i
C
is congruent to
R
i
modulo
p
i
499
1
47141263
234
503
2
47141263
103
563
3
47141263
147
We compute the difference
D
= 103
201 =
98
and form the modified sum
C
74111215 + 98327950
(
98)
9562027885
47141263 (mod 141311311).
To verify that this works see Table 16.3, in which we have once again recovered the 3
records.
16.3
LARGE INTEGER ARITHMETIC
CRT provides us with a particularly novel way to do arithmetic with very large nonnega-
tive integers. We usually represent numbers using a single radix, like
10
3
+ 2
10
2
+ 3
10
1
+ 1
10
0
4231 = 4
or
2
5
+ 0
2
4
+ 0
2
3
+ 0
2
2
+ 1
2
1
+ 1
2
0
.
100011
base 2
= 1
The Chinese Remainder Theorem tells us that the representation of an integer
x
such that
x
a
1
(mod
m
1
)
x
a
2
(mod
m
2
)
x
a
n
(mod
m
n
),
where the moduli are pairwise relatively prime, is unique modulo
M
=
m
1
m
2
...
m
n
. Thus,
we can either represent
in its “composed” representation, or in its “decomposed” repre-
sentation. Using multiple moduli to represent an integer in this way is called a mixed radix
system, or a residue number system.
x
Search WWH ::
Custom Search