One feature pertains to a method that reduces the computational delay associated with generating prime numbers. The method includes generating a first random number having a plurality of bits. A first primality test is then executed on the first random number. Then, it is determined whether the first random number generated fails or passes the first primality test. If the first random number fails the primality test then a portion but not all of the plurality of bits of the first random number are replaced with an equal number of randomly generated bits to generate a second random number. Next, a primality test is again executed on the second random number. This process is repeated until a prime number is detected.