IJPAM: Volume 87, No. 1 (2013)
USING INTEGER SUB-DECOMPOSITION METHOD



University Sains Malaysia
11800 USM, Penang, MALAYSIA
Abstract. This study proposes a new approach called, integer sub-decomposition (ISD), to compute any multiple of a point
of order
lying on an elliptic curve. Our method depends, in computations, on fast endomorphisms
and
of elliptic curve over prime fields. The integer sub-decomposition to multiple
, when the value of
is decomposed into two values
and
, where both values or one of them is not bounded by
, is illustrated in the following formula:
where
. The integers
and
are computed by solving a closest vector problem in lattice. Consequently, as for this sub-decomposition, we have managed to increase the percentage of a successful computation of
.
Moreover, the gap in the proof of the bound of kernel
vectors of the reduction map
on ISD method will be filled through the analysis of the multiplier
, using two fast endomorphisms with minimal polynomials
for
.
In particular, we prove an integer sub-decomposition (ISD) with explicit constant

with

Received: May 3, 2013
AMS Subject Classification: 06-xx, 18B35, 06Bxx, 03G10
Key Words and Phrases: elliptic curves, fast performance, efficiently-computable endomorphisms, integer sub-decomposition
Download paper from here.
DOI: 10.12732/ijpam.v87i1.5 How to cite this paper?
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2013
Volume: 87
Issue: 1