Rainbow table concept for Prime numbers

Question

Is there a concept where pre-computed tables can be used for prime number factorization ? Is it possible that a computer can generate millions of prime numbers, store it and then effectively determine the factors ?

Answer 1

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×10¹⁵¹. If we can store every prime in a 512-bit entry, that's 1.207×10¹⁵³ bytes, which is 132 orders of magnitude more than we have disk storage capacity in the world.

So no, not really feasible.

Answer 2

Rainbow table: each "color" takes a random input (the output hash of the last iteration or the original hash) and returns an output that maps to whatever pattern you wanted (e.g., all letters). That is then hashed and fed back to the input.

Because we can also specify a reduction function that takes any random string and deterministically maps it to whatever output pattern we want, this works for passwords. There is no definable function to take an input value and output a number that is known to be prime as a result, however.

Every number that isn't known to be prime because you've already tested it will need to be testeed for primeness. Thus, unless a number is stored as a known prime value, there is no time / memory tradeoff to be had.

Answer 3

What you're talking about here is not feasible. Crypto doesn't simply calculate large primes, you would need to factor the product of two primes.

What you'd need to do is compute millions of prime numbers and feed them into an insanely large array. Then you'd need to duplicate that array so you had two dimensional array. Then you would need to multiple every single entry in the first dimension against every single entry in the second dimension, and store the two primes and the result in a second array. This second array would be gigantic, and by gigantic I mean completely unable to be stored in any capacity, but it would hold your answers.

Answer 4

As already mentioned above, there isn't anywhere near the storage space required in the entire world. I'd wager that before we even get to that amount of storage, a quantum computer running Shor's algorithm (or a similar algorithm) will have nullified the need.