In this section we present an example that uses bigger numbers.
First we prove a proposition that we can use to
choose a prime
in such a way that it is easy to find a
with order
. We have already seen
in Section 2.5 that for every prime
there
exists an element
of order
, and we gave
Algorithm 2.5.16 for finding a primitive
root for any prime. The significance of the proposition
below is that it suggests an algorithm for finding
a primitive root that is easier to use in practice when
is large, because it does not require factoring
.
Of course, one could also just use a random
for Diffie-Hellman; it is not essential that
generates
.
Proposition 3.1
Suppose
is a prime such that
is also prime.
Then the elements of
have order either
,
,
, or
.
Proof.
Since

is prime, the group

has order

. By assumption, the prime
factorization of

is

. Let

. Then by Theorem
2.1.19,

,
so the order of

is a divisor of

, which proves the
proposition.
Given a prime
with
prime, find an element of
order
as follows. If
has order
we are done.
If not,
has order
since
doesn't have order
either
or
. Then
has order
.
Let
.
Then
is prime,
but
is not. So we keep adding
to
and
testing pseudoprimality using algorithms from
Section 2.4
until we find that the next pseudoprime after
is
It turns out that
pseudoprime and
is also pseudoprime.
We find that
has order
, so
has
order
modulo
, and is hence a generator of
,
at least assuming that
is really prime.
The secret
random numbers generated by Nikita and Michael are
and
Nikita sends
to Michael, and Michael sends
to Nikita. They agree on the secret key
SAGE Example 3.1
We illustrate the above computations using SAGE.
sage: q = 93450983094850938450983409623
sage: q.is_prime()
True
sage: is_prime((q-1)//2)
True
sage: g = Mod(-2, q)
sage: g.multiplicative_order()
93450983094850938450983409622
sage: n = 18319922375531859171613379181; m = 82335836243866695680141440300
sage: g^n
45416776270485369791375944998
sage: g^m
15048074151770884271824225393
sage: (g^n)^m
85771409470770521212346739540
sage: (g^m)^n
85771409470770521212346739540
William
2007-06-01