Date Added: Apr 2010
Public key cryptography has several practical applications, for example in e-commerce systems for authentication (electronic signatures) and for secure communication. The most widely used cryptosystems RSA and ECC (elliptic curve cryptosystems) are based on the problems of integer factorisation and discrete logarithm respectively. Integer factorisation and discrete logarithm problems are only believed to be hard but no proof is known for their NPcompleteness or NP-hardness. Improvements in factorisation algorithms and computation power demand larger bit size in RSA key which makes RSA less efficient for practical applications. Although RSA and ECC have some drawbacks, they are still not broken. But in 1999 Peter Shor discovered the polynomial time algorithm for integer factorization and computation of discrete logarithm on quantum computers.