الفهرس 
Chapter 1 Introduction to Exponentiation AlgorithmsOnly 14 pages are availabe for public view
 |  | from | 108 |  |  |
| | | from | 108 | | |
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.