The algorithm that caught my interest was the Agrawal-Kayal-Saxena primality test (also know as the AKS primality test or the cyclotomic AKS test). This test falls within the category of primality tests, which are used primarily in cryptography (wiki). The creators of the AKS primality test are Manendra Agrawal, Neeraj Kayal, and Nitin Saxena (“AKS Primality test”). These three created an algorithm by looking at a simple problem and found a simple answer (Tao, “The AKS primality test.”). This algorithm is the first to satisfy all four requirements (general, polynomial, deterministically and unconditional which I will talk about later) for a primality test (“AKS Primality test”). This algorithm is a great example that can be applied to having many algorithms that compute the same talks within a different amount of time (page 79, Hillis).
A great example about how there are different algorithms to accomplish the same task is the sock algorithm from chapter five of The Pattern on the Stone by W. Daniel Hillis. The way that the sock algorithm works is to help someone sort their clean socks, within the book two different methods are shown. The first is by pulling one sock out of the pile and comparing each and every sock to that first one. If the two socks don’t match then the second sock gets tossed back into the pile of clean laundry. This is repeated until all socks have been matched. In the second scenario one sock is pulled from the pile and placed aside, then another sock is selected to be compared to the first and if they don’t match it is placed next to the first. By sorting socks by this second example the chore time of sock pairing is greatly reduced. This is the same way that a lot of the tests within the primality area work. There are some algorithms that require a lot more time to be run to accomplish the same or a similar task.
As I stated before, the AKS primality test falls into the Primality test category. The AKS is currently the only primality test to achieve all four criteria (general, polynomial, deterministically, and unconditional) (“AKS primality test”). By having an algorithm that satisfies the general classification the number is not required to be a certain type or contain certain properties. In the polynomial classification the output is displayed in a polynomial of run time and will accept any input. The third classification is deterministically, which states what the output is and does not place any sort of probability on the likely hood that the answer is or is not a prime number. The fourth and final classification for primality tests is unconditional. In this classification if the algorithm is supported by a yet unproven theorem or hypothesis then that theorem is considered conditional since the algorithm could become false if the hypothesis is proven wrong. An example of a conditional algorithm is the Miller’s test. The Miller’s test is supported by the yet proven generalized Riemann’s Hypothesis, which if disproven will mean that the Miller’s test and Miller-Rabin primality test are both untrue.
There are other tests (algorithms) within the Primality tests category that accomplish the same thing in similar or different ways. The first way is the Fermat primality test. While this test is classified under the primality tests it would actually be better off in a separate category titled composite tests. The way that the Fermat primality test works is to look and see what numbers can be combined to get the input value. Two other tests located in the Primality test field but would do better as composite tests are the Miller-Rabin and Solovay-Strassen primality tests (“Primality test”). These two tests also look at the inputs as what numbers can be multiplied together to get the input rather than looking to see if the inputted value is divisible by any other numbers besides itself and one. The fourth test is the Forbenius primality test and it is more accurate at seeing what numbers are prime but is a much slower algorithm than the previous two (“Primality test”). The Forbenius primality test is a primality test not a composite test. Another difference between this one and the previous examples is the Forbenius has no counterexample.
Hillis, W. Daniel. “The Algorithmic Guarantee.” The Pattern on the Stone: The Simple Ideas That Make Computers Work. New York: Basic, 1998. 78-79. Print.
Hillis, W. Daneil. “Algorithms and Heuristics.” The Pattern on the Stone: The Simple Ideas That Make Computers Work. New York: Basic, 1998. 77-78. Print.
“AKS Primality Test.” Wikipedia. Wikimedia Foundation. n.d. Web. 19 Sept. 2016.
“Primality Test.” Wikipedia. Wikimedia Foundation. n.d. Web. 19 Sept 2016.
Tao, Terence. “The AKS Primality Test.” Whtats New. WordPress, 23 Feb. 2011. Web. 19 Sept. 2016.