New primality test algorithm found.

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

New primality test algorithm found.

Post 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.

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post 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?

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

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

wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

Post 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.

Post Reply

Return to “Other words”