3 Added a part about an estimate. edited Dec 11 '12 at 6:50 Polynomial 116k3737 gold badges259259 silver badges350350 bronze badges It's unlikely. The primes involved are huge, so the keyspace is massive. Just how massive depends on your key size, but let's pick 512-bit primes for a lower bound example. The prime counting function gives us an estimate of how many prime numbers are below a given number. It is difficult to compute precisely, but a close estimate is defined as `π(x) = x / ln(x)`, where `ln` is the natural logarithm. As such, we can compute an estimate of the expected number of primes below the highest value in an `n`-bit number by computing `π(2^n)`. If we want to exclude all numbers that aren't exactly `n`-bit, we compute `π(2^n) - π(2^(n-1))`. This isn't technically required, but it gives us a nice lower bound of how many large primes there are for that key size. For `n = 512` the number of primes required for an exhaustive list is 1.885×10151. If we can store every prime in a 512-bit entry, that's 1.207×10153 bytes, which is 132 orders of magnitude more than we have disk storage capacity in the world. So no, not really feasible. It's unlikely. The primes involved are huge, so the keyspace is massive. Just how massive depends on your key size, but let's pick 512-bit primes for a lower bound example. The prime counting function gives us an estimate of how many prime numbers are below a given number. It is defined as `π(x) = x / ln(x)`, where `ln` is the natural logarithm. As such, we can compute the expected number of primes below the highest value in an `n`-bit number by computing `π(2^n)`. If we want to exclude all numbers that aren't exactly `n`-bit, we compute `π(2^n) - π(2^(n-1))`. This isn't technically required, but it gives us a nice lower bound of how many large primes there are for that key size. For `n = 512` the number of primes required for an exhaustive list is 1.885×10151. If we can store every prime in a 512-bit entry, that's 1.207×10153 bytes, which is 132 orders of magnitude more than we have disk storage capacity in the world. So no, not really feasible. It's unlikely. The primes involved are huge, so the keyspace is massive. Just how massive depends on your key size, but let's pick 512-bit primes for a lower bound example. The prime counting function gives us an estimate of how many prime numbers are below a given number. It is difficult to compute precisely, but a close estimate is defined as `π(x) = x / ln(x)`, where `ln` is the natural logarithm. As such, we can compute an estimate of the expected number of primes below the highest value in an `n`-bit number by computing `π(2^n)`. If we want to exclude all numbers that aren't exactly `n`-bit, we compute `π(2^n) - π(2^(n-1))`. This isn't technically required, but it gives us a nice lower bound of how many large primes there are for that key size. For `n = 512` the number of primes required for an exhaustive list is 1.885×10151. If we can store every prime in a 512-bit entry, that's 1.207×10153 bytes, which is 132 orders of magnitude more than we have disk storage capacity in the world. So no, not really feasible. 2 added 152 characters in body edited Dec 10 '12 at 20:44 Polynomial 116k3737 gold badges259259 silver badges350350 bronze badges It's unlikely. The primes involved are huge, so the keyspace is massive. Just how massive depends on your key size, but let's pick 512-bit primes for a lower bound example. The prime counting function gives us an estimate of how many prime numbers are below a given number. It is defined as `π(x) = x / ln(x)`, where `ln` is the natural logarithm. As such, we can compute the expected number of primes below the highest value in an `n`-bit number by computing `π(2^n)`. If we want to exclude all numbers that aren't exactly `n`-bit, we compute `π(2^n) - π(2^(n-1))`. This isn't technically required, but it gives us a nice lower bound of how many large primes there are for that key size. For `n = 512` the number of primes required for an exhaustive list is 1.885×10151. If we can store every prime in a 4096512-bit entry, that's 9.653×10153 bytesthat's 1.207×10153 bytes, which is 132 orders of magnitude more than we have disk storage capacity in the world. So no, not really feasible. It's unlikely. The primes involved are huge, so the keyspace is massive. Just how massive depends on your key size, but let's pick 512-bit primes for a lower bound example. The prime counting function gives us an estimate of how many prime numbers are below a given number. It is defined as `π(x) = x / ln(x)`, where `ln` is the natural logarithm. As such, we can compute the expected number of primes below the highest value in an `n`-bit number by computing `π(2^n)`. If we want to exclude all numbers that aren't exactly `n`-bit, we compute `π(2^n) - π(2^(n-1))`. This isn't technically required, but it gives us a nice lower bound of how many large primes there are for that key size. For `n = 512` the number of primes required for an exhaustive list is 1.885×10151. If we can store every prime in a 4096-bit entry, that's 9.653×10153 bytes, which is 132 orders of magnitude more than we have storage capacity in the world. So no, not really feasible. It's unlikely. The primes involved are huge, so the keyspace is massive. Just how massive depends on your key size, but let's pick 512-bit primes for a lower bound example. The prime counting function gives us an estimate of how many prime numbers are below a given number. It is defined as `π(x) = x / ln(x)`, where `ln` is the natural logarithm. As such, we can compute the expected number of primes below the highest value in an `n`-bit number by computing `π(2^n)`. If we want to exclude all numbers that aren't exactly `n`-bit, we compute `π(2^n) - π(2^(n-1))`. This isn't technically required, but it gives us a nice lower bound of how many large primes there are for that key size. For `n = 512` the number of primes required for an exhaustive list is 1.885×10151. If we can store every prime in a 512-bit entry, that's 1.207×10153 bytes, which is 132 orders of magnitude more than we have disk storage capacity in the world. So no, not really feasible. 1 answered Dec 10 '12 at 20:38 Polynomial 116k3737 gold badges259259 silver badges350350 bronze badges It's unlikely. The primes involved are huge, so the keyspace is massive. Just how massive depends on your key size, but let's pick 512-bit primes for a lower bound example. The prime counting function gives us an estimate of how many prime numbers are below a given number. It is defined as `π(x) = x / ln(x)`, where `ln` is the natural logarithm. As such, we can compute the expected number of primes below the highest value in an `n`-bit number by computing `π(2^n)`. If we want to exclude all numbers that aren't exactly `n`-bit, we compute `π(2^n) - π(2^(n-1))`. This isn't technically required, but it gives us a nice lower bound of how many large primes there are for that key size. For `n = 512` the number of primes required for an exhaustive list is 1.885×10151. If we can store every prime in a 4096-bit entry, that's 9.653×10153 bytes, which is 132 orders of magnitude more than we have storage capacity in the world. So no, not really feasible.