Cryptography Reference
In-Depth Information
n
−
1
mod 2
s
for
s>
0
,
n
odd
−
Algorithm for calculating the inverse
1.
Set
x
←
2
,
y
←
1
,and
i
←
2
.
2.
If
x<ny
mod
x
, set
y
←
y
+
x
.
3.
Set
x
←
2
x
and
i
←
i
+1
;if
i
≤
s
, go to step 2.
4.
Output
x − y
.
With complete induction it can be shown that in step 2 of this algorithm
yn ≡
1mod
x
always holds, and thus
y ≡ n
−
1
mod
x
. After
x
has taken on the
value
2
s
in step 3, we obtain with
2
s
− y ≡−n
−
1
mod 2
s
the desired result if we
choose
s
such that
2
s
=
B
. The short function for this can be obtained under the
name
invmon_l()
in the FLINT/C source. It takes only the modulus
n
as argument
and outputs the value
n
−
1
mod
B
.
These considerations are borne out in the creation of the functions
mexp5m_l()
and
mexpkm_l()
, for which we give here only the interface, together
with a computational example.
−
Function:
modular exponentiation with odd modulus
(
2
5
-ary or
2
k
-ary method with Montgomery product)
int mexp5m_l (CLINT bas_l, CLINT exp_l,
CLINT p_l, CLINT m_l);
int mexpkm_l (CLINT bas_l, CLINT exp_l,
CLINT p_l, CLINT m_l);
Syntax:
bas_l
(base)
exp_l
(exponent)
m_l
(modulus)
Input:
p_l
(power residue)
Output:
E_CLINT_OK
if all is ok
E_CLINT_DBZ
if division by 0
E_CLINT_MAL
if
malloc()
error
E_CLINT_MOD
if even modulus
Return:
These functions employ the routines
invmon_l()
,
mulmon_l()
,and
sqrmon_l()
to compute the Montgomery products. Their implementation is based on the
functions
mexp5_l()
and
mexpk_l()
modified according to the exponentiation
algorithm described above.
We would like to reconstruct the processes of Montgomery exponentiation
in
mexpkm_l()
with the same numerical example that we looked at for
M
-ary
