Upper Bound of Scalars in the Integer Sub-decomposition Method: The Theoretical Aspects
Ruma Kareem, K. Ajeena · 2015
The focal point of this paper is to present the theoretical aspects of the building blocks of the upper bounds of ISD (integer sub-decomposition) method defined by n C k k 22 21 , max , where 1 C that uses efficiently computable endomorphisms j for 2 , 1 j to compute any multiple kP of a point P of order n lying on an elliptic curve E. The upper bounds of sub-scalars in ISD method are presented and utilized to enhance the rate of successful computation of scalar multiplication kP. Important theorems that establish the upper bounds of the kernel vectors of the ISD reduction map are generalized and proved in this work. The values of C in the upper bounds, that are greater than 1, have been proven in two cases of characteristic polynomials (with degree 1 or 2) of the endomorphisms. The upper bound of ISD method with the case of the endomorphism rings over an integer ring Z results in a higher rate of successful computations kP. Compared to the case of endomorphism rings, which is embedded over an imaginary quadratic field D Q . The determination of the upper bounds is considered as a key point in developing the ISD elliptic scalar multiplication technique.