Multiple prime number generation using a parallel prime number search algorithm

• US 7,120,248 B2
• Filed: 03/26/2001
• Issued: 10/10/2006
• Est. Priority Date: 03/26/2001
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company), Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Wang, Ruth A., Wierenga, Steven W., Hopkins, W. Dale, Collins, Thomas W.
• Primary Examiner(s): Moise, Emmanuel L.
• Assistant Examiner(s): CALLAHAN, PAUL E
• Application Number:
  US09/818,914
• Publication Number:
  US 20020186837A1
• Time in Patent Office: 2,024 Days
• Field of Search: 463/22, 708/250, 708/255, 708/252, 708/256, 708/490, 708/605, 708/493, 708/507, 708/253, 708/604, 380/44, 380/47, 380/46, 380/30
• US Class Current: 380/44
• CPC Class Codes: G06F 2207/7204 Prime number generation or prime number testing
• CPC Class Codes: G06F 7/72 using residue arithmetic
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/3033 details relating to pseudo-prime or prime number generation, e.g. primality test

Abstract

A process is provided for searching in parallel for a plurality of prime number values simultaneously includes the steps of: randomly generating a plurality of k random odd numbers (wherein k is preferably more than 2, but could also be one or more) expressed as n_0,0, n_1,0, . . . n_((k−1)),0, each number providing a prime number candidate; determining a plurality of y additional odd numbers based on each one of the randomly generated odd numbers n_0,0, n_1,0, . . . n_(k−1),0 to provide additional prime number candidates thereby yielding a total number of prime number candidates; sieving the total number of prime number candidates by performing a small divisor test on each of the candidates in order to eliminate candidates revealed to be composite numbers by the small divisor test thereby yielding a sieved number s of candidates; and performing a first probabilistic primality test on each of the sieved number s of candidates, each of the plurality of s first primality tests including an associated exponentiation operation executed by an associated one of a plurality of s of the exponentiation units, the exponentiation operations being performed by the plurality of s exponentiation units substantially simultaneously in order to eliminate candidates revealed to be composite numbers by the primality test thereby yielding a remaining number r of candidates.

Claims

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 for a plurality of prime number values, comprising the steps of:

randomly generating a plurality of k random odd numbers each providing a prime number candidate, including defining a length L for each of the plurality of k random numbers to be generated, and generating each of said plurality of k random odd numbers in an interval between 2^L and 2<sup>L−

1</sup>; and

performing a plurality of t primality tests on each of said plurality of k randomly generated prime numbers whereby (k×

t) tests are performed in parallel, each of the plurality of (k×

t) primality tests including an associated exponentiation operation executed by an associated one of a plurality of (k×

t) exponentiation units.

2. In a prime number generating system as recited in claim 1 further comprising the steps of:

sieving said (k×

(y+1)) prime number candidates by performing a small divisor test on each of said (k×

(y+1)) candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates;

wherein said step of performing includes performing said plurality of t primality tests on each of said sieved number s of candidates, each of primality tests including an associated exponentiation operation executed by an associated one of a plurality of st of the exponentiation units, said exponentiation operations being performed in parallel by said plurality of st exponentiation units.

3. In a prime number generating system as recited in claim 2 further comprising the steps of:

receiving a specified public exponent e associated with a cryptographic application;

testing the suitable of each of said prime number candidates for use in said cryptographic application by testing the relative primality of a each said prime number candidate (p_c) minus one (p_c−

1) and (b) said specified public exponent e, wherein said step of testing the suitability is performed prior to said step of performing said plurality of primality tests.

4. 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 for a plurality of prime number values, comprising the steps of:

randomly generating a plurality of k random odd numbers each providing a prime number candidate, wherein said plurality of k randomly generated numbers are expressed as n_0,0, n_1,0 . . . n<sub>(k−

1)),0</sub>;

determining a plurality of y additional odd numbers based on each one of the randomly generated numbers n_0,0, n_1,0, . . . n<sub>(k−

1),0</sub> to provide (K×

y) additional prime number candidates (n_0,1, n_0,2, . . . n_0,y), (n_1,1, n_1,2, . . . n_1,y), . . . (n<sub>(k−

1),1</sub>, n<sub>(k−

1),2</sub>, . . . n<sub>(k−

1),y</sub>) thereby yielding a total number of (k×

(y+1)) prime number candidates; and

performing t primality tests on each of said total number of (k×

(y+1)) prime number candidates, each of the plurality of (k×

(y+1)×

t) primality tests including an associated exponentiation operation executed by an associated one of a plurality of (k×

(y+1)×

t) exponentiation units, said exponentiation operations being performed in parallel by said plurality of (k×

(y+1)×

t) exponentiation units.

5. In a prime number generating system as recited in claim 4 wherein each of said plurality of prime number values being searched for has a specified length, and wherein said plurality of y additional odd numbers defines an interval that is selected relative to said specified length.

6. In a prime number generating system as recited in claim 4 wherein said step of determining a plurality of y additional odd numbers based on each one of the randomly generated numbers n_0,0, n_1,0, . . . n_(k−

1),0 includes successively adding two in each of said randomly generated odd numbers n_0,0, n_1,0, . . . n<sub>(k−

1),0</sub> to provide (k×

y) additional prime number candidates expressed as (n_0,1=n₀₀+2, n_0,2=n_0,0+4, . . . n_0,y=n_0,0+(y

     2)), (n_1,1=n_1,0+2, n_1,2=n_1,0+4, . . . n_1,y=n_1,0+(y

     2)), . . . (n<sub>(k−

1),1</sub>=n<sub>(k−

1),0</sub>+2, n<sub>(k−

1),2</sub>=n<sub>(k−

1,0</sub>+4, . . . n<sub>(k−

1),y</sub>=n<sub>(k−

1),0</sub>+(y

     2)).

7. In a prime number generating system as recited in claim 4 wherein said exponentiation operations are performed by said associated exponentiation units simultaneously.

8. In a prime number generating system as recited in claim 4 further comprising the steps of:

sieving said prime number candidates by performing a small divisor test on each of said number (k×

(y×

1)) of prime number candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates;

wherein said step of performing primality tests includes performing t primality tests on each of said sieved number s of candidates, each of the plurality of s×

t primality tests including an associated exponentiation operation executed by an associated one of a plurality of s×

t exponentiation units, said exponentiation operations being performed in parallel by said plurality of s×

t exponentiation units.

9. In a prime number generating system as recited in claim 4 further comprising the step of:

sieving said prime number candidates by performing a small divisor test on each of said number (k×

(y+1)) of prime number candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates;

wherein said step of performing primality tests includes performing an associated first one of t primality tests on each of said sieved number s of candidates, each of the plurality of s first primality tests including an associated exponentiation operation executed by an associated one of a plurality of s of the exponentiation units, said first exponentiation operations being performed by said plurality of s exponentiation units in parallel in order to eliminate candidates revealed to be composite numbers by said first primality tests thereby yielding a remaining number r of candidates; and

performing a plurality of t−

1 additional primality tests on each of said remaining number r of candidates, each of the plurality of (r×

(t−

1)) primality tests including an associated exponentiation operation executed by an associated one of a plurality of (r×

(t−

1)) exponentiation units, said (r×

(t−

1)) exponentiation operations being performed by said plurality of (r×

(t−

1)) exponentiation units in parallel in order to eliminate further candidates revealed to be composite numbers.

10. In a prime number generating system as recited in claim 4 wherein said step of performing primality tests includes performing a Fermat type primality test.

11. In a prime number generating system as recited in claim 4 wherein said step of performing primality tests includes performing a Miller-Rabin type primality test.

12. In a prime number generating system as recited in claim 4 wherein said step of randomly generating a plurality of k random odd numbers further includes:

defining a length L for each of the plurality of k random numbers to be generated; and

generating each of said plurality of k random odd numbers in an interval between 2^L and 2<sup>L−

1</sup>.

13. 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 for a plurality of prime number values, comprising the steps of,

randomly generating at least one random odd number providing a prime number candidate;

determining a plurality of y additional odd numbers based on said at least one randomly generated odd number to provide y additional prime number candidates, thereby providing a total number of y+1 candidates;

performing a plurality t primality tests on each of said (y+1)×

t candidates, each of the (y+1)×

t primality tests including an associated exponentiation operation executed by an associated one of (y+1)×

t exponentiation units, said (y+1)×

t exponentiation operations being performed in parallel by said associated (y+1)×

t exponentiation units;

and further comprising the step of;

receiving a specified public exponent e associated with a cryptographic application;

testing the suitability of each of said prime number candidates for use in said cryptographic application by testing the relative primality of (a) each of said prime number candidates (p_c) minus one (p_c−

1) and (b) a specified public exponent e, wherein said step of testing the suitability is performed prior to said step of performing said primality tests.

14. In a prime number generating system as recited in claim 13 wherein said at least one randomly generated odd number is expressed as n_0,0, and wherein said step of determining a plurality of y additional odd numbers based on said randomly generated odd number n_0,0 includes successively adding two to said randomly generated odd number n_0,0 to provide y+1 additional prime number candidates expressed as (n_0,1=n₀₀+2, n_0,2=n_0,0+4, . . . n_0,y=n_0,0+(y 2)).

15. In a prime number generating system as recited in claim 13 further comprising the step of sieving said y+1 candidates by performing a small divisor test on each of said candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved numbers of candidates.

16. In a prime number generating system as recited in claim 13 further comprising the step of:

sieving said y+1 candidates by performing a small divisor test on each of said candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates;

wherein said step of performing primality tests includes performing an associated first one of t primality tests on each of said sieved numbers of candidates, each of the plurality of s first primality tests including an associated exponentiation operation executed by an associated one of a plurality of s of the exponentiation units, said first exponentiation operations being performed by said plurality of s exponentiation units in parallel in order to eliminate candidates revealed to be composite numbers by said first primality tests thereby yielding a remaining number r of candidates; and

performing a plurality of t−

1 additional primality tests on each of said remaining number r of candidates, each of the plurality of (r×

(t−

1)) additional primality tests including an associated exponentiation operation executed by an associated one of a plurality of (r×

(t−

1)) exponentiation units, the (r×

(t−

1)) exponentiation operations being performed by said plurality of (r×

(t−

1)) exponentiation units in parallel in order to eliminate further candidates revealed to be composite numbers.

17. In a prime number generating system as recited in claim 13 wherein said step of performing primality tests includes performing a Fermat type primality test.

18. In a prime number generating system as recited in claim 13 wherein said step of performing primality tests includes performing a Miller-Rabin type primality test.

19. In a prime number generating system as recited in claim 13 wherein said step of randomly generating at least one random odd number further includes:

defining a length L for the or each of the odd numbers to be generated; and

generating the or each of said plurality of odd numbers in an interval between 2^L and 2<sup>L−

1</sup>.

20. 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 for a plurality of prime number values, comprising the steps of:

randomly generating a plurality of random odd numbers providing prime number candidates;

sieving said candidates by performing a small divisor test on each of said candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates;

testing the pimality of said sieved candidates by performing a first one of a plurality of t primality tests on said sieved number s of candidates, each of the plurality s of the first primality tests including an associated exponentiation operation executed by an associated one of a plurality s of the exponentiation units, said exponentiation operations being performed simultaneously by said plurality of s exponentiation units in order to eliminate candidates revealed to be composite numbers thereby yielding a remaining number r of candidates; and

performing a plurality of t−

1 additional ones of said t primality tests on each of said remaining number r of candidates, each of the plurality of (r×

(t−

1)) first primality tests including an associated exponentiation operation executed by an associated one of a plurality of (r×

(t−

1)) exponentiabon units, said (r×

(t−

1)) exponentiation operations being simultaneously performed by said plurality of (r×

(t−

1)) exponentiation units in order to eliminate further candidates revealed to be composite numbers.

21. In a prime number generating system as recited in claim 20 further including the steps of:

receiving a specified public exponent e associated with a cryptographic application;

testing the suitability of each of said prime number candidates for use in said cryptographic application by testing the relative primality of (a) each said prime number candidates (p_c) minus one (p_c−

1) and (b) said specified public exponent e, wherein said step of testing the suitability is performed prior to said step of performing said first one of said primality tests.

22. 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 for a plurality of prime number values, comprising the steps of:

randomly generating a plurality of k random odd numbers expressed as n_0,0, n_1,0, . . . n<sub>(k−

1),0</sub>, each said number providing a prime number candidate;

determining a plurality of y additional odd numbers based on each one of the randomly generated odd numbers n_1,0, . . . n<sub>(k−

1),0</sub>, to provide (k×

y) additional prime number candidates (n_0,1, n_0,2′

. . . n_0,y), (n_1,1, n_1,2, . . . n_1,y), . . . (n<sub>(k−

1),1</sub>, n<sub>(k−

1),y</sub>) thereby yielding a total number of (k×

(y+1)) prime number candidates;

sieving said (k×

(y+1)) prime number candidates by performing a small divisor test on each of said candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates; and

performing at least one primality test on each of said sieved number s of candidates, each of the plurality of s primality tests including an associated exponentiation operation executed by an associated one of a plurality of s of the exponentiation units, said exponentiation operations being performed in parallel by said plurality of s exponentiation units in order to eliminate candidates revealed to be composite numbers by said primality test thereby yielding a remaining number r of candidates; and

performing a plurality of t−

1 additional primality tests on each of said remaining number r of candidates, each of the plurality of (r×

(t−

1)) primality tests including an associated exponentiation operation executed by an associated one of a plurality of (r×

(t−

1)) exponentiation units, said (r×

(t−

1)) exponentiation operations being performed by in parallel by said plurality of (r×

(t−

1)) exponentiation units in order to eliminate further candidates revealed to be composite numbers.

23. In a prime number generating system as recited in claim 22 wherein said step of determining a plurality of y additional odd numbers based on each one of the randomly generated odd numbers n_1,0, . . . n_(k−

1),0 includes successively adding two to each of said randomly generated odd numbers n_1,0, . . . n<sub>(k−

1),0</sub> to provide (k×

y) additional prime number candidates expressed as (n_0,1=n₀₀+2, n_0,2=n_0,0+4, . . . n_0,y+(y

     2)), (n_1,1=n_1,0+2, n_1,2=n_1,0+4, . . . n_1,y=n_1,0+(y

     2)), . . . (n<sub>(k−

1),1</sub>=n<sub>(k−

1),0</sub>+2, n<sub>(k−

1),2</sub>=n<sub>(k−

1,0</sub>+4, . . . n<sub>(k−

1),y</sub>=n<sub>(k−

1),0</sub>+(y

     2)).

24. In a prime number generating system as recited in claim 22 wherein said step of performing said first primality test includes performing a Fermat type primality test.

25. In a prime number generating system as recited in claim 22 wherein said step of performing said first primality test includes performing a Miller-Rabin type primality test.

26. In a prime number generating system as recited in claim 22 wherein said step of randomly generating a plurality of k random odd numbers further includes:

defining a length L for each of the plurality of k random numbers to be generated; and

generating each of said plurality of k random odd numbers in an interval between 2^L and 2<sup>L−

1</sup>.

27. In a prime number generating system as recited in claim 22 wherein k is greater than or equal to 2.

28. In a prime number generating system as recited in claim 22 further comprising the steps of:

receiving a specified public exponent e associated with a cryptographic application;

testing the suitability of each of said sieved prime number candidates for use in said cryptographic application by testing the relative primality of (a) each said sieved prime number candidate (p_c) minus one (p_c−

1) and (b) said specified public exponent e, wherein said step of testing the suitability is performed prior to said step of performing said first primality tests.

29. A prime number generating system for searching for a plurality of prime number values, comprising:

processing means operative to randomly generate a plurality of k random odd numbers each providing a prime number candidate, and to provide a plurality t sets of test parameters associated with a plurality of t primality tests to be performed on each one of said plurality of k randomly generated numbers, each (k×

t) sets of said test parameters including said associated one of said plurality k randomly generated numbers and an associated one of a plurality of t base values; and

a plurality of exponentiation units each being communicatively coupled with said processing means, said plurality of exponentiation units includes a plurality of at least (k×

t) exponentiation units each being responsive to an associated one of said (k×

t) sets of test parameters, and operative to perform an exponentiation operation based on said associated set of test parameters, and also operative to generate a primality test result signal declaring said associated prime number candidate to be either composite or prime with reference to said associated base value, said exponentiation units being operative to perform said plurality of at least (k×

t) exponentiation operations in parallel;

said processing means being responsive to said primality test result signals, and operative to process said test result signals for the purpose of eliminating randomly generated numbers declared to be composite in accordance with a search for prime number values.

30. A prime number generating system as recited in claim 29 wherein said processing means is further operative to sieve said prime number candidates by performing a small divisor test on each of said prime number candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates.

31. A prime number generating system as recited in claim 29 wherein said plurality of k randomly generated odd numbers are expressed as n_0,0, n_1,0, . . . n_(k−

1),0, and wherein;

said processing means is further operative to develop a plurality of y additional odd numbers based on each one of the randomly generated odd numbers n_0,0, n_1,0, . . . n<sub>(k−

1),0</sub>, to provide (k×

y) additional prime number candidates (n_0,1, n_0,2, . . . n_0,y), (n_1,1, n_1,2, . . . n_1,y), . . . (n<sub>(k−

1),1</sub>, n<sub>(k−

1),2</sub>, . . . n<sub>(k−

1),y</sub>) thereby yielding a total number of (k×

(y+1)) prime number candidates;

said plurality of exponentiation units includes a plurality of at least (k×

(y+1)) exponentiation units each being responsive to an associated one of said (k×

(y+1)) sets of said test parameters, and being operative to perform an exponentiation operation based on said associated set of test parameters, and also operative to generate a primality test result signal declaring said associated prime number candidate to be either composite or prime with reference to said associated base value, said plurality of at least (k×

(y+1)) exponentiation units being operative to perform the plurality of (k×

(y+1)) exponentiation operations in parallel.

32. A prime number generating system as recited in claim 31 wherein said processing means is operative to develop said plurality of y additional odd numbers based on each one of the randomly generated odd numbers n_1,0, . . . n_(k−

1),0, by successively adding two to each of said randomly generated odd numbers n_1,0, . . . n<sub>(k−

1),0</sub>, to provide (k×

y) additional prime number candidates expressed as (n_0,1=n₀₀+2, n_0,2=n_0,0+4, . . . n_0,y=n_0,1+(y

     2)), (n_1,1=n_1,0+2, n_1,2=n_1,0+4, . . . n_1,y=n_1,0+(y

     2)), . . . n<sub>(k−

1),1</sub>=n<sub>(k−

1),0</sub>+2, n<sub>(k−

1),2</sub>=n<sub>(k−

1,0</sub>+4, . . . n<sub>(k−

1),y</sub>=n<sub>(k−

1),0</sub>+(y

     2)).

33. A prime number generating system as recited in claim 31 wherein:

said processing means is operative to provide a plurality of t sets of test parameters associated with a plurality of t primality tests to be performed on each one of said plurality of (k×

(y+1)) randomly generated numbers, each of the (k×

(y+1)×

t) sets of said test parameters including said associated one of said plurality of (k×

(y+1)) prime number candidates and an associated one of a plurality of t base values;

said plurality of exponentiation units includes a plurality of at least (k×

(y+1)×

t) exponentiation units each being responsive to an associated one of said (k×

(y+1)×

t) sets of said test parameters, and being operative to perform an exponentiation operation based on said associated set of test parameters, and also operative to generate a primality test result signal declaring said associated prime number candidate to be either composite or prime with reference to said associated base value, said plurality of at least (k×

(y+1)×

t) exponentiation units being operative to perform said plurality of (k×

(y+1)×

t) exponentiation operations in parallel.

34. A prime number generating system as recited in claim 29 wherein each of said primality tests is a Fermat type primality test.

35. A prime number generating system as recited in claim 29 wherein each of said primality tests is a Miller-Rabin type primality test.

36. A prime number generating system as recited in claim 29 wherein said processing means is operative to randomly generate said plurality of k random odd numbers by performing the steps of:

defining a length L for each of the plurality of k random numbers to be generated; and

generating each of said plurality of k random odd numbers in an interval between 2^L and 2<sup>L−

1</sup>.

37. A prime number generating system for searching for a plurality of prime number values, comprising:

processing means operative to randomly generate at least one random odd number providing a prime number candidate, and to determine a plurality of y additional odd numbers based on each of said at least one randomly generated odd number to provide y additional prime number candidates, thereby providing a total number of y+1 candidates, said processing means also operative to provide a plurality of t sets of test parameters associated with a plurality t primality tests to be performed on each one of said y+1 prime number candidates, each of the ((y+1(×

t) sets of test parameters including said associated one of said plurality of prime number candidates and an associated base value; and

a plurality of at least ((y+1)×

t) exponentiation units each communicatively coupled with said processing means, and each responsive to an associated one of said ((y+1)×

t) sets of test parameters, and operative to perform an ecponentiation operation based on said associated set of test parameters, and also operative to generate a primality test result signal declaring said associated prime number candidate to be either composite or prime with reference to said associated base value, said plurality of at least ((y+1)×

t) exponentiation units being operative in parallel to perform said plurality of ((y+1)×

t) exponentiation;

said processing means being responsive to said primality test result signals, and operative to process said test result signals for the purpose of eliminating randomly generated numbers declared to be composite in accordance with a search for prime number values.

38. A prime number generating system as recited in claim 37 wherein said at least one randomly generated odd number is expressed as n_0,0, and wherein said processing means is operative to determine said plurality of y additional odd numbers based on said randomly generated odd number by successively adding two to said randomly generated odd number n_0,0 to provide (y+1) additional prime number candidates expressed as (n_0,1=n₀₀+2, n_0,0+4, . . . n_0,y=n_0,0+(y 2)).

39. A prime number generating system as recited in claim 37 wherein said processing means is further operative to sieve said prime number candidates by performing a small divisor test on each of said prime number candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates.

40. A prime number generating system as recited in claim 37 wherein:

said processing means is operative to generate a plurality of k random odd numbers each providing a prime number candidate, and to determine a plurality of y additional odd numbers based on each of said k random odd numbers to provide k×

y additional prime number candidates, thereby providing a total number of at least k×

(y+1) candidates, said processing means also operative to provide t sets of test parameters associated with t primality tests to be performed on each one of said k×

(y+1) prime number candidates, each said set of said test parameters including said associated prime number candidate and an associated base value; and

said plurality of exponentiation units includes a plurality of at least (k×

(y+1)×

t) exponentiation units each being responsive to an associated one of said (k×

(y+1)×

t) sets of said test parameters, and being operative to perform an exponentiation operation based on said associated set of test parameters, and also operative to generate a primality test result signal declaring said associated prime number candidate to be either composite or prime with reference to said associated base value, said plurality of at least (k×

(y+1)×

t) exponentiation units being operative to perform said plurality of (k×

(y+1)×

t) exponentiation operations in parallel.

41. A prime number generating system as recited in claim 40 wherein said processing means is operative to randomly generate said plurality of k random odd numbers by performing the steps of:

defining a length L for each of the plurality of k random numbers to be generated; and

generating each of said plurality of k random odd numbers in an interval between 2^L and 2<sup>L−

1</sup>.

42. A prime number generating system as recited in claim 37 wherein each of said primality tests is a Fermat type primality test.

43. A prime number generating system as recited in claim 37 wherein each of said primality tests is a Miller-Rabin type primality test.

44. A computer readable storage medium having stored thereon encoding instructions for executing a process of searching for a plurality of prime number values in a prime number generation system including a processing unit and a plurality of exponentiation units communicatively coupled with the processing unit, the process comprising the steps of:

randomly generating a plurality of k random odd numbers each providing a prime number candidate, said plurality of k randomly generated numbers are expressed as n_0,0, n_1,0, . . . n<sub>(k−

1),0</sub>;

determining a plurality of y additional odd numbers based on each one of the randomly generated numbers n_0,0, n_1,0, . . . n<sub>(k−

1),0</sub> to provide (k×

y) additional prime number candidates (n_0,1, n_0,2, . . . n_0,y), (n_1,1, n_1,2, . . . n_1,y), . . . (n<sub>(k−

1),1</sub>, n<sub>(k−

1),2</sub>, . . . n<sub>(k−

1),y</sub>) thereby yielding a total number of (k×

(y+1)) prime number candidates; and

performing a plurality of t primality tests on each of said total number of (k×

(y+1)) prime numbers whereby (k×

(y+1)×

t) tests are performed in parallel, each of the plurality of (k×

(y+1)×

t) primality tests including an associated exponentiation operation executed by an associated one of a plurality of (k×

x(y+1)×

t) exponentiation units.

45. A computer readable storage medium as recited in claim 44 wherein said step of determining a plurality of y additional odd numbers based on each one of the randomly generated numbers n_0,0, n_1,0, . . . n_(k−

1),0 includes successively adding two to each of said randomly generated odd numbers n_0,0, n_1,0, . . . n<sub>(k−

1),0</sub> to provide (k×

y) additional prime number candidates expressed as (n_0,1=n_0,0+2, n_0,2=n_0,0+4, . . . n_0,y=n_0,0+(y

     2)), (n_1,1=n_1,0+2, n_1,2=n_1,0+4, . . . n_1,y=n_1,0+(y

     2)), . . . n<sub>(k−

1),1</sub>=n<sub>(k−

1),0</sub>+2, n<sub>(k−

1),2</sub>=n<sub>(k−

1,0</sub>+4, . . . n<sub>(k−

1),y</sub>=n<sub>(k−

1),0</sub>+(y

     2)).

46. A computer readable storage medium as recited in claim 44 further comprising the steps of:

sieving said prime number candidates by performing a small divisor test on each of said number (k×

(y+1)) of prime number candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates;

wherein said step of performing includes performing t primality tests on each of said sieved number s of candidates, each of the plurality of s×

t primality tests including an associated exponentiation operation executed by an associated one of a plurality of s×

t exponentiation units, said exponentiation operations being performed by said plurality of s×

t exponentiation units simultaneously.

47. A computer readable storage medium as recited in claim 46 further comprising the steps of:

receiving a specified public exponent e associated with a cryptographic application;

testing the suitability of each of said prime number candidates for use in said cryptographic application by testing the relative primality of (a) each said prime number candidate (p_c) minus one (p_c−

1) said specified public exponent e, wherein said step of testing the suitability as performed prior to said step of performing said primality tests.

48. A computer readable storage medium as recited in claim 44 further comprising the steps of:

sieving said prime number candidates by performing a small divisor test on each of said number (k×

(y+1)) of prime number candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number s of candidates;

wherein said step of performing includes performing an associated first one of t primality tests on each of said sieved numbers of candidates, each of the plurality of s first primality tests including an associated exponentiation operation executed by an associated one of a plurality of s of the exponentiation units, said first exponentiation operations being performed by said plurality of s exponentiation units in parallel in order to eliminate candidates revealed to be composite numbers by said first primality tests thereby yielding a remaining number r of candidates; and

performing a plurality of t−

1 additional primality tests on each of said remaining number r of candidates, each of the plurality of (r×

(t−

1)) primality tests including an associated exponentiation operation executed by an associated one of a plurality of (r×

(t−

1)) exponentiation units, said (r×

(t−

1)) exponentiation operations being performed by said plurality of (r×

(t−

1)) exponentiation units in parallel in order to eliminate further candidates revealed to be composite numbers.

49. 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 for a plurality of prime number values, comprising the steps of:

randomly generating a plurality of random odd numbers each providing a prime number candidate; and

receiving a specified public exponent e associated with a cryptographic application;

testing the suitability of each of said prime number candidates for use in said cryptographic application by testing the relative primality of (a) each said prime number candidate (p_c) minus one (p_c−

1) and (b) said specified public exponent e to yield a plurality of k suitable prime number candidates; and

performing a plurality of t primality tests on each of said plurality of k suitable prime number candidates whereby (k×

t) tests are performed in parallel, each of the plurality of (k×

t) primality tests including an associated exponentiation operation executed by an associated one of a plurality of (k×

t) exponentiation units.

50. 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 for a plurality of prime number values, comprising the steps of:

randomly generating a plurality of k random odd numbers expressed as n_0,0, n_1,0, . . . n<sub>(k−

1),0</sub>, each said number providing a prime number candidate;

determining a plurality of y additional odd numbers based on each one of the randomly generated odd numbers n_1,0, . . . n<sub>(k−

1),0</sub> to provide (k×

y) additional prime number candidates (n_0,1, n_0,2′

. . . n_0,y), (n_1,1, n_1,2, . . . n_1,y), . . . n<sub>(k−

1),1</sub>, n<sub>(k−

1),2</sub>, . . . n<sub>(k−

1),y</sub>) thereby yielding a total number of (k×

(y+1)) prime number candidates;

sieving said (k×

(y+1)) prime number candidates by performing a small divisor test on each of said candidates in order to eliminate candidates revealed to be composite numbers by said small divisor test thereby yielding a sieved number of candidates;

receiving a specified public exponent e associated with a cryptographic application;

testing the suitability of each of said sieved prime number candidates for use in said cryptographic application by testing the relative primality of (a) each said sieved prime number candidate (p_c) minus one (p_c−

1) and (b) said specified public exponent e to yield s suitable sieved candidates; and

performing at least one primality test on each of said s suitable sieved candidates, each of the plurality of s primality tests including an associated exponentiation operation executed by an associated one of a plurality of s exponentiation units, said exponentiation operations being performed in parallel by said plurality of s exponentiation units in order to eliminate candidates revealed to be composite numbers by said primality test thereby yielding a remaining number r of candidates.

51. In a prime number generating system as recited in claim 50 further comprising the steps of:

performing a plurality of t−

1 additional primality tests on each of said remaining number r of candidates, each of the plurality of (r×

(t−

1)) primality tests including an associated exponentiation operation executed by an associated one of a plurality of (r×

(t−

1)) exponentiation units, said (r×

(t−

1)) exponentiation operations being performed by in parallel by said plurality of (r×

(t−

1)) exponentiation units in order to eliminate further candidates revealed to be composite numbers.