Cryptography Reference
In-Depth Information
the constants are positive. Congruences not in this form can easily be put so by replacing
the values for
a
and
b
with their least nonnegative residues modulo
m
. For example, the
congruence 143
x
11 (mod 121) yields exactly the same set of incongruent solutions as
22
x
110 (mod 121).
E
XAMPLES
.
• Find all incongruent solutions to 9
x
7 (mod 12). Note that (9, 12) = 3, and that 3
7.
Therefore, there are no solutions.
• Find all incongruent solutions to 16
x
12(mod 20). We compute (16, 20) = 4, and note
that 4|12. Thus, 4 incongruent solutions modulo 12 exist. We first find a particular solu-
tion by noting that solving 16
x
12 (mod 20) for
x
is the same as solving the linear dio-
phantine equation 16
x
20
y
= 12. Note that we may just as well solve the equation
16
x
+ 20
y
= 12 because we will discard the value obtained for
y
anyway. We find a par-
ticular solution to be
x
=
x
0
=
3,
y
=
y
0
= 3. The set of all incongruent solutions can be
computed as
x
=
3 + 0
(20/4) =
3
17 (mod 20)
x
=
3 + 1
5
2 (mod 20)
x
=
3 + 2
5
7 (mod 20)
x
=
3 + 3
5
12 (mod 20).
The validity of each of these solutions is easily checked, and you are invited to do so.
Java Algorithm.
Surely you have noticed that solving a linear congruence simply
means solving the appropriate linear diophantine equation. Therefore, writing a solveLin-
earCongruence() method in the BigIntegerMath class should be a snap.
public static BigInteger[] solveLinearCongruence(BigInteger a, BigInteger b,
BigInteger m) {
BigInteger[] answers=solveLinearDiophantine(lnr(a,m),m,lnr(b,m));
return answers;
}
I have written an applet called TestLinearCongruenceApplet which you can run from
the topic's website. Some screen shots are shown in Figures 4.2, 4.3, and 4.4.
Note that if there are multiple solutions, you can repeatedly press the “Next Solution” but-
ton to see the others.
4.3
MODULAR INVERSES
Congruences of the form
ax
1 (mod
m
) are considered special. Solutions for
a
to such con-
gruences are called inverses of
a
, when they exist. The following definition formalizes this
concept.
Search WWH ::
Custom Search