Cryptography Reference
In-Depth Information
g,g
p
are the roots of the equation
x
2
Let
g
∈
G
. Then the elements of [
g
]
={
}
−
tx
+
1
g
p
∈ F
p
such that the roots of
x
2
in
F
p
2
where
t
=
g
+
∈ F
p
. Conversely, each
t
−
tx
+
1
are Galois conjugates corresponds to a class [
g
] (the values
t
=±
2 correspond to [1] and
[
1]). Hence, one can represent an element of
G/ψ
by the trace
t
. We therefore require
half the storage compared with the standard representation of
G
−
⊂ F
p
2
.
In Section
6.3.2
we show that, given the trace
t
of
g
, one can compute the trace
t
n
of
g
n
efficiently using Lucas sequences (though there is a slight catch, namely that we have to
work with a pair (
t
n
,t
n
−
1
) of traces).
Another important example of an algebraic group quotient is elliptic curve arithmetic
using
x
-coordinates only. This is the quotient of an elliptic curve by the equivalence relation
P
≡−
P
.
4.4 Algebraic groups over rings
Algebraic geometry is traditionally studied over fields. However, several applications (both
algorithmic and cryptographic) will exploit algebraic groups or algebraic group quotients
over
Z
/N
Z
(we do not consider general rings).
=
i
=
1
p
i
be square-free (the non-square-free case is often more subtle). By the
Chinese remainder theorem,
Let
N
i
denotes
the direct sum of rings). Hence, if
G
is an algebraic group then it is natural to define
Z
/N
Z
is isomorphic as a ring to
⊕
F
p
i
(where
⊕
=
1
k
Z
Z
=
F
p
i
)
G
(
/N
)
G
(
(4.1)
i
=
1
(where
⊕
now denotes the direct sum of groups). A problem is that this representation for
G
(
) does not satisfy the natural generalisation to rings of our informal definition of
an algebraic group. For example, group elements are not
n
-tuples over the ring, but over a
collection of different fields. Also the value
n
is no longer bounded.
The challenge is to find a representation for
G
(
Z
/N
Z
Z
and satisfies the other properties of the informal definition. Example
4.4.1
shows that this
holds for the additive and multiplicative groups.
Z
/N
Z
) that uses
n
-tuples over
Z
/N
=
i
p
i
where the
p
i
are distinct primes. Then, using the definition
Example 4.4.1
Let
N
in equation (
4.1
),
)
=
F
p
i
)
=
F
p
i
=
Z
G
a
(
Z
/N
Z
G
a
(
/N
Z
.
i
i
Similarly
i
F
p
i
=
)
=
F
p
i
)
=
)
∗
.
G
m
(
Z
/N
Z
G
m
(
(
Z
/N
Z
i
Hence, both groups can naturally be considered as algebraic groups over
Z
/N
Z
.