The GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) computes any multiple kP of a point P of prime order n lying on an elliptic curve with a low-degree endomorphism Φ (called GLV curve) over GF(p) as

kP = k_{1}P + k_{2}Φ(P), with
max|k_{1}|,|k_{2}| <= C_{1} n^(1/2)

for some explicit constant C_{1}>0. Recently, Galbraith, Lin and
Scott (EUROCRYPT 2009) extended this method to all curves over GF(p^{2})
which are twists of curves defined over GF(p). We show in this work how to merge
the two approaches in order to get, for twists of any GLV curve over
GF(p^{2}), a four-dimensional decomposition together with fast
endomorphisms Φ, Ψ over GF(p^{2}) acting on the group generated
by a point P of prime order n, resulting in a proven decomposition for any scalar
k ∈ [1,n] given by

kP=k_{1}P+ k_{2}Φ(P)+ k_{3}Ψ(P) +
k_{4}ΨΦ(P), with max_{i} (|k_{i}|)<
C_{2} n^(1/4)

for some explicit C_{2}>0. Remarkably, taking the best
C_{1}, C_{2}, we obtain C_{2}/C_{1}<412,
independently of the curve, ensuring in theory an almost constant relative
speedup. In practice, our experiments reveal that the use of the merged GLV-GLS
approach supports a scalar multiplication that runs up to 1.5 times faster than
the original GLV method. We then improve this performance even further by
exploiting the Twisted Edwards model and show that curves originally slower may
become extremely efficient on this model. In addition, we analyze the performance
of the method on a multicore setting and describe how to efficiently protect
GLV-based scalar multiplication against several side-channel attacks. Our
implementations improve the state-of-the-art performance of scalar multiplication
on elliptic curves over large prime characteristic fields for a variety of
scenarios including side-channel protected and unprotected cases with sequential
and multicore execution.