Why is large prime factorization so hard?

[zeroinfinity]

One-way (trapdoor) functions are at the heart of some encryption schemes such as RSA and PGP. So far there is no known method or algorithm of factoring product of two large primes in polynomial time. Absent breakthroughs in quantum computing, a 4096bit RSA PGP key would take much longer than the known age of the universe to brute force, even with general number field sieve (GNFS) algorithm... <br /><br />As far as I know, no one has published anything either way that proves there cannot possibly be a way to factor in polynomial time (using conventional non-quantum computing techniques) nor has there been a proof that states there is or should/could be a way to factor in polynomial time. Basically it is a big unknown...<br /><br />Is there any literally or explanation that shed light on why and how it is so fundamentally different to factor the product of two very large and approximately equal length primes? Is there a law of mathematics or some sort of platonic barrier to strictly forbids there being a shortcut?

Edited May 3, 2011 by zeroinfinity

[DrRocket]

One-way (trapdoor) functions are at the heart of some encryption schemes such as RSA and PGP. So far there is no known method or algorithm of factoring product of two large primes in polynomial time. Absent breakthroughs in quantum computing, a 4096bit RSA PGP key would take much longer than the known age of the universe to brute force, even with general number field sieve (GNFS) algorithm... <br /><br />As far as I know, no one has published anything either way that proves there cannot possibly be a way to factor in polynomial time (using conventional non-quantum computing techniques) nor has there been a proof that states there is or should/could be a way to factor in polynomial time. Basically it is a big unknown...<br /><br />Is there any literally or explanation that shed light on why and how it is so fundamentally different to factor the product of two very large and approximately equal length primes? Is there a law of mathematics or some sort of platonic barrier to strictly forbids there being a shortcut?

 

I know of no proof that factorization in polynomial time is impossible. But no existing algorithm will do the trick either. Sieve methods are up against what is known about the distribution of prime numbers.

 

http://en.wikipedia.org/wiki/Integer_factorization

 

http://en.wikipedia.org/wiki/Prime_number_theorem

[Shadow]

So far there is no known method or algorithm of factoring product of two large primes in polynomial time.

 

Incorrect; have a look at Shor's algorithm, although it should be said that it's very technical.

[imatfaal]

Here is an easier explanation of Shor's algorithm by MIT's Scott Aaronson (nb the third comment!) Shtetl-Optimized

[DrRocket]

Incorrect; have a look at Shor's algorithm, although it should be said that it's very technical.

 

Incorrect. Shor's algorithm is a quantum algorithm, and quantum algorithms were specifically excluded in the OP.

[Shadow]

My bad, I just skimmed the post and missed that part.