Design and analysis of efficient parallel hardware prime generators

Dong Kyue Kim, Piljoo Choi, Mun Kyu Lee, Heejin Park

Research output: Contribution to journalArticle

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.

Original languageEnglish
Pages (from-to)564-581
Number of pages18
JournalJournal of Semiconductor Technology and Science
Volume16
Issue number5
DOIs
StatePublished - 2016 Oct 1

Fingerprint

Random variables
Hardware
Probability distributions
Experiments

Keywords

  • Digital integrated circuits
  • Information security
  • Performance analysis
  • Prime number
  • Public key cryptosystem

Cite this

@article{38de319d7db14a81aa750c6319a70c11,
title = "Design and analysis of efficient parallel hardware prime generators",
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.",
keywords = "Digital integrated circuits, Information security, Performance analysis, Prime number, Public key cryptosystem",
author = "Kim, {Dong Kyue} and Piljoo Choi and Lee, {Mun Kyu} and Heejin Park",
year = "2016",
month = "10",
day = "1",
doi = "10.5573/JSTS.2016.16.5.564",
language = "English",
volume = "16",
pages = "564--581",
journal = "Journal of Semiconductor Technology and Science",
issn = "1598-1657",
number = "5",

}

Design and analysis of efficient parallel hardware prime generators. / Kim, Dong Kyue; Choi, Piljoo; Lee, Mun Kyu; Park, Heejin.

In: Journal of Semiconductor Technology and Science, Vol. 16, No. 5, 01.10.2016, p. 564-581.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Design and analysis of efficient parallel hardware prime generators

AU - Kim, Dong Kyue

AU - Choi, Piljoo

AU - Lee, Mun Kyu

AU - Park, Heejin

PY - 2016/10/1

Y1 - 2016/10/1

N2 - 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.

AB - 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.

KW - Digital integrated circuits

KW - Information security

KW - Performance analysis

KW - Prime number

KW - Public key cryptosystem

UR - http://www.scopus.com/inward/record.url?scp=84994320326&partnerID=8YFLogxK

U2 - 10.5573/JSTS.2016.16.5.564

DO - 10.5573/JSTS.2016.16.5.564

M3 - Article

AN - SCOPUS:84994320326

VL - 16

SP - 564

EP - 581

JO - Journal of Semiconductor Technology and Science

JF - Journal of Semiconductor Technology and Science

SN - 1598-1657

IS - 5

ER -