Return to search

Table Driven Algorithm for Joint Sparse Form

In Cryptography, computing a^xb^y mod n is the most important and the most time-consuming calculation The problem can be solved by classical binary method. Later research is based on this basis to increase computational efficiency. Furthermore, Binary signed-digit representation recoding algorithm, the Sparse Form, the DJM recoding method, and the Joint Sparse Form can be used to decrease the number of multiplication by aligning more non-zero bits. Another method is to pre-compute and store the part of the results to decrease the number of computations by shifting bits. Joint Sparse Form recording method is not a table driven algorithm in converting source codes into joint sparse form. In this paper, we first proposed a table driven algorithm for joint sparse form to simply recording concept. This algorithm can be constructed a finite state machine to denote the recording procedure. According to this finite state machine, we show that the average joint Hamming weight among joint sparse form is 0.5n when n approaches infinity. Finally, we show that the average joint Hamming weights of SS1 method and DS1 method among joint sparse form are 0.469n and 0.438n by using a similar method, respectively.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0825107-171056
Date25 August 2007
CreatorsChen, Bing-hong
ContributorsChun-I Fan, D. J. Guan, Chia-Mei Chen
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageCholon
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0825107-171056
Rightsunrestricted, Copyright information available at source archive

Page generated in 0.0025 seconds