Probabilistic analysis on JPV algorithm and improving it using GCD function

Hosung Jo, Heejin Park

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

JPV algorithm, proposed by Joye et al. was predicted to be faster than the combined prime generation algorithm but it runs slower in practice. This discrepancy is because only the number of Fermat test calls was compared in estimating its total running time. We present a probabilistic analysis on the total running time of JPV algorithm. This analysis is very accurate and corresponds to the experiment with only 1-2% error. Furthermore, we propose an improved JPV algorithm that uses GCD function. It is faster than JPV algorithm and similar to the combined algorithm with the same space requirement.

Original languageEnglish
Pages (from-to)535-542
Number of pages8
JournalApplied Mathematics and Information Sciences
Volume9
Issue number2
DOIs
StatePublished - 2015 Jan 1

Fingerprint

Probabilistic Analysis
Fermat
Discrepancy
Requirements
Experiment
Experiments

Keywords

  • GCD function
  • Primality test
  • Prime generation
  • Public-key cryptosystem

Cite this

@article{8dedf4dd0f8946c399b1598946dc8f50,
title = "Probabilistic analysis on JPV algorithm and improving it using GCD function",
abstract = "JPV algorithm, proposed by Joye et al. was predicted to be faster than the combined prime generation algorithm but it runs slower in practice. This discrepancy is because only the number of Fermat test calls was compared in estimating its total running time. We present a probabilistic analysis on the total running time of JPV algorithm. This analysis is very accurate and corresponds to the experiment with only 1-2{\%} error. Furthermore, we propose an improved JPV algorithm that uses GCD function. It is faster than JPV algorithm and similar to the combined algorithm with the same space requirement.",
keywords = "GCD function, Primality test, Prime generation, Public-key cryptosystem",
author = "Hosung Jo and Heejin Park",
year = "2015",
month = "1",
day = "1",
doi = "10.12785/amis/092L28",
language = "English",
volume = "9",
pages = "535--542",
journal = "Applied Mathematics and Information Sciences",
issn = "1935-0090",
number = "2",

}

Probabilistic analysis on JPV algorithm and improving it using GCD function. / Jo, Hosung; Park, Heejin.

In: Applied Mathematics and Information Sciences, Vol. 9, No. 2, 01.01.2015, p. 535-542.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Probabilistic analysis on JPV algorithm and improving it using GCD function

AU - Jo, Hosung

AU - Park, Heejin

PY - 2015/1/1

Y1 - 2015/1/1

N2 - JPV algorithm, proposed by Joye et al. was predicted to be faster than the combined prime generation algorithm but it runs slower in practice. This discrepancy is because only the number of Fermat test calls was compared in estimating its total running time. We present a probabilistic analysis on the total running time of JPV algorithm. This analysis is very accurate and corresponds to the experiment with only 1-2% error. Furthermore, we propose an improved JPV algorithm that uses GCD function. It is faster than JPV algorithm and similar to the combined algorithm with the same space requirement.

AB - JPV algorithm, proposed by Joye et al. was predicted to be faster than the combined prime generation algorithm but it runs slower in practice. This discrepancy is because only the number of Fermat test calls was compared in estimating its total running time. We present a probabilistic analysis on the total running time of JPV algorithm. This analysis is very accurate and corresponds to the experiment with only 1-2% error. Furthermore, we propose an improved JPV algorithm that uses GCD function. It is faster than JPV algorithm and similar to the combined algorithm with the same space requirement.

KW - GCD function

KW - Primality test

KW - Prime generation

KW - Public-key cryptosystem

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

U2 - 10.12785/amis/092L28

DO - 10.12785/amis/092L28

M3 - Article

AN - SCOPUS:84931834239

VL - 9

SP - 535

EP - 542

JO - Applied Mathematics and Information Sciences

JF - Applied Mathematics and Information Sciences

SN - 1935-0090

IS - 2

ER -