SPEEDING UP EXPONENTIATION ALGORITHMS FOR PUBLIC-KEY CRYPTOSYSTEMS

Abstract

Generating a shortest addition chain (AC) for a positive integer e plays an important role in speeding up exponentiation pe mod m, p ∈ Zm, when e is fixed. This thesis aims at speeding up the generation of short- est AC using graphics processing unit (GPU).

We introduce the first GPU-based algorithm to generate a shortest addition chain for e. The main idea of the proposed algorithm is to di- vide the search tree into a sequence of three subtrees: top, middle, and bottom. The top subtree works using a branch and bound depth first strategy. The middle subtree works using a branch and bound breadth first strategy, while the bottom subtree works using a GPU branch and bound depth first strategy. Our experimental results show that 1. Compared to the fastest sequential algorithm for generating a short- est addition chain, we improve the generation of a shortest addition chain by about 70% using single GPU (NVIDIA GeForce GTX 770) and about 80% using single GPU (NVIDIA GeForce GTX 1060) . 2. Compared to multicore algorithm to generate shortest AC, we im- prove the generation by about 50%. 3. For generating all shortest addition chains, the percentage of the improvement, compared to the sequential algorithm, is about 50% using GTX 770.