Vol 8, No 3 (2017) > Electrical, Electronics and Computer Engineering >

New Modified Left-to-right Radix-R Representation for Integers

Arash Eghdamian, Azman Samsudin


Abstract: This research addresses
the problem of finding a minimum Hamming Weight by proposing a left-to-right recoding of integers (from the most
significant bit to the less significant one). This representation is the
enhanced and modified version of a well-known recoding method called Generalized
Non-Adjacent Form (G-NAF).
Scanning the digits from the left-to-right is called Modified Generalized Signed
Digit Non-Adjacent Form (MGSDNAF), which
unlike the G-NAF,
presents the ‘nice
property’ to be
obtained. A ‘nice property’ is one that is based on
intuition and is  particularly desirable
to be obtained in a given context. This
processing direction is of great importance because a table of pre-computed
values may be used to speed up the scalar multiplication only for that
direction. A subsequent advantage is that recoding the exponent in advance is
not required. This results in better performances in both running time and
memory space. This representation method can reduce the Hamming Weight of
integers from about 21.6% for radix 3 to 15.1% for radix 9. These numbers for G-NAF
recoding are 16.7% and 8.9% respectively. Comparing these numbers together
shows that efficiency of the proposed method in reducing the Hamming
is more than the efficiency of G-NAF, which is from 30% (for radix 3) to more than
65% (for radix 9) more efficient in reducing the Hamming Weight. Finally, two radix 3 single scalar multiplication
methods for Elliptic
Curve Cryptography (ECC),
which are based on G-NAF and Left-to-Right MGSDNAF, are compared in order to examine the
application of the proposed method in cryptography. The results show that the
proposed method can reduce the number of underlying arithmetic operations in
single scalar multiplication by 14.1% while G-NAF can only reduce this number by 11.5%.
Keywords: Cryptography; Elliptic curve; Generalized NAF (G-NAF); Hamming weight; Radix-r representation

Full PDF Download


Ciet, M., Joye, M., Lauter, K., Montgomery, P.L., 2006. Trading Inversions for Multiplications in Elliptic Curve Cryptography. Designs, Codes, and Cryptography, Volume 39(2), pp. 189–206

Clark, W., Liang, J., 1973. On Arithmetic Weight for a General Radix Representation of Integers. IEEE Transactions on Information Theory, Volume 19, pp. 823–826

Eghdamian, A., Samsudin, A., 2015a. A Modified Left-to-right Radix-r Representation. In: 2015 International Symposium on Technology Management and Emerging Technologies (ISTMET), pp. 254–257

Eghdamian, A., Samsudin, A., 2014. An Improved Signed Digit Representation of Integers. In: 3rd International Conference on Computer Engineering & Mathematical Sciences, pp. 287–290

Eghdamian, A., Samsudin, A., 2015b. MGSDNAF - A Modified Signed Digit Generalized Non- Adjacent Form for Integers Representation. In: 2nd Advancement on Information Technology International Conference (ADVCIT)

Eisentrager, K., Lauter, K., Montgomery, P., 2003. Fast Elliptic Curve Arithmetic and Improved Weil Pairing Evaluation. Topics in Cryptology—CT-RSA 2003, pp. 343–354

ElGamal, T., 1985. A Public Key Cryptosystem and a Signature Scheme based on Discrete Logarithms. IEEE Transactions on Information Theory, Volume 31(4), pp. 469–472

Fong, K., Hankerson, D., Lopez, J., Menezes, A., 2004. Field Inversion and Point Halving Revisited. IEEE Transactions on Computers, Volume 53(8), pp. 1047–1059

Hankerson, D., Hernandez, J.L., Menezes, A., 2000. Software Implementation of Elliptic Curve Cryptography over Binary Fields (Invited Talk). In: Cryptographic Hardware and Embedded Systems, Springer, pp. 1–24

Joye, M., Yen, S.M., 2002. New Minimal Modified Radix-r Representation with Applications to Smart Cards. In: Naccache D., Paillier P. (eds) Public Key Cryptography. Lecture Notes in Computer Science, Volume 2274, pp. 375–383. Springer, Berlin, Heidelberg

Joye, M., Yen, S.M., 2000. Optimal Left-to-right Binary Signed-digit Recoding. IEEE Transactions on Computers, Volume 49(7), pp. 740–748

Koc, C.K., 1994. High-speed RSA Implementation. Technical Report, RSA Labratories, November

Menezes, A., Oorschot, P., Van & Vanstone, S., 1997. Handbook of Applied Cryptography, CRC Press

Morain, F., Olivos, J., 1990. Speeding Up the Computations on an Elliptic Curve using Addition-subtraction Chains. Informatique théorique et Applications, Volume 24(6), pp. 531–543

Muir, J.A., 2007. A Simple Left-to-right Algorithm for Minimal Weight Signed Radix-r Representations. IEEE Transactions on Information Theory, Volume 53(3), pp. 1234–1241

Rivest, R., Shamir, A., Adleman, L., 1978. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Volume 21(2), pp. 120–126