## Complexity theory and prime numbers

Today, while avoiding work, I came across a paper (PDF format) proving that the primality of a number can be determined in polynomial computing time. As the Slashdot thread emphasizes, this does not weaken current cryptography schemes, since the algorithms merely determines if a number is prime, but not what the actual factors are.

I didn't understand much of the paper, since I haven't taken a college-level algebra class, but the entire field of complexity theory seems cool. For a good intro, check out the NP and P classes entry in the Wikipedia.