### 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

**eneralized**

*G***on-**

*N***djacent**

*A***orm (G-NAF).**

*F*Scanning the digits from the left-to-right is called

**odified**

*M***eneralized**

*G***igned**

*S***igit**

*D***on-**

*N***djacent**

*A***orm (MGSDNAF), which**

*F*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

Weight

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

#### References

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