3
$\begingroup$

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.

  • 1
    What about [this](http://en.wikipedia.org/wiki/AKS_primality_test)?2011-11-29
  • 1
    Wake me up when AKS becomes practical...2011-11-29
  • 1
    You don't think it's practical?2011-11-29
  • 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.2011-11-29
  • 0
    @MichaelHardy interesting. I had actually just gotten done reading [this](http://math.stackexchange.com/questions/7377/why-are-very-large-prime-numbers-important-in-cryptography), which is partially how I came to be interested in the "why".2011-11-29
  • 1
    You might be interested in the paper [Primes is in P](http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf). It's fairly advanced, but it might give you some other things to look up as you read.2011-11-29

1 Answers 1