Research indexJournal article
Probabilistic Analysis on JPV Algorithm and Improving It using GCD Function
Jo, Park
1 Jan 2015
NobleIDark:/48914/w1/20260523/DFB430BBDOI10.12785/amis/092l28
Probabilistic Analysis on JPV Algorithm and Improving It using GCD Function
Jo, Park · 2015 · Subscription
NobleIDark:/48914/w1/20260523/DFB430BBDOI10.12785/amis/092l28
The full text is at the publisher
You can read the abstract here, or open it at the publisher.
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.