Cryptography Reference
In-Depth Information
Z n ,
Z n .If n is prime,
·
is a commutative group that is frequently written as
Z n , and hence
then
Z n \{
0
}
=
Z n \{
0
}
,
·
is a group. Furthermore, the order of
Z n (i.e.,
| Z n |
) is equal to φ ( n ). This means that it can be computed using Euler's
totient function (see Section 3.2.6).
3.3.2
Modular Exponentiation
A frequently used computation in cryptography is modular exponentiation. If, for
example, we want to compute
a b (mod n )
for a
, then the simplest algorithm is to iteratively multiply a
modulo nb times. If b =23, then the following sequence of equations yields the
correct result with 22 modular multiplications:
Z n
and b
N
R n ( a 2 )= R n ( a
·
a )
R n ( a 3 )= R n ( a
R n ( a 2 ))
·
R n ( a 4 )= R n ( a
R n ( a 3 ))
·
...
R n ( a 23 )= R n ( a
R n ( a 22 ))
·
This can be simplified considerably, and the following sequence of equations
yields the correct result but requires only 7 modular multiplications:
R n ( a 2 )= R n ( a
a )
R n ( a 4 )= R n ( R n ( a 2 )
·
R n ( a 2 ))
·
R n ( a 4 ))
R n ( a 10 )= R n ( R n ( a 5 )
R n ( a 5 )= R n ( a
·
R n ( a 5 ))
·
R n ( a 11 )= R n ( a
R n ( a 10 ))
R n ( a 22 )= R n ( R n ( a 11 )
·
R n ( a 11 ))
·
R n ( a 23 )= R n ( a
R n ( a 22 ))
·
Search WWH ::




Custom Search