65 0

Design and Analysis of Efficient Parallel Hardware Prime Generators

Title
Design and Analysis of Efficient Parallel Hardware Prime Generators
Author
박희진
Keywords
Performance analysis; digital integrated circuits; prime number; public key cryptosystem; information security
Issue Date
2016-10
Publisher
IEEK PUBLICATION CENTER
Citation
JOURNAL OF SEMICONDUCTOR TECHNOLOGY AND SCIENCE, v. 16, NO. 5, Page. 564-581
Abstract
We present an efficient hardware prime generator that generates a prime p by combining trial division and Fermat test in parallel. Since the execution time of this parallel combination is greatly influenced by the number k of the smallest odd primes used in the trial division, it is important to determine the optimal k to create the fastest parallel combination. We present probabilistic analysis to determine the optimal k and to estimate the expected running time for the parallel combination. Our analysis is conducted in two stages. First, we roughly narrow the range of optimal k by using the expected values for the random variables used in the analysis. Second, we precisely determine the optimal k by using the exact probability distribution of the random variables. Our experiments show that the optimal k and the expected running time determined by our analysis are precise and accurate. Furthermore, we generalize our analysis and propose a guideline for a designer of a hardware prime generator to determine the optimal k by simply calculating the ratio of M to D, where M and D are the measured running times of a modular multiplication and an integer division, respectively.
URI
http://www.dbpia.co.kr/Journal/ArticleDetail/NODE07041139http://repository.hanyang.ac.kr/handle/20.500.11754/81344
ISSN
1598-1657; 2233-4866
DOI
10.5573/JSTS.2016.16.5.564
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE