39 lines
2.2 KiB
Plaintext
39 lines
2.2 KiB
Plaintext
The [http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf AKS algorithm] for testing whether a number is prime is a polynomial-time algorithm based on an elementary theorem about Pascal triangles.
|
|
|
|
The theorem on which the test is based can be stated as follows:
|
|
|
|
* a number <big><big><math>p</math></big></big> is prime if and only if all the coefficients of the polynomial expansion of
|
|
::: <big><big><math>(x-1)^p - (x^p - 1)</math></big></big>
|
|
are divisible by <big><big><math>p</math>.</big></big>
|
|
|
|
|
|
;Example:
|
|
Using <big><big><math>p=3</math>:</big></big>
|
|
|
|
<big><big>(x-1)^3 - (x^3 - 1)
|
|
= (x^3 - 3x^2 + 3x - 1) - (x^3 - 1)
|
|
= -3x^2 + 3x</big></big>
|
|
|
|
|
|
And all the coefficients are divisible by '''3''', so '''3''' is prime.
|
|
|
|
|
|
{{alertbox|#ffe4e4|'''Note:'''<br/>This task is '''not''' the AKS primality test. It is an inefficient exponential time algorithm discovered in the late 1600s and used as an introductory lemma in the AKS derivation.}}
|
|
|
|
|
|
;Task:
|
|
|
|
|
|
# Create a function/subroutine/method that given <big><big><math>p</math></big></big> generates the coefficients of the expanded polynomial representation of <big><big><math>(x-1)^p</math>.</big></big>
|
|
# Use the function to show here the polynomial expansions of <big><big><math>(x-1)^p</math></big></big> for <big><big><math>p</math></big></big> in the range '''0''' to at least '''7''', inclusive.
|
|
# Use the previous function in creating another function that when given <big><big><math>p</math></big></big> returns whether <big><big><math>p</math></big></big> is prime using the theorem.
|
|
# Use your test to generate a list of all primes ''under'' '''35'''.
|
|
# '''As a stretch goal''', generate all primes under '''50''' (needs integers larger than 31-bit).
|
|
|
|
|
|
;References:
|
|
* [https://en.wikipedia.org/wiki/AKS_primality_test Agrawal-Kayal-Saxena (AKS) primality test] (Wikipedia)
|
|
* [http://www.youtube.com/watch?v=HvMSRWTE2mI Fool-Proof Test for Primes] - Numberphile (Video). The accuracy of this video is disputed -- at best it is an oversimplification.
|
|
<br><br>
|
|
|