![](https://csdnimg.cn/release/download_crawler_static/21076315/bgb.jpg)
The Elliptic Curve Digital Signature Algorithm (ECDSA)
9
1
= (0010)
2
= (0100)
3
= (1000)
4
=(0011)
5
= (0110)
6
= (1100)
7
= (1011)
8
= (0101)
9
=(1010)
10
=(0111)
11
= (1110)
12
= (1111)
13
= (1101)
14
= (1001)
15
=(0001).
Selecting a Reduction Polynomial
.A
trinomial
over
F
2
is a polynomial of the form
x
m
+
x
k
+
1, where 1
k
m
;
1. A
pentanomial
over
F
2
is a p olynomial of the form
x
m
+
x
k
3
+
x
k
2
+
x
k
1
+1,
where 1
k
1
<k
2
<k
3
m
;
1. ANSI X9.62 species the following rules for selecting the reduction
polynomial for representing the elements of
F
2
m
.
1. If there exists an irreducible trinomial of degree
m
over
F
2
, then the reduction polynomial
f
(
x
)must be an irreducible trinomial of degree
m
over
F
2
. To maximize the chances for
interoperability, ANSI X9.62 recommends that the trinomial used should be
x
m
+
x
k
+ 1 for
the smallest possible
k
.
2. If there does not exist an irreducible trinomial of degree
m
over
F
2
, then the reduction
polynomial
f
(
x
)must be an irreducible p entanomial of degree
m
over
F
2
.To maximize the
chances for interoperability, ANSI X9.62 recommends that the pentanomial used should b e
x
m
+
x
k
3
+
x
k
2
+
x
k
1
+1 chosen according to the following criteria:
1
(i)
k
3
is as small as p ossible
(ii) for this particular value of
k
3
,
k
2
is a small as p ossible and (iii) for these particular values
of
k
3
and
k
2
,
k
1
is as small as p ossible.
3.2.2 Normal Basis Representations
Normal Bases
.A
normal basis
of
F
2
m
over
F
2
is a basis of the form
f
2
2
2
:::
2
m
;
1
g
, where
2
F
2
m
. Such a basis always exists. Any element
a
2
F
2
m
can be written as
a
=
P
m
;
1
i
=0
a
i
2
i
,
where
a
i
2f
0
1
g
. Normal basis representations have the computational advantage that squaring an
element can be done very eciently (see Field Op erations below). Multiplying distinct elements,
on the other hand, can be cumbersome in general. For this reason, ANSI X9.62 species that
Gaussian
normal bases b e used, for whichmultiplication is b oth simpler and more ecient.
Gaussian Normal Bases
.The
type
of a GNB is a p ositiveinteger measuring the complexityof
the multiplication operation with resp ect to that basis. Generally speaking the smaller the type,
the more ecient the multiplication. For a given
m
and
T
, the eld
F
2
m
can have at most one
GNB of type
T
.Thus it is prop er to sp eak of
the
type
T
GNB of
F
2
m
. See Mullin et al. 59]and
Ash, Blake and Vanstone 5] for further information on GNBs.
Existence of Gaussian Normal Bases
. A Gaussian normal basis (GNB) exists whenever
m
is not divisible by 8. Let
m
be a positiveinteger not divisible by 8, and let
T
be a positiveinteger.
Then a type
T
GNB for
F
2
m
exists if and only if
p
=
Tm
+ 1 is prime and gcd(
Tm=k m
)= 1,
where
k
is the multiplicative order of 2 mo dulo
p
.
1
Actually, ANSI X9.62 recommends the following criteria for selecting the pentanomial: (i)
k
1
is as small as
possible (ii) for this particular value of
k
1
,
k
2
is a small as possible and (iii) for these particular values of
k
1
and
k
2
,
k
3
is as small as p ossible. However, the ANSI X9F1 committee agreed in April 1999 to change this recommendation
in a forthcoming revision of ANSI X9.62 to the one given ab ove in order to b e consistent with the IEEE P1363 and
FIPS 186-2 recommendations.