zeroinfinity Posted May 3, 2011 Share Posted May 3, 2011 (edited) 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 Link to comment Share on other sites More sharing options...

DrRocket Posted May 3, 2011 Share Posted May 3, 2011 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 Link to comment Share on other sites More sharing options...

Shadow Posted May 4, 2011 Share Posted May 4, 2011 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. Link to comment Share on other sites More sharing options...

imatfaal Posted May 4, 2011 Share Posted May 4, 2011 Here is an easier explanation of Shor's algorithm by MIT's Scott Aaronson (nb the third comment!) Shtetl-Optimized Link to comment Share on other sites More sharing options...

DrRocket Posted May 4, 2011 Share Posted May 4, 2011 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. Link to comment Share on other sites More sharing options...

Shadow Posted May 5, 2011 Share Posted May 5, 2011 My bad, I just skimmed the post and missed that part. Link to comment Share on other sites More sharing options...

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now