Cryptography Reference
In-Depth Information
F
q
Algorithm 5
Computing a primitive root in
=
i
=
1
l
e
i
INPUT:
q,m,
{
(
l
i
,e
i
)
}
such that
q
−
1
and the
l
i
are distinct primes
i
OUTPUT: primitive root
g
1:
Let
S
={
1
,...,m
}
2:
t
1
3:
while
S
=
= ∅
do
∈ F
q
uniformly at random
Choose
g
4:
g
(
q
−
1)
/l
e
i
i
for 1
Compute
g
i
=
≤
i
≤
m
using Algorithm
4
5:
for
i
∈
S
do
6:
if
g
l
e
i
−
1
=
1
then
i
7:
i
tg
i
9:
Remove
i
from
S
10:
end if
11:
end for
12:
end while
13:
return
t
t
=
8:
2.16 Fast evaluation of polynomials at multiple points
We have seen that one can evaluate a univariate polynomial at a field element efficiently
using Horner's rule. For some applications, for example the attack on small CRT exponents
for RSA in Section
24.5.2
, one must evaluate a fixed polynomial repeatedly at lots of
field elements. Naively repeating Horner's rule
n
times would give a total cost of
n
2
multiplications. This section shows that one can solve this problem more efficiently than
the naive method.
Theorem 2.16.1
Let F
(
x
)
∈ k
[
x
]
have degree n and let x
1
,...,x
n
∈ k
. Then one can
compute
{
F
(
x
1
)
,...,F
(
x
n
)
}
in O
(
M
(
n
)log(
n
))
field operations. The storage requirement
is O
(
n
log(
n
))
elements of
k
.
2
t
.For0
Proof
(Sketch) Let
t
=
log
2
(
n
)
and set
x
i
=
0for
n<i
≤
≤
i
≤
t
and 1
≤
2
t
−
i
define
j
≤
j
2
i
G
i,j
(
x
)
=
(
x
−
x
k
)
.
k
=
(
j
−
1)2
i
+
1
One
computes
the
G
i,j
(
x
)for
i
=
0
,
1
,...,t
using
the
formula
G
i,j
(
x
)
=
G
i
−
1
,
2
j
−
1
(
x
)
G
i
−
1
,
2
j
(
x
). (This is essentially the same trick as Section
2.15.1
.)
Once all the
G
i,j
(
x
) have been computed one defines, for 0
2
t
−
i
the
≤
i
≤
t
,1
≤
j
≤
polynomials
F
i,j
(
x
)
F
(
x
)(mod
G
t,
0
(
x
))
and then computes
F
i,j
(
x
) efficiently as
F
i
+
1
,
(
j
+
1)
/
2
(
x
)(mod
G
i,j
(
x
)) for
i
=
F
(
x
)(mod
G
i,j
(
x
)). One computes
F
t,
0
(
x
)
=
=
t
−
1
downto 0. Note that
F
0
,j
(
x
)
=
F
(
x
)(mod(
x
−
x
j
))
=
F
(
x
j
) as required.
