Does this mean as much as I think it does? Aren't most of our current cryptography schemes based on prime numbers taking time to calculate?
Finding random primes is easy, especially if you don't mind using methods which allow an extremely tiny probability of error [1] -- this is standard practice in cryptography.
Finding random big primes p and q is easy. Multiplying them together into a product r = pq is easy. RSA cryptosystem picks p and q when generating the key, multiplies them, then throws away original p and q values. Only r is stored in the key.
Cracking the RSA algorithm itself [2] is basically equivalent to turning r back into p and q.
RSA is based on the hardness of factoring an integer into a product of primes. I don't think this conjecture will lead to practical improvements in cryptography / cryptanalysis, at least not with respect to cryptosystems that are currently widely used.
[1] http://en.wikipedia.org/wiki/Primality_testing#Probabilistic...
[2] Of course, there are many more attack vectors on specific implementations of the RSA algorithm, like trying to gain information on the secret key by measuring time taken to encrypt a message, measuring heat/power consumption/electronic noise, taking advantage of implementations that use a poor source of randomness, hacking into the system where the private key is stored, or bribing/threatening a human with legitimate access to the private key (as covered in http://xkcd.com/538/).
This has not been proven. RSA encrypts by taking C=m^e (MOD N). The normal way of decrypting is to take C^d (MOD N), where d can be efficiently computed if you know the factors of N. However, all you need to do to decrypt C is to take the e`th root (mod n). It has not been shown that the ability to do so allows you to factor N.
In fact, it appears (after a few minutes of research, so someone please correct me if I'm wrong), that their is evidence that breaking RSA is easier than factoring [1]
[1]http://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf
For those wondering why then, it is news when a new largest prime is found: there are gradations of 'big'. The big primes used in cryptography have fewer than 1000 bits, or about 300 digits. That is not what one (nowadays) calls 'large' in the field of finding the largest prime. There, one laughs at numbers of a million digits (the largest known prime has 17,425,170 digits)
You can generally repeat a probabilistic test with different parameters to make the probability of a "false positive" prime number very tiny -- like .000 000 000 001 -- while still staying within the computational budget manageable on an ordinary computer (obviously, a practical Internet security scheme should be able to complete its computations in a second or two on a typical desktop, laptop, server, and smartphone).
So probabilistic tests are good enough for practical purposes, but you need a non-probabilistic test to get the false positive probability all the way down to zero. And you need to use a method that has zero percent false positive chance to claim a world record. The EFF-administered monetary prize for a record-breaking prime number, for example, requires "the primality proof must be a deterministic proof..." [1] So you can't use probabilistic methods.
Or is o̅(log⁷·⁵(n)) just infeasible for those sizes of numbers?
The basic principle is that if I take two large prime numbers, P1 and P2, and give you their product, Q, then it will take you a very long time to learn P1 and P2 unless I give you one of them.
It is actually very important that the hardness of that problem does not come from the difficulty of finding prime numbers. Which numbers are prime is a question that is independent of breaking any particular key, which means that if that were the source of hardness, you could reuse the work from breaking one key to break future keys, by storing a list of the prime numbers you calculated. This would be a Bad Thing.
There are a lot of misconceptions, in fact, about hardness, prime numbers, and factorization. People often assume that primality testing and factorization are equivalent, and that both are NP complete. In fact, PRIMES is known to be in P, and (the decision version of) integer factorization is probably not NP complete (it is in NP by way of PRIMES being in P), although it is not known if it is in P.
The twin prime conjecture posits that the limit is 2, i.e you can never exhaust pairs of consecutive primes with the smallest possible separation size.
If someone discovers a shortcut in factoring very large numbers, then it will have the attention of cryptographers.