Multiple prime number generation using a parallel prime number search algorithm
First Claim
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.
8 Assignments
0 Petitions
Accused Products
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 n0, 0, n1, 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 n0, 0, n1, 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.
-
Citations
63 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 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 51, 52)
-
-
15. 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 simultaneously, 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 at least one primality test on each of said y+1 candidates, each of the y+1 primality tests including an associated exponentiation operation executed by an associated one of y+1 of the exponentiation units, said y+1 exponentiation operations being performed by said associated y+1 exponentiation units substantially simultaneously.
-
-
24. 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 simultaneously, comprising the steps of:
-
randomly generating at least one random odd number providing a prime number candidate; and
testing the primality of said candidate by performing a plurality of t primality tests on said candidate, each of the plurality of the t primality tests including an associated exponentiation operation executed by an associated one of a plurality of t of the exponentiation units, said exponentiation operations being performed by said plurality of t exponentiation units substantially simultaneously.
-
-
28. 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 simultaneously, comprising the steps of:
-
randomly generating a plurality of k random odd numbers expressed as n0, 0, n1, 0, . . . n((k−
1)), 0, 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 n0, 0, n1, 0, . . . n(k−
1), 0 to provide (k×
y) additional prime number candidates (n0, 1, n0, 2, . . . n0, y), (n1, 1, n1, 2, . . . n1, y), . . . (n(k−
1), 1, n(k−
1), 2, . . . n(k−
1), y) 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 by said plurality of s exponentiation units substantially simultaneously in order to eliminate candidates revealed to be composite numbers by said primality test thereby yielding a remaining number r of candidates.
-
-
36. A prime number generating system for searching in parallel for a plurality of prime number values simultaneously, comprising:
-
processing means operative to randomly generate a plurality of k random odd numbers each providing a prime number candidate, and to provide at least one set of test parameters associated with a primality test to be performed on each one of said plurality of k randomly generated numbers, each said set of said test parameters including said associated randomly generated number and an associated base value; and
a plurality of exponentiation units each being communicatively coupled with said processing means, and being responsive to an associated one of said 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 exponentiation operations substantially simultaneously;
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.
-
-
45. A prime number generating system for searching in parallel for a plurality of prime number values simultaneously, 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 being operative to provide at least one set of test parameters associated with a primality test to be performed on each one of said prime number candidates, each said set of test parameters including said associated prime number candidate and an associated base value; and
a plurality of exponentiation units each being communicatively coupled with said processing means, and being responsive to an associated one of said 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 exponentiation operations substantially simultaneously;
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.
-
-
53. A prime number generating system for searching in parallel for a plurality of prime number values simultaneously, comprising:
-
processing means operative to randomly generate a plurality of random odd numbers each providing a prime number candidate, and to provide a set of test parameters associated with a primality test to be performed on each one of said plurality of randomly generated numbers, each said set of said test parameters including said associated randomly generated number; and
a plurality of exponentiation units each being communicatively coupled with said processing means, and being responsive to an associated one of said sets of test parameters, and operative to perform an exponentiation operation based on said associated set of test parameters and an associated base value, 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 exponentiation operations substantially simultaneously;
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.
-
-
54. A computer readable storage medium having stored thereon encoding instructions for executing a process of searching in parallel for a plurality of prime number values simultaneously 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; 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. - View Dependent Claims (55, 56, 57, 58, 59, 60, 61, 62, 63)
-
Specification