Cryptography Reference
In-Depth Information
The number-theoretic functions can be tested according to the same
principles as the arithmetic functions. To examine the function to be tested
one is well advised to use inverse functions, equivalent functions, or different
implementations of the same function that are as independent as possible from
one another. We have examples of each of these variants:
•
If the Jacobi symbol indicates that an element of a finite ring is a square,
this can be verified by calculating the square root. Conversely, a calculated
square root can be verified as such by a simple modular squaring.
•
The function
inv()
for calculating the multiplicative inverse
i
of an integer
a
modulo
n
can be tested with the condition
ai
≡
1mod
n
.
•
For calculating the greatest common divisor of two integers one may make
use of the two FLINT/C functions
gcd_l()
and
xgcd_l()
, where the latter
returns the representation of the greatest common divisor as a linear
combination of the arguments. The results can be compared one with the
other, and the linear combination can be constructed, which in turn must
agree with the greatest common divisor.
•
Redundance is also to be found in the relation between the greatest
common divisor and the least common multiple: For integers
a, b
one has
the relation
lcm(
a, b
)=
|ab|
gcd(
a, b
)
,
a fruitful relation that can also easily be checked. Additional useful formulas
that relate the greatest common divisor and least common multiple are
presented in Section 10.1.
•
Finally, the RSA procedure can be invoked for testing the primality test: If
p
or
q
is not prime, then
φ
(
n
)
=(
p −
1)(
q −
1)
. The RSA procedure will work
correctly only if the Fermat test for
p
and
q
states that
p
and
q
are probably
prime. Thus some mutually inverse RSA operations and a comparison of
the decrypted messages with the original messages will certainly reveal
whether the primality test has been implemented correctly.
There are thus sufficiently many and varied approaches to effective testing of
the
LINT
functions. The reader is encouraged to develop and implement at least
one such test for each
LINT
function. It is highly effective both as a test and as an
exercise and will develop in the user of the
LINT
class familiarity with how the
class works and the uses to which it might be put.
