Cryptography Reference
In-Depth Information
Table 4.1
n
Number of apples
Number of oranges
Total spent (in cents)
-26
183+7(-26)=1
-122-5(-26)=8
35•1+49•8=427
-25
183+7(-25)=8
-122-5(-25)=3
35•8+49•3=427
general solutions to the equation are then
x
= 183 + 7
n
,
y
=
122
5
n ∀
integers
n
. Since
we obviously cannot buy a negative number of apples or oranges, we need to find which of
these solutions are nonnegative. Thus we find that
x
= 183 + 7
n ≥
0, or
n ≥
183/7 =
26 1/7, and
y
=
122
5
n ≥
0, or
n ≤
122/5 =
24 2/5. Thus,
n
can only attain the val-
ues
26, and
25. Each of these values of
n
produces a satisfactory solution to our prob-
lem, which can be seen in the Table 4.1.
Note that with diophantine equations, it is only necessary to solve the equation
ax
+
by
=
c
where
a
,
b
, and
c
are all positive, for if any of these are negative, the solution is still eas-
ily obtained by inverting some of the signs. For example, suppose
x
=
x
and
y
=
y
is a
solution to
ax
+
by
=
c
, where
a
,
b
, and
c
are all positive. Then we have all of the following
in case any one of the constants changes sign.
x
=
x
,
y
=
y
is a solution to
ax
+
by
=
c
,
x
=
x
,
y
=
y
is a solution to
ax
+
by
=
c
, and
x
=
x
,
y
=
y
is a solution to
ax by
=
c
One can easily solve for the other cases when 2 or all 3 of the constants change sign.
More cases to consider are when one of
a
,
b
, or
c
is 0. For these cases we have
x
=
b
,
y
=
a
is a solution to
ax
+
by
= 0
•
x
= 0,
y
=
c
/
b
is a solution to 0
x
+
by
=
c
(provided
b
|
c
)
•
x
=
c
/
a
,
y
= 0 is a solution to
ax
+ 0
y
=
c
(provided
a
|
c
)
•
Java Algorithm.
We now write for the BigIntegerMath class a method to solve linear
diophantine equations
ax
+
by
=
c
. Because of the previous discussion, we will allow only
equations where
a
and
b
are positive, and
c
is nonnegative. You may wish to rewrite the
method to solve equations when any of
a
,
b
, or
c
are negative, or zero. The method will accept
the coefficients
a
and
b
, and the constant
c
as BigIntegers. If
a
or
b
are not positive, or if
c
is negative, it will throw an IllegalArgumentException. It will then compute
d
= (
a
,
b
), and
if
d
c
, it will again throw an IllegalArgumentException. Otherwise, it will compute a par-
ticular solution
x
=
x
,
y
=
y
to the equation, and return it in an array of BigIntegers. The
element at index 1 will be
x
, and
y
will be at index 2. For convenience, the gcd of
a
and
b
will be returned at index 0. This is useful if we want to display the general solution.
public static BigInteger[] solveLinearDiophantine (BigInteger a,
BigInteger b,
Search WWH ::
Custom Search