(You may have omitted this detail on purpose, but I think it's worth pointing out) The example of trial division as a primality test is a good illustration of an algorithm that takes a lot of work to run but whose output is easy to verify. However, the problem of primality testing is actually in P. [1] You have to use a fancier algorithm than trial division in order to get polynomial time.
Hopefully you'd try another algorithm before you did that ;). Primality tests are one of the most highly understood and well documented areas of CS - trial division has been obsolete since, what, 1640?
That code is making an array of primes and iterating through it. It's just that the array is stored in instruction memory, and there is no explicit fiddling with indices or pointers.
As for more advanced primality testing methods, I guess it depends on where the the fancier algorithms begin to pay off. It would not surprise me if this simple algorithm was the fastest for any input small enough to be stored in a single machine word.
2) Mark all numbers of the form i times n as composite, where i
is a positive integer. (We can do this by stepping over multiples of n. No multiplication needs to take place.
3) The next unmarked number is prime. Let it be n. Goto 2
Notice how this alogorithm does not use division. Division in modern CPUs is slow.
The algorithm presented uses the `mod` operator, which does division. This algorithm is equivalent to the Trial Division Algorithm. Instead of "deleting" multiples of n as composite, this algorithm tests all numbers greater than n for divisibilty by n, and then only does it "delete" the number.
And your description makes little sense to me. I guess it is based on a bad understanding of RSA (http://en.wikipedia.org/wiki/RSA_%28algorithm%29). That does not convert your message to a prime.
The paper is quite straightforward and use only math from the first or second year of the university. If you understand the word "module" and have 15 minutes to loose, give it a try.
Ignoring the reference to unrelated results about prime numbers, the main idea is that to check if a number is prime:
1) First check the remainder modulo 10, modulo 9 and modulo 24. This part is correct, but it's suspicious that they waste a few pages to prove it. Anyone with a minimal background will agree with this part explained in a line.
2) They make a multiplication table "Q-grid" of the number that are not multiple of 2 nor 3. The idea is that after discarding the numbers with the bad remainder module 24, the rest of the numbers are not multiple of 2 nor 3. Again, it's suspicious that they give a long explanation and the use of invented names like "Quasi-primes"
3) To test if N is prime, they try to find in this table build looking first at the numbers nearby the x~=sqrt(N) and y~=sqrt(N) so x * y ~= N. It's not clear how they lookup in the table.
Being very optimistic, this is essentially like searching for a divisor of N up to sqrt(N). [I'm not sure that their implementation is not worse.] This search up to sqrt(N) is one of the first trick you learn to test primality. The advantage of their method is that they reduce the search space modulo 24 and they get the result in sqrt(N)/3 steps. [I'm not sure that their implementation is not worse.] This is slightly better than using only the odd numbers to get the result in sqrt(N)/2 steps.
For big enough numbers to be used in cryptography, this sqrt(N) or sqrt(N)/2 or sqrt(N)/3 is complete rubbish compared to any modern serious method, it's not even funny, I understand the uproar.
Some quotes:
> And because when we search for the prime factors of some semiprime number we need to remove the non-prime numbers from both axes of the Q-grid, like 25, 35, 49 etc., the problem will automatically reduce to simply locating the number in the Q-grid, with its horizontal and vertical projections on both axes being its prime factors.
I hope they are not trying to build the whole Q-grid. It uses more memory than a simple search. Also if they are keeping only the prime numbers, why all the discussion of using the remainder module 24. All big prime numbers have the correct remainder module 24.
> In fact, these two numbers, 2 and 3, contradict many of the primes properties such that some mathematicians consider them as sub-prime integers.
I never hear that.
Bad math joke: Did you notice that 2 is an odd prime number?
In essence, my reasoning was simply that primes don't behave like this. Any connection with addition-type stuff is spurious and doesn't go on forever.
Mind you, when I'd searched up to 10^5 and still hadn't found a counter-example I was starting to doubt my intuition. The first counter-example is when the sequence predicts that 521^2 is prime.
In fact, if p is prime then p divides k(p). I find that non-obvious, but do follow and believe the proof. Even so, I don't know it well enough to feel enlightened by it.
Performing a Miller-Rabin primality test or filling a Sieve of Eratosthenes will almost always be the way to go. However, this line of code seems like magic and that's kind of impressive.
I believe they actually have very optimized algorithms to test for primality [0], which not necessarily involve diving by every possible number.
There are simple tests and there are more complex ones, that use probabilities and other workarounds to avoid having to divide by every possible number.
Essentially, although it looks complicated, it's the simplest possible idea: it's just trying factorisations, with the `(11+?)` part being the factor, and the `\1+` part insisting that we repeat that factor. It is of course wildly inefficient, and limitations in the backtracking engine mean that it can give false positives for large numbers (http://zmievski.org/2010/08/the-prime-that-wasnt, also linked from that post).
It is a proven deterministic test of primality. We already had those before AKS, and they are significantly faster than AKS (even the various improvements). But they don't check all the boxes that are useful for stating things in computational complexity proofs without a paragraph of weasel words. So from the theory side of things, it's great since we don't particularly care about the actual execution time, but the asymptotic behavior and whether it is solidly shown to be in P.
Lots of math packages have deterministic primality tests, but none use AKS as a primary method, because AKS offers no benefits over other methods and is many orders of magnitude slower.
For inputs of special form, there are various fast tests. E.g. Mersenne numbers, Proth numbers, etc.
The fastest method depends on the input size and how much work you want to put in. For tiny inputs, say less than 1M, trial division is typically fastest. For 32-bit inputs, a hashed single Miller-Rabin test is fastest. For 64-bit inputs, BPSW is fastest (debatable vs. hashed 2/3 test). The BLS methods from 1975 are significantly faster than AKS up to at least 80 digits, but ECPP and APR-CL easily beat those. ECPP is the method of choice for 10k+ digit numbers, with current records a little larger than 30k digits.
"On my machine, testing the prime number 27,644,437 took about 1.2 milliseconds with a k value of 50 (far higher than you’ll probably need for your applications.)"
I'm sorry, but WHAT?
Writing the dumbest implementation of trial-division that I could, in C++ on my laptop, in Debug mode, took 0.0247046 ms to determine definitively if 27,644,437 is prime.
My dumbest-possible implementation, in Debug mode, is 48.5 times faster, and doesn't get confused by Carmichael numbers.
Move along, folks, nothing to see here.
"The trial-division method... gets slow quickly."
That may be true, but using the number 27,644,437 as a benchmark will not get you anywhere near that "slow" point.
reply