Cryptography Reference
In-Depth Information
“mask out” the required digits
e
i
to base
M
from the representation of
e
to base
B
. For this we set the following: Let
(
ε
r
−
1
ε
r
−
2
...ε
0
)
2
be the representation
of the exponent
e
to base
2
(we need this on account of the number
r
of binary
digits). Let
(
e
u
−
1
e
u
−
2
...e
0
)
B
be the representation of
e
as a CLINT type
to base
B
=2
16
, and let
e
n
−
1
e
n
−
2
...e
0
M
be the representation of
e
to
the base
M
=2
k
,
k ≤
16
(
M
should not be greater than our base
B
). The
representation of
e
in memory as a
CLINT
object
e_l
corresponds to the sequence
[
u
+1]
,
[
e
0
]
,
[
e
1
]
,...,
[
e
u
−
1
]
,
[0]
of
USHORT
values
e_l[i]
for
i
=0
,...,u
+1
;
one should note that we have added a leading zero.
Let
f
:=
r
−
k
, and for
i
=0
,...,f
let
s
i
:=
ki
16
and
d
i
:=
ki
mod 16
.
With these settings the following statements hold:
1.
There are
f
+1
digits in
e
n
−
1
e
n
−
2
...e
0
M
;thatis,
n −
1=
f
.
2.
e
s
i
contains the least-significant bit of the digit
e
i
.
3.
d
i
specifies the position of the least-significant bit of
e
i
in
e
s
i
(counting of
positions begins with 0). If
i<f
and
d
i
>
16
k
, then not all the binary
digits of
e
i
are in
e
s
i
; the remaining (higher-valued) bits of
e
i
are in
e
s
i
+1
.
The desired digit
e
i
thus corresponds to the
k
least-significant binary digits
of
−
e
s
i
+1
B
+
e
s
i
2
d
i
.
Table 6-3. Values for the factorization of the exponent digits into
products of a power of 2 and an odd factor
e
i
tu
e
i
tu
e
i
tu
000
101
211
11
0
11
22
1
11
12
2
3
23
0
23
13
0
13
24
3
3
303
421
14
1
7
25
0
25
15
0
15
26
1
13
505
613
16
4
1
27
0
27
17
0
17
28
2
7
707
831
18
1
9
29
0
29
19
0
19
30
1
15
909
10
20
2
5
31
0
31
1
5
21
0
21