Cryptography Reference
In-Depth Information
Table 13-1. Group law for the integers to help in testing
Addition
Multiplication
Identity
a
+0=
a
a
·
1=
a
Commutative Law
a
+
b
=
b
+
a
a · b
=
b · a
Associative Law
(
a
+
b
)+
c
=
a
+(
b
+
c
)
a
·
b
)
·
c
=
a
·
(
b
·
c
)
Addition and multiplication can be tested one against the other by making
use of the definition
k
ka
:=
a,
j
=1
at least for small values of
k
. Further relations amenable to testing are the
distributive law and the first binomial formula:
Distributive law
:
a ·
(
b
+
c
)=
a · b
+
a · c,
(
a
+
b
)
2
=
a
2
+2
ab
+
b
2
.
Binomial formula
:
The cancellation laws for addition and multiplication provide the following
test possibilities for addition and subtraction, as well as for multiplication and
division:
a
+
b
=
c
⇒
c
−
a
=
b
and
c
−
b
=
a
and
a · b
=
c ⇒ c ÷ a
=
b
and
c ÷ b
=
a.
Division with remainder can be tested against multiplication and addition by
using the division function to compute, for a dividend
a
and divisor
b
, first the
quotient
q
and remainder
r
. Then multiplication and addition are brought into
play to test whether
a
=
b
·
q
+
r.
For testing modular exponentiation against multiplication for small
k
we fall
back on the definition:
k
a
k
:=
a.
i
=1
From here we can move on to the exponentiation laws (cf. Chapter 1)
a
rs
=(
a
r
)
s
,
a
r
+
s
=
a
r
· a
s
,
which are likewise a basis for testing exponentiation in relation to multiplication
and addition.
