Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As I read more and more about advanced mathematics, the more complex and obscure topics seem to be tougher to bend the rules of math to describe. However, the simple (and undoubtedly very useful) subject of prime number identification remains an enigma (to me, at least). For a system with rules so simple, calculation isn't. Even though the rules of the calculation change as larger and larger values are tested, because of additional primes to take into consideration when testing a given value, how is there not a computationally cheap and easy way of identifying primes? I've got pages and pages full of attempts to find patterns (with a knowledge base not too well suited for this sort of research), and as soon as I have a large enough value that I'm testing, the pattern falls apart in quite an ugly manner.

share|improve this question
1  
What about this? –  Zev Chonoles Nov 29 '11 at 5:11
1  
Wake me up when AKS becomes practical... –  J. M. Nov 29 '11 at 5:13
1  
You don't think it's practical? –  mixedmath Nov 29 '11 at 5:21
2  
If there were a computationally inexpensive way to factor numbers, then electronic money transactions would not be safe from thieves. (That of course does not explain why there is none.) Multiplying is easy and factoring is hard. –  Michael Hardy Nov 29 '11 at 5:27
1  
You might be interested in the paper Primes is in P. It's fairly advanced, but it might give you some other things to look up as you read. –  Austin Mohr Nov 29 '11 at 5:43
show 1 more comment

1 Answer 1

Depends on what you call "cheap and easy". Adleman-Pomerance-Rumely-Cohen-Lenstra and Elliptic Curve Primality testing have been used to prove primality of numbers (not of special form) with thousands of digits.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.