Cryptography Reference
In-Depth Information
1.
Precomputations
The representation of the exponent
e
= 667
can be expressed to the base
2
k
with
k
=2
(cf. the algorithm for
M
-ary exponentiation on page 89),
whereby the exponent
e
has the representation
e
= (10 10 01 10 11)
2
2
.
The power
a
3
mod 18577
has the value
17354
. Further powers of
a
do not
arise in the precomputation because of the small size of the exponent.
2.
Exponentiation loop
exponent digit
e
i
=2
t
u
2
1
2
1
2
0
2
1
2
0
·
1
·
1
·
1
·
1
·
3
p ← p
2
mod
n
-
14132
13261
17616
13599
p
2
2
mod
n
p
←
-
-
4239
-
17343
pa
u
mod
n
p
←
1234
13662
10789
3054
4445
p
2
mod
n
p
←
18019
7125
-
1262
-
3.
Result
p
= 1234
667
mod 18577 = 4445
.
As an extension to the general case we shall introduce a special version
of exponentiation with a power of two
2
k
as exponent. From the above
considerations we know that this function can be implemented very easily by
means of
k
-fold exponentiation. The exponent
2
k
will be specified by
k
.
Function:
modular exponentiation with exponent a power of 2
int mexp2_l (CLINT a_l, USHORT k, CLINT p_l,
CLINT m_l);
Syntax:
a_l
(base)
k
(exponent of 2)
m_l
(modulus)
Input:
p_l
(residue of
a_l
2
k
mod
m_l)
Output:
E_CLINT_OK
if all is ok
E_CLINT_DBZ
if division by 0
Return:
int
mexp2_l (CLINT a_l, USHORT k, CLINT p_l, CLINT m_l)
{
CLINT tmp_l;
if (EQZ_L (m_l))
{
return E_CLINT_DBZ;
}
