Parallel Algorithms for Generating Large Tables of Primes

Kathy Liszka
Associate Professor of Mathematical Sciences
 

                                                           Funding Sources
                                                           Description of the Project
                                                           High Performance Computing Sources
                                                           Projected Benefits of the Project
                                                           Collaborations
 

Funding Sources

NSF Grant CCR-9634559

[top]
 

Description of the Project

The search for efficient algorithms to produce large primes is motivated largely by the needs of cryptologists and number theorists.^41-43 The focus of the project is to investigate variations on sieving algorithms to generate very large tables of primes efficiently using parallel architectures.  Testing and implementation of the algorithms are based on selected mapping and communication structures that are determined to be optimal.  Of special interest is insight into the scope of memory limitations that must be addressed in order to generate primes to 10 ¹⁸.  Break even points between various algorithms are being identified to determine how feasible it is to reach a certain point given a particular algorithm.

[top]
 

High Performance Computing Sources

This project requires high-speed network access for moving large file of primes, both for initial setups in some algorithms, and for the final results on remote computers.  The connections are to the Ohio Super Computer Center and Purdue University.

[top]
 

Projected Benefits of the Project

[top]
 

Collaborations

John K. Antonio, Texas Tech University, H.J. Siegel, Purdue University, Samuel S Wagstaff, Purdue University

[top]