Calculating Average Joint Hamming Weight for Minimal Weight Conversion of d Integers

摘要

In this paper, we propose an algorithm to calculate the efficiency of number representations in elliptic curve cryptography, average joint Hamming weight. The method uses Markov chains generated from a minimal weight conversion algorithm of d integers using the minimal weight conversion. With redundant representations using digit sets like {0, ±1}, it is possible to reduce computation time of the cryptosystem. Although larger digit sets make the computation time shorter, it requires longer preprocessing time. Therefore, the average joint Hamming weight is useful to evaluate digit sets. The Markov chains to find the average joint Hamming weight are derived automatically from the conversions. However, the number of states in these Markov chains is generally infinite. In [8], we propose an algorithm to reduce the number of states, but it is still unclear which representations the method can be applied for. In this paper, the finiteness of Markov chain with the existence of a stationary distribution is proven in a class of representation whose digit set D_s be a finite set such that there exists a natural number A where D_s (⊂) {0, ±1,…, ±Λ} and {0, ±1, ±Λ} (⊂) D_s. The class covers most of the representation practically used in elliptic curve cryptography such as the representation which digit set are {0, ±1} and {0, ±1,±3}.