Cryptography Reference
In-Depth Information
that
nc
|
ac-bc
or
ac = bc mod nc
holds.
This means that we can multiply both sides of a congruence
and
the module
(in this case the number
n
) by the same number. We will utilize this finding
further below.
This subsection of mathematics is called
congruence arithmetic
or
modular
arithmetic
. It works exclusively with integers, which is implicitly understood
in the following.
Not all equations can be solved by this arithmetic. For example,
3x = 1 mod 12
has no integer solution
x
. And not all simple equations can be easily solved.
While
d
can still be computed by
de = 1 mod n
for suitable numbers,
e
and
n
, at a reasonable effort (see below), equations in
the form
a
x
= g mod n
for large numbers are extremely hard to solve for
x
. Without the 'mod
n
'at
the end, we could simply write 'log
a
(g)
', but we are dealing with integers and
remainders here — that's something totally different. Only the name of solution
x
is similar to normal numbers:
x
is the
discrete logarithm
from
g
to base
a
.
We will get back to this in Section 4.5.4.
