Cryptography Reference
In-Depth Information
modulo
n
(where
n
is a natural positive number), written as
a=bdnra
≡
b mod n
if
a
and
b
leave the same remainder when divided by
n
. The equivalent is that
(
a
−
b
) is not divisible by
n
without remainder, which can be written like this:
n
|
a-b
We can do arithmetic with such congruencies similarly to equations, e.g., we
can add or multiply them:
a = b mod n
and
c = d mod n
are followed by
a+c = b+d mod n
ac = bc mod n
and
ac = bd mod n
In particular, the last equation results in
a
k
=b
k
mod n
for every natural number,
k
.
Finally, we conclude from
a = b mod n
(i.e., n
|
a-b)
