Cryptography Reference
In-Depth Information
we do not abandon the residue system
R
(
r, n
)=
}
introduced above. This process yields us both the function
wmexpm_l()
and the
dual function
umexpm_l()
for
USHORT
exponents, respectively for odd moduli,
which in comparison to the two conventional functions
wmexp_l()
and
umexp_l()
again yields a significant speed advantage. For these functions, too, we present
here only the interface and a numerical example. The reader is again referred to
the FLINT/C source for details.
{
ir
mod
n
|
0
≤
i<n
Function:
modular exponentiation with Montgomery reduction
for USHORT-base, respectively
USHORT
exponents
and odd modulus
int wmexpm_l (USHORT bas, CLINT e_l,
CLINT p_l, CLINT m_l);
int umexpm_l (CLINT bas_l, USHORT e,
CLINT p_l, CLINT m_l);
Syntax:
bas, bas_l
(base)
e, e_l
(exponent)
m_l
(modulus)
Input:
p_l
(residue of
bas
e_l
mod
m_l
, resp.
bas_l
e
mod
m_l)
Output:
Return:
E_CLINT_OK if all is ok
E_CLINT_DBZ
if division by 0
E_CLINT_MOD
if even modulus
The function
wmexpm_l()
is tailor-made for our primality test in Section 10.5,
where we shall profit from our present efforts. The function will be documented
with the example used previously of the calculation of
1234
667
mod 18577
.
1.
Precalculations
The binary representation of the exponent is
e
= (1010011011)
2
.
The value
r
for the Montgomery reduction is
r
=2
16
=
B
= 65536
.
The value
n
0
(cf. page 110) is calculated as above, yielding
n
0
= 34703
.
The initial value of
p
is set as
p ← pr
mod 18577
.
2.
Exponentiation loop
Ex
po
ne
nt bit
1
0
1
0
0
1
1
0
1
1
p
←
p
×
p
in
R
(
r, n
)
9805
9025
16994
11105
3682
6646
14511
1628
11066
9350
p
←
pa
mod
n
5743
-
15740
-
-
8707
16923
-
1349
1583
3.
Result
The value of the exponent
p
after normalization:
p
=
p ×
1=
pr
−
1
mod
n
= 1583
r
−
1
mod
n
= 4445
.
