### 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 language | English |
---|---|

Pages (from-to) | 564-581 |

Number of pages | 18 |

Journal | Journal of Semiconductor Technology and Science |

Volume | 16 |

Issue number | 5 |

DOIs | |

State | Published - 2016 Oct 1 |

### Fingerprint

### Keywords

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

### Cite this

*Journal of Semiconductor Technology and Science*,

*16*(5), 564-581. https://doi.org/10.5573/JSTS.2016.16.5.564

}

*Journal of Semiconductor Technology and Science*, vol. 16, no. 5, pp. 564-581. https://doi.org/10.5573/JSTS.2016.16.5.564

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

Research output: Contribution to journal › Article

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 -