Cryptography Reference
In-Depth Information
Example 2.15.2
Let
N
=
N
1
N
2
N
3
N
4
and suppose one needs to compute
g
N
1
N
2
N
3
,g
N
1
N
2
N
4
,g
N
1
N
3
N
4
,g
N
2
N
3
N
4
.
We first compute
g
N
3
N
4
g
N
1
N
2
h
1
,
1
=
and
h
1
,
2
=
in
≤
2(log
2
(
N
1
N
2
)
+
log
2
(
N
3
N
4
))
=
2log
2
(
N
) operations. One can then compute the result
g
N
1
N
2
N
3
h
N
3
1
,
2
,g
N
1
N
2
N
4
h
N
4
1
,
2
,g
N
1
N
3
N
4
h
N
1
1
,
1
,g
N
2
N
3
N
4
h
N
2
=
=
=
=
1
,
1
.
This final step requires at most 2(log
2
(
N
3
)
+
log
2
(
N
4
)
+
log
2
(
N
1
)
+
log
2
(
N
2
))
=
2log
2
(
N
)
operations. The total complexity is at most 4 log
2
(
N
) operations in the group.
The algorithm has a compact recursive description. Let
F
be the function that on input
(
g,m,N
1
,...,N
m
) outputs the list of
m
values
g
N/N
i
for 1
≤
i
≤
m
where
N
=
N
1
···
N
m
.
Then
F
(
g,
1
,N
1
)
=
g
.For
m>
1 one computes
F
(
g,m,N
1
,...,N
m
)asfollows:Let
g
N
1
···
N
l
and
h
2
=
g
N
l
+
1
···
N
m
. Then
F
(
g,m,N
1
,...,N
m
) is equal to
l
=
m/
2
and let
h
1
=
the concatenation of
F
(
h
1
,
(
m
l
)
,N
l
+
1
,...,N
m
) and
F
(
h
2
,l,N
1
,...,N
l
).
We introduce some notation to express the algorithm in a non-recursive format.
−
1
,
2
,...,
2
k
2
l
define
Definition 2.15.3
Define
S
={
}
.For1
≤
l
≤
k
and 1
≤
j
≤
1)2
k
−
l
j
2
k
−
l
S
l,j
={
i
∈
S
:(
j
−
+
1
≤
i
≤
}
.
2
l
. The sets S
l,j
satisfy:
Lemma 2.15.4
Let
1
≤
l
≤
k and
1
≤
j
≤
2
k
−
l
;
1.
#
S
l,j
=
j
;
2. S
l,j
∩
S
l,j
= ∅
if j
=
2
l
j
3.
∪
1
S
l,j
=
S for all
1
≤
l
≤
k;
=
2
l
−
1
4. If l
≥
2
and
1
≤
j
≤
then S
l
−
1
,j
=
S
l,
2
j
−
1
∪
S
l,
2
j
;
2
k
.
5. S
k,j
={
j
}
for
1
≤
j
≤
Exercise 2.15.5
Prove Lemma
2.15.4
.
2
l
define
Definition 2.15.6
For 1
≤
l
≤
k
and 1
≤
j
≤
g
j
∈
S
−
S
l,j
N
i
.
h
l,j
=
2
l
then
To compute
{
h
k,j
:1
≤
j
≤
m
}
efficiently, one notes that if
l
≥
2 and 1
≤
j
≤
writing
j
1
=
j/
2
h
i
∈
S
l
−
1
,j
1
−
S
l,j
N
i
l
−
1
,j
1
h
l,j
=
.
This leads to Algorithm
4
.
