Abstract
In this paper, we discuss how to efficiently generate a prime number using Multi-core architecture. We modify the bit-array algorithm so that it can work in parallel manner. The proposed algorithm searches for the candidates of prime numbers in parallel. Then, the Miller-Rabin primality tests are performed on these candidates using all available cores. Since more than one candidate can be tested, a prime number can be found in a less time than single-core case if the proposed algorithm works on multi-core environment. Experimental result shows that about 110% and 265% performance improvements are achieved when two and four cores are used, respectively.
| Translated title of the contribution | Fast Prime Number Generation on Software Leveraging Multi-core Environment |
|---|---|
| Original language | Korean |
| Pages (from-to) | 339-347 |
| Number of pages | 9 |
| Journal | 정보과학회논문지 : 정보통신 |
| Volume | 40 |
| Issue number | 6 |
| State | Published - 2013 |