박희진
2019-01-17T02:43:14Z
2019-01-17T02:43:14Z
2016-10
JOURNAL OF SEMICONDUCTOR TECHNOLOGY AND SCIENCE, v. 16, NO. 5, Page. 564-581
1598-1657
2233-4866
http://www.dbpia.co.kr/Journal/ArticleDetail/NODE07041139
https://repository.hanyang.ac.kr/handle/20.500.11754/81344
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.
This work was supported by the research fund of Signal Intelligence Research Center supervised by Defense Acquisition Program Administration and Agency for Defense Development of Korea and by the MSIP (Ministry of Science, ICT and Future Planning), Korea, under the ITRC (Information Technology Research Center) support program (IITP-2016-H8501-16-1008)
supervised by the IITP (Institute for Information & communications Technology Promotion).
en
IEEK PUBLICATION CENTER
Performance analysis
digital integrated circuits
prime number
public key cryptosystem
information security
Design and Analysis of Efficient Parallel Hardware Prime Generators
Article
5
16
10.5573/JSTS.2016.16.5.564
564-581
JOURNAL OF SEMICONDUCTOR TECHNOLOGY AND SCIENCE
Kim, Dong Kyue
Choi, Piljoo
Lee, Mun-Kyu
Park, Heejin
2016010716
S
COLLEGE OF ENGINEERING[S]
DEPARTMENT OF COMPUTER SCIENCE
hjpark