2009/11/16 Kapil Hari Paranjape <ka...@imsc.res.in> > Hello, > > On Mon, 16 Nov 2009, Girish Venkatachalam wrote: > > Basically RSA relies on the NP complete problem of prime number > > factorization and Diffie Hellman relies on discrete log problem. > > First of all, I should clarify that my aim is not to try to prove > anyone wrong. However, when a statement is made on a public channel > that is used by newbies and this statement may (IMNSHO!) mislead some > of them, I feel that it should be corrected. > > The case in point: factorisation is not known to be an NP complete > problem. > > However, people who study algorithms do believe that it is > unlikely that there is a P algorithm for factorisation. >
I would like to add to what Prof. Kapil has said here. Factorisation is known to be in both NP and co-NP complexity classes. If it could be proved that factorisation is either NP-complete or co-NP-complete, then that means that NP = co-NP. This would be a very surpising result in complexity theory, and hence it is widely believed that factorisation is neither NP-complete nor co-NP-complete. > > A P algorithm for factorisation is one which will factorise a large > number N in log(N)^k steps for some fixed k (independent of N). > Actually, O((log N) ^ k) is the correct notation. Vinod. > > Regards, > > Kapil. > -- > > _______________________________________________ > To unsubscribe, email ilugc-requ...@ae.iitm.ac.in with > "unsubscribe <password> <address>" > in the subject or body of the message. > http://www.ae.iitm.ac.in/mailman/listinfo/ilugc > _______________________________________________ To unsubscribe, email ilugc-requ...@ae.iitm.ac.in with "unsubscribe <password> <address>" in the subject or body of the message. http://www.ae.iitm.ac.in/mailman/listinfo/ilugc
