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
.
Search WWH ::




Custom Search