1. In a prime number generating system including a processing unit and a plurality of exponentiation units communicatively coupled with the processing unit, a process of searching in parallel for a plurality of prime number values substantially simultaneously, comprising the steps of: randomly generating a plurality of k random odd numbers each providing a prime number candidate; and performing at least one primality test on each of said candidates, each of said primality tests including an associated exponentiation operation executed by an associated one of the exponentiation units, said exponentiation operations being performed by said associated exponentiation units substantially simultaneously.