A note on efficient implementation of prime generation algorithms in small portable devices

This paper investigates existing prime generation algorithms on small portable devices, makes optimizations and compares their efficiencies. It shows by comparing the performances that the bit array algorithm is the most efficient among all the existing prime generation algorithms. The paper further optimizes the implementation of the bit array algorithm by using an optimal parameter in the prime generations, namely the small prime set for its sieving procedure. A method for estimating the optimal small prime set for the bit array algorithm is provided. The paper gives generalized bit array algorithms which are able to find primes with special constraints, i.e., DSA primes and strong primes. Finally, the algorithms are implemented in a smart card and a PDA for validation. It shows that there is very little efficiency sacrifice for generating special primes with respect to generating random primes. It also shows that using optimal sets of small primes for prime generations will result in 30-200% efficiency improvement.