Cryptography Reference
In-Depth Information
Therefore
f
i
+
j,P
=
f
i,P
g
iP,jP
. This leads to the following algorithm which
computes the Tate pairing [16,17].
·
f
j,P
·
Algorithm 1.
Miller's algorithm.
Input: integer
r
=
i
=0
b
i
2
i
with
b
i
∈{
0
,
1
}
,
b
l
=1
and
P ∈ E
(
F
p
)[
r
]
,Q∈ E
(
F
p
k
)[
r
].
Output:
f
=
f
(
p
k
−
1)
/r
r,P
.
1.
f
←
1,
R
←
P
;
2. for
i
←
l
−
1downto0do
f
2
f
←
·
g
R,R
(
Q
),
R
←
2
R
;
if
b
i
=1then
f
←
f
·
g
R,P
(
Q
),
R
←
R
+
P
;
f
(
p
k
−
1)
/r
.
3. Return
f
←
3
Geometric Interpretation of the Group Law on Hessian
Curves
An elliptic curve in Hessian form is defined by
:
X
3
+
Y
3
+
Z
3
=3
dXY Z,
H
K
with
d
3
where
d
1:1:0).
Thenegativeof(
X
:
Y
:
Z
)is(
Y
:
X
:
Z
). Birational maps between Weierstrass
and Hessian curves can be found in [2]. The addition formulas are given by
(
X
3
:
Y
3
:
Z
3
)=(
X
1
:
Y
1
:
Z
1
)+(
X
2
:
Y
2
:
Z
2
)where
∈
= 1. The identity element is represented by (
−
X
3
=2
Y
1
X
2
Z
2
−
2
X
1
Z
1
Y
2
,
Y
3
=2
X
1
Y
2
Z
2
−
2
Y
1
Z
1
X
2
,
Z
3
=2
Z
1
X
2
Y
2
−
2
X
1
Y
1
Z
2
.
The doubling formulas are given by
2
Y
1
Z
1
)(2
X
1
Z
1
+2(
X
1
+
Z
1
))
,
X
3
=(2
X
1
Y
1
−
2
X
1
Y
1
)(2
Y
1
Z
1
+2(
Y
1
+
Z
1
))
,
Y
3
=(2
X
1
Z
1
−
2
X
1
Z
1
)(2
X
1
Y
1
+2(
X
1
+
Y
1
))
.
Z
3
=(2
Y
1
Z
1
−
Suppose the computational costs of a multiplication, a squaring in the field
K
are denoted by m,s. The point addition algorithms in [7] and [14] require 12m,
while point doubling costs 3m+6s [10].
Theorem 1.
Let
P
1
=(
X
1
:
Y
1
:
Z
1
)
and
P
2
=(
X
2
:
Y
2
:
Z
2
)
be two points on
H
(
K
)
. Define
P
3
=
P
1
+
P
2
.Let
l
1
be the line passing through
P
1
and
P
2
while
l
2
be the line passing through
P
3
and
−
P
3
. Then we have
div
(
l
1
/l
2
)=(
P
1
)+(
P
2
)
−
(
P
3
)
−
(
O
)
.
Search WWH ::
Custom Search