Reading through:
http://cacr.uwaterloo.ca/hac/
Chapter 1.3

It says that public key crypto uses trap door one-way functions, such as integer factorization.

Another site about it:
http://learncryptography.com/prime-factorization/

The main idea is that you multiply two primes together conventionally named 'p' and 'q' to get 'n'. Knowing 'n', it is a mathematically difficult problem to factor out 'p' and 'q'. However, I wonder if there isn't a shortcut. I mean in the applied crypto book it says that 'p' and 'q' are very large distinct prime numbers of about 100 decimals each. Given this restriction on 'p' and 'q', couldn't you just try to guess 'p' and 'q' without having to factor them from 'n' ? I mean try all prime numbers of 100 decimals length.

I've tried searching for numbers on if this is indeed a possible shortcut, but I can't seem to find anything.

Ok, so I found a table later in Chapter 1 that says there are 5.2 x 10 ^ 72 (5.2E72) 75-digit prime numbers. It is clearly not feasible to guess at 'p' and 'q' as this would probably take more time than factoring.

My impression is that there is, but the implementation of that shortcut needs a quantum computer. Is that correct?

After more reading, the main shortcuts are very fast factoring methods like quadratic sieve, number field sieve, and elliptic curve factoring.

In the book it says that if someone were able to build a quantum computer (currently just a theory and non-quantum prototypes) it would very likely shake up the world of cryptography, minus the one time pad. Really, all algorithms other than the one time pad are computationally secure, not unconditionally secure. As such, any huge jump in computing power or algorithmic efficiency would shake up the world of cryptography.

Have you read webpages about post quantum cryptography by tanja lane and djb.

They say symmetric cipher of strength 128bit and more (like aes-128, aes-256) are secure even if someone uses a quantum computer.

But todays all popularly used public cryptography are not safe.

But NTRU is safe plus few others.

I don't think AES is safe at all even now, but maybe other symmetric ciphers 256-bit key and up. It's true that symmetric ciphers are significantly (10 times) stronger than public key ciphers for the same bit length, that's why public key ciphers recommend 2048-bit key.

No. All AES(Rjindael), truefish, serpent 128 bit and above are quantum secure.

But todays public ciphers are not except some ones I already wrote.

This is because there is a sub-exponential method of factoring numbers, see Index calculus algorithm. By the way, "10 times" might be okay as a rule of thumb, but the relationship is not linear:

The index calculus method doesn't apply to elliptic curves, which is why typical sizes for ECC keys are between 192 to 512 bits.

Apparently, Grover's algorithm gives quadratic speedup so effectively the bit strength of the key is cut in half, i.e. aes-256 is okay (equivalent to aes-128 today) but aes-128 would be too small (64 bits is generally considered not enough).

And it always bears remembering that practical breaks into crypto systems usually come about from some exploitable flaw in key management, often by people. Intruders and are frequently content to be able to capture only a portion of the traffic on a communication link, vs. cracking a single message. Crypto is simply designed to make it sufficiently difficult to read a message, or the traffic on a particular link, quickly enough to do Eve any practical good. Theoretical discussions about "weaknesses" of a crypto system are often just that ... theoretical, not pragmatic.

Keys can still be stolen and people can still be lured into accepting a key that they shouldn't. It's still true that the weakest link in any crypto infrastructure is in-between two ears.

And the private key held by the other party can be demanded via court order.

... "and that's the way it goes, in civilized(?!?!) society."

Most of the time, cryptography serves as the all-important(!) digital equivalent of: "a postal envelope."

The information that is to be protected (let's face it ...) is not, actually, "a State Secret." It might simply be "nobody's business but yours.™" Nevertheless, you have a legitimate (and legal) business requirement that the information "is not being transmitted on a postcard," and that there is a credible technical support for the message's provenance and authenticity.

If a Court of Law presents you with a Search Warrant, then you, having done no wrong, will of course be quite happy to comply. Meanwhile, your archives and/or your transmissions require verifiable protection and "due diligence™" ... perhaps to comply with regulations such as (in the USA) Sarbanes-Oxeley, Securities laws, HIPAA, and so on. "Boring, but essential."

Cryptography is mostly boring . . . but essential.