New primality test algorithm found.

AlexandreN · Post by **AlexandreN** » Wed Aug 21, 2002 2:31 pm

http://www.cse.iitk.ac.in/primality.pdf

This is a polynomial time algorithm to test if a number is prime.

Good work.

wyvmak · Post by **wyvmak** » Fri Aug 23, 2002 6:18 pm

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?

Caesum · Post by **Caesum** » Fri Sep 06, 2002 10:35 am

re P/NP: you are thinking of factorisation, primality testing is a different problem

wsarzynski · Post by **wsarzynski** » Sat Oct 12, 2002 12:50 am

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.