Cryptography Reference
In-Depth Information
Algorithm 4 Computing set of exponentials of products
INPUT: N 1 ,...,N m
OUTPUT:
g N/N i :1
{
i
m
}
1: k
=
log 2 ( m )
g N 2 k 1 + 1 ··· N 2 k , h 1 , 2 =
g N 1 ··· N 2 k 1
2: h 1 , 1 =
3: for l
=
2to k do
1to2 l do
for j
=
4:
j 1 =
j/ 2
5:
h i S l 1 ,j 1 S l,j N i
l 1 ,j 1
h l,j =
6:
7: end for
8: end for
9: return
{
h k, 1 ,...,h k,m }
Lemma 2.15.7 Algorithm 4 is correct and requires
2
log 2 ( m )
log( N ) group operations.
Proof Almost everything is left as an exercise. The important observation is that lines 4 to
7 involve raising to the power N i for all i
S . Hence, the cost for each iteration of the loop
in line 3 is at most 2 2 k
i = 1 log 2 ( N i )
=
2log 2 ( N ).
This method works efficiently in all cases (i.e., it does not require m to be large).
However, Exercise 2.15.8 shows that for small values of m there may be more efficient
solutions.
Exercise 2.15.8 Let N = N 1 N 2 N 3 where N i
N 1 / 3
for 1
i
3. One can compute
g N/N i
3 using Algorithm 4 or in the “naive” way. Suppose one uses the
standard square-and-multiply method for exponentiation and assume that each of N 1 ,N 2
and N 3 has Hamming weight about half their bit-length.
Note that the exponentiations in the naive solution are all with respect to the fixed base g .
A simple optimisation is therefore to precompute all g 2 j for 1
for 1
i
log 2 ( N 2 / 3 ). Determine
the number of group operations for each algorithm if this optimisation is performed. Which
is better?
j
Remark 2.15.9 Sutherland gives an improved algorithm (which he calls the snowball
algorithm ) as Algorithm 7.4 of [ 536 ]. Proposition 7.3 of [ 536 ] states that the complexity
is
O (log( N ) log( m ) / log(log( m )))
(2.6)
group operations.
 
Search WWH ::




Custom Search