[Ilugc] .a-tip-a-day. (cksum utility in OpenBSD)

  • From: vinnytryclyst@xxxxxxxxx (Vinod Parthasarathy)
  • Date: Mon Nov 16 10:58:54 2009

2009/11/16 Kapil Hari Paranjape <kapil@xxxxxxxxxxx>

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-request@xxxxxxxxxxxxx with
"unsubscribe <password> <address>"
in the subject or body of the message.
http://www.ae.iitm.ac.in/mailman/listinfo/ilugc

Other related posts:

  1. Home
  2. ilugc
  3. Archive
  4. 11-2009