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 ?
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.
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.
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.
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.
Certainly not easy but... "where there is a will there is a way" IF you wanted all prime numbers from number 2--> 512bit in a table then all possible products then yes this would be unfeasably large. But lets go back and speculate as to why someone might want it. Just suppose someone has a scenario where they were using a pair of similar bit-length prime numbers to make a big number that would be difficult for others to factor to a pair of primes (sound familiar...?) Not all possible combinations of primes would be needed as only similar bit-lengths would be used. This dramatically reduces the table size. Anyway to be pedantic this would be a Rainbow Cube not table as this requires several dimensions. The ability to determine factrs of these large primes is certainly difficult as the memory-resident size of the cubes (when held in RAM for efficient analysis) is too large for a cheap PC, however there are certainly some large organisations who hold giant multidimensional structures of these kind of proportions (such as Google for their searches). It seems highly unlikley that there are not heavily resourced organisations out there who already have calculated and use such prime cubes. The difficulty of factoring the pair of primes is the "headline" difficulty for e.g. RSA, but don't underestimate the additionla difficulty produced by the step for generating the private key because it has a modular calc.