Page 1 of 1
New primality test algorithm found.
Posted: Wed Aug 21, 2002 2:31 pm
by AlexandreN
http://www.cse.iitk.ac.in/primality.pdf
This is a polynomial time algorithm to test if a number is prime.
Good work.
Posted: Fri Aug 23, 2002 6:18 pm
by wyvmak
yes, i have heard that before.
but i would like to know, to clarify my confusion, was primality testing originally thought as P or NP? as testing every number smaller than n, just O(n), isn't it?
Posted: Fri Sep 06, 2002 10:35 am
by Caesum
re P/NP: you are thinking of factorisation, primality testing is a different problem
Posted: Sat Oct 12, 2002 12:50 am
by wsarzynski
P/NP
Complexity for problems is measured with
maximum number of operations for given size of input.
For primality size of input is number of digits.
Its quite easy to prove that primality is in NP and in coNP,
so if it would be NP-complete then P=NP.
Also note that P is subset of NP.