Prime number generation for encryption

Abstract

A device may select a first pseudorandom integer within a range of integers. The device may generate a first candidate prime, based on the first pseudorandom integer, for primality testing. Based on determining that the first candidate prime fails a primality test, the device may select a second pseudorandom integer within the range of integers. The device may generate a second candidate prime, based on the second pseudorandom integer, for primality testing. The device may determine whether the second candidate prime satisfies the primality test. The device may selectively: re-perform, based on the second candidate prime failing the primality test, the selecting the second pseudorandom integer, the generating the second candidate prime, and the determining whether the second candidate prime satisfies the primality test, or using, based on the second candidate prime satisfying the primality test, the second candidate prime as a prime integer in a cryptographic protocol.

What is claimed is: 
     
         1 . A method, comprising:
 determining, by a device, that a first candidate prime fails a primality test,
 wherein the first candidate prime is a product based on a product of known prime integers and a first pseudorandom integer within a range of integers; 
   adjusting the range of integers or a step size associated with the range of integers based on failing to identify a potential second pseudorandom integer using a Galois register or a linear feedback shift register;   identifying a second pseudorandom integer within the range of integers based on adjusting the range of integers or the step size; and   generating, by the device, a second candidate prime for primality testing,
 wherein the second candidate prime is based on a product of another product of the known prime integers and the second pseudorandom integer. 
   
     
     
         2 . The method of  claim 1 , wherein the first pseudorandom integer is generated based on satisfying a size constraint. 
     
     
         3 . The method of  claim 1 , wherein the first pseudorandom integer is additionally based on an addend and one or more integer constraints. 
     
     
         4 . The method of  claim 1 , wherein the second pseudorandom integer is based on stepping through values to avoid repeating pseudorandom integer values. 
     
     
         5 . The method of  claim 1 , wherein the step size is based on random or pseudorandom selections. 
     
     
         6 . The method of  claim 1 , wherein the primality test includes an application of a Pocklington test based on determining that the first pseudorandom integer is not divisible by a sieving prime of a set of sieving primes. 
     
     
         7 . The method of  claim 1 , wherein the first pseudorandom integer is generated based on a group structure constraint. 
     
     
         8 . A non-transitory computer-readable medium storing a set of instructions, the set of instructions comprising:
 one or more instructions that, when executed by one or more processors of a device, cause the device to:
 determine that a first candidate prime fails a primality test,
 wherein the first candidate prime is a product based on a product of known prime integers and a first pseudorandom integer within a range of integers; 
 
 adjust the range of integers or a step size associated with the range of integers based on failing to identify a potential second pseudorandom integer using a Galois register or a linear feedback shift register; 
 identify a second pseudorandom integer within the range of integers based on adjusting the range of integers or the step size; and 
 generate a second candidate prime for primality testing,
 wherein the second candidate prime is based on a product of another product of the known prime integers and the second pseudorandom integer. 
 
   
     
     
         9 . The non-transitory computer-readable medium of  claim 8 , wherein the first pseudorandom integer is generated based on satisfying a size constraint. 
     
     
         10 . The non-transitory computer-readable medium of  claim 8 , wherein the first pseudorandom integer is additionally based on an addend and one or more integer constraints. 
     
     
         11 . The non-transitory computer-readable medium of  claim 8 , wherein the second pseudorandom integer is based on stepping through values to avoid repeating pseudorandom integer values. 
     
     
         12 . The non-transitory computer-readable medium of  claim 8 , wherein the step size is based on random or pseudorandom selections. 
     
     
         13 . The non-transitory computer-readable medium of  claim 8 , wherein the primality test includes an application of a Pocklington test based on determining that the first pseudorandom integer is not divisible by a sieving prime of a set of sieving primes. 
     
     
         14 . The non-transitory computer-readable medium of  claim 8 , wherein the first pseudorandom integer is generated based on a group structure constraint. 
     
     
         15 . A device, comprising:
 one or more memories; and   one or more processors to:
 determine that a first candidate prime fails a primality test,
 wherein the first candidate prime is a product based on a product of known prime integers and a first pseudorandom integer within a range of integers; 
 
 adjust the range of integers or a step size associated with the range of integers based on failing to identify a potential second pseudorandom integer using a Galois register or a linear feedback shift register; 
 identify a second pseudorandom integer within the range of integers based on adjusting the range of integers or the step size; and 
 generate a second candidate prime for primality testing,
 wherein the second candidate prime is based on a product of another product of the known prime integers and the second pseudorandom integer. 
 
   
     
     
         16 . The device of  claim 15 , wherein the first pseudorandom integer is generated based on satisfying a size constraint. 
     
     
         17 . The device of  claim 15 , wherein the first pseudorandom integer is additionally based on an addend and one or more integer constraints. 
     
     
         18 . The device of  claim 15 , wherein the step size is based on random or pseudorandom selections. 
     
     
         19 . The device of  claim 15 , wherein the primality test includes an application of a Pocklington test based on determining that the first pseudorandom integer is not divisible by a sieving prime of a set of sieving primes. 
     
     
         20 . The device of  claim 15 , wherein the first pseudorandom integer is generated based on a group structure constraint.