0

Its right there in the question. I'm just interested in the subject. Has it been shown that you will always need brute computation to know if a number is prime?

jwillis0720
  • 131
  • 1
    No, there are much faster algorithms for testing primality. Look up "PRIMES is in P" for one such algorithm. – Alex Becker Mar 25 '14 at 07:30
  • 2
    Quantum computers, coupled with Shor's Algorithm (http://en.wikipedia.org/wiki/Shor's_algorithm) determines the primality of a number in polynomial time. Mersenne Primes can be tested for using a specialized test (the Lucas-Lehmer primality test : http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test) which performs a lot faster than brute force. – Yiyuan Lee Mar 25 '14 at 07:31
  • 3
    @YiyuanLee Although quantum computers aren't even necessary, the AKS primality test is polynomial time as well. – Alex Becker Mar 25 '14 at 07:33
  • 1
    Is it common to refer to primality checking as "solving" primes? – anon Mar 25 '14 at 07:34
  • No, I'm not a mathematician - what should I say? Factoring Primes? – jwillis0720 Mar 25 '14 at 07:43
  • I guess I should of asked...Will there ever be a pattern in numbers that allows you to predict where all the primes will be. Esoteric i know. – jwillis0720 Mar 25 '14 at 07:44
  • You should say "checking". Note that checking whether an individual number is prime is a very different problem than finding a list of consecutive primes; for that you want a sieve method. – Alex Becker Mar 25 '14 at 07:53

1 Answers1

1

There are two very different concepts here. One is proving that a number is prime. The other is factorisation if it isn't prime. The second is much harder and is the foundation of encryption algorithms.

Most of the primality tests and factorizations are NOT based on trial division: prime testing is usually based on the Fermat's little theorem, and the trick behind different tests is how to select which numbers to put into $a^p=a\mod p$ and how to avoid "fake primes" that aren't primes but satisfy the identity.

There are a lot of fast prime testing algorithms that are probabilistic: if they say the number isn't prime, it really isn't, or they say it's a probable prime (but they can't be sure). For instance, checking Fermat's little theorem for a couple of random $a$ is pretty good, but not exact. Miller Rabin's and Pollard's Rho (also factorizes the result) are like that. On the other hand, you have AKS test (very recently discovered, I remember when it was published) that is actually exact and runs in polynomial time.

And of course there is the Shor's algorithm for quantum computers, but that's a whole different mechanism of "cheating" the time complexity by computing many options at the same time (not possible classically).

So it really depends on what you mean by "brute force". It certainly isn't trivial to prove primality, and it's much harder to factorize a number, but I wouldn't call our current algorithms brute-force. They definitely take into account known theorems to make work easier.

orion
  • 15,781