Cryptography Reference
In-Depth Information
π
+
e
=
e
π
+
π
=
π
e
+
e
=
π
π
π = 0
π e
=
π
e e
=
e
Here, essentially,
π
is the additive identity (like 0), and
e
is the multiplicative identity (like 1).
Normally, however, we usually have a set of integers to work on, like {0, 1, ... ,
n
- 1}, with normal integer
addition and multiplication, but modulo
n
to reduce everything back to the finite field.
However, not every value of
n
works very well, at least with normal addition and multiplication (taken mod-
ulo
n).
If we have the set {0, 1, 2, 3, 4, 5} (often abbreviated as
6
), then it is difficult to find multiplicative
inverses of every number. Only when the number
n
is prime do we find nice, easy-to-work-with numbers. We
can also work with
n
=
p
m
,where
p
is a prime and
m
is a positive integer, but the math gets a little ugly and
complicated in explaining how it works, so we won't go into it here.
As a short example of finite fields, we can check to see if (
7
, +, ×) satisfies the desired properties. Since
normal addition and multiplication modulo 7 will work as expected, then the only thing to check is to make sure
that we have multiplicative inverses for everything but 0. It should be easy to verify that
1 × 1 = 1 (mod 7)
2 × 4 = 1 (mod 7)
3 × 5 = 1 (mod 7)
Therefore, all of the elements, except for 0, have multiplicative inverses, thus we indeed have a finite field.
Finitefieldsarealsocalled
Galoisfields,
andtheprimaryintegerGaloisfieldsareoftenabbreviatedas
GF
(
n
)
= ({0, 1, ... ,
n
- 1{, +, ×), where
n
is an integer.
2.3.2 Finite Field Inverses
We have glossed over one last detail: how to calculate the multiplicative inverse in a finite field, say, (
p
, +, ×)
? It turns out that there is a simple algorithm for calculating this — the
Euclidean algorithm.
This algorithm
wasn't made to solve for these numbers, as Euclid lived long before finite fields were conceived, but is instead
an algorithm to compute the greatest common divisor of two integers. In our case, we will use the Euclidean
algorithm to calculate the GCD of
p
and the number we wish to find the inverse of, say
a
. We should note that
the GCD should be 1, since
p
is supposedly prime.
Let's define our goal a little more clearly before we get into the nitty gritty algorithm itself. The multiplicat-
ive inverse of
a
will be some number
a
-1
such that
a
×
a
-1
≡ 1 (mod
p
)
Or, if we rewrite this in terms of normal integer operations, using the previous definition of equivalence,
a
× a
-1
= 1 +
kp
where
k
is some other integer.
Search WWH ::
Custom Search