Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
AKS primality test
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==The algorithm== The algorithm is as follows:<ref name="AKS" /> : Input: integer {{math|''n'' > 1}}. # Check if ''n'' is a [[perfect power]]: if {{math|1=''n'' = ''a''<sup>''b''</sup>}} for integers {{math|''a'' > 1}} and {{math|''b'' > 1}}, then output ''composite''. # Find the smallest ''r'' such that {{math|[[multiplicative order|ord]]<sub>''r''</sub>(''n'') > (log<sub>2</sub> ''n'')<sup>2</sup>}}. If ''r'' and ''n'' are not coprime, then output ''composite''. # For all 2 β€ ''a'' β€ min (''r'', ''n''β1), check that ''a'' does not divide ''n'': If ''a''|''n'' for some 2 β€ ''a'' β€ min (''r'', ''n''β1), then output ''composite''. # If ''n'' β€ ''r'', then output ''prime''. # For {{math|1=''a'' = 1}} to <math>\left\lfloor \sqrt{\varphi(r)}\log_2(n) \right\rfloor</math> do #: if (''X''+''a'')<sup>''n''</sup> β ''X''<sup>''n''</sup>+''a'' (mod ''X''<sup>''r''</sup> β 1,''n''), then output ''composite''; # Output ''prime''. Here [[multiplicative order|ord]]<sub>''r''</sub>(''n'') is the [[multiplicative order]] of ''n'' [[modular arithmetic|modulo]] ''r'', log<sub>2</sub> is the [[binary logarithm]], and <math>\varphi(r)</math> is [[Euler's totient function]] of ''r''. Step 3 is shown in the paper as checking 1 < gcd(''a'',''n'') < ''n'' for all ''a'' β€ ''r''. It can be seen this is equivalent to trial division up to ''r'', which can be done very efficiently without using [[greatest common divisor|gcd]]. Similarly the comparison in step 4 can be replaced by having the trial division return ''prime'' once it has checked all values up to and including <math>\left\lfloor \sqrt{n} \right\rfloor.</math> Once beyond very small inputs, step 5 dominates the time taken. The essential reduction in complexity (from exponential to polynomial) is achieved by performing all calculations in the finite ring : <math>R = (\mathbb Z/n\mathbb Z)[X]/(X^r -1)</math> consisting of <math>n^r</math> elements. This ring contains only the <math>r</math> [[monomial]]s <math>\{X^0,X^1,\ldots,X^{r-1}\} </math>, and the [[coefficient]]s are in <math>\mathbb Z/n\mathbb Z</math> which has <math>n</math> elements, all of them codable within <math>\log_2(n)</math> bits. Most later improvements made to the algorithm have concentrated on reducing the size of ''r,'' which makes the core operation in step 5 faster, and in reducing the size of ''s'', the number of loops performed in step 5.<ref name="bernstein03">Daniel J. Bernstein, "[https://cr.yp.to/papers/aks.pdf Proving Primality After Agrawal-Kayal-Saxena]", version of January 25, 2003.</ref> Typically these changes do not change the computational complexity, but can lead to many orders of magnitude less time taken; for example, Bernstein's final version has a theoretical speedup by a factor of over 2 million. ===Proof of validity outline=== For the algorithm to be correct, all steps that identify ''n'' must be correct. Steps 1, 3, and 4 are trivially correct, since they are based on direct tests of the divisibility of ''n''. Step 5 is also correct: since (2) is true for any choice of ''a'' coprime to ''n'' and ''r'' if ''n'' is prime, an inequality means that ''n'' must be composite. The difficult part of the proof is showing that step 6 is true. Its proof of correctness is based on the upper and lower bounds of a [[multiplicative group]] in <math>\mathbb{Z}_{n}[x]</math> constructed from the (''X'' + ''a'') binomials that are tested in step 5. Step 4 guarantees that these binomials are <math>\left\lfloor \sqrt{\varphi(r)}\log_2(n) \right\rfloor</math> distinct elements of <math>\mathbb{Z}_n[x]</math>. For the particular choice of ''r'', the bounds produce a [[proof by contradiction|contradiction]] unless ''n'' is prime or a power of a prime. Together with the test of step 1, this implies that ''n'' is always prime at step 6.<ref name="AKS"/> ===Example 1: ''n'' = 31 is prime=== {{pre|style=white-space:pre;overflow:auto; |1=<nowiki/> '''Input''': integer ''n'' = 31 > 1. <u>(* Step 1 *)</u> '''If''' (''n'' = ''a''<sup>''b''</sup> for integers ''a'' > 1 and ''b'' > 1), '''output''' ''composite''. '''For''' ( b = 2; b <= log<sub>2</sub>(n); b++) { a = n<sup>1/b</sup>; '''If''' (a is integer), '''Return'''[Composite] } a = n<sup>1/2</sup>...n<sup>1/4</sup> = {5.568, 3.141, 2.360} <u>(* Step 2 *)</u> Find the smallest ''r'' such that ''O''<sub>''r''</sub>(''n'') > (log<sub>''2''</sub> ''n'')<sup>2</sup>. maxk = β(log<sub>''2''</sub> n)<sup>2</sup>β; maxr = Max[3, β(Log<sub>''2''</sub> n)<sup>5</sup>β]; <u>(* maxr really isn't needed *)</u> nextR = True; '''For''' (r = 2; nextR && r < maxr; r++) { nextR = False; '''For''' (k = 1; (!nextR) && k ≤ maxk; k++) { nextR = (Mod[n<sup>k</sup>, r] == 1 {{!!}} Mod[n<sup>k</sup>, r]==0) } } r--; <u>(*the loop over increments by one*)</u> r = 29 <u>(* Step 3 *)</u> '''If''' (1 < [[greatest common divisor|gcd]](''a'',''n'') < ''n'' for some ''a'' β€ ''r''), '''output''' ''composite''. '''For''' (a = r; a > 1; a--) { '''If''' ((gcd = GCD[a,n]) > 1 && gcd < n), '''Return'''[Composite] } gcd = {GCD(29,31)=1, GCD(28,31)=1, ..., GCD(2,31)=1} β― 1 <u>(* Step 4 *)</u> '''If''' (''n'' β€ ''r''), '''output''' ''prime''. '''If''' (n ≤ r), '''Return'''[Prime] <u>(* this step may be omitted if n > 5690034 *)</u> 31 > 29 <u>(* Step 5 *)</u> '''For''' ''a'' = 1 '''to''' <math>\left\lfloor\sqrt{\varphi(r)}\log_2(n)\right\rfloor</math> '''do''' '''If''' ((''X''+''a'')<sup>''n''</sup> β ''X''<sup>''n''</sup> + ''a'' (mod ''X''<sup>''r''</sup> β 1,''n'')), '''output''' ''composite''; Ο[x_] := EulerPhi[x]; PolyModulo[f_] := PolynomialMod<nowiki>[</nowiki>[[polynomial remainder|PolynomialRemainder]][f, x<sup>r</sup>-1, x], n]; max = Floor[Log[2, n]{{sqrt|Ο[r]}}]; '''For''' (a = 1; a β€ max; a++) { '''If''' (PolyModulo[(x+a)<sup>n</sup> - PolynomialRemainder[x<sup>n</sup>+a, x<sup>r</sup>-1], x] β 0) { '''Return'''[Composite] { } (x+a)<sup>31</sup> = a<sup>31</sup> +31a<sup>30</sup>x +465a<sup>29</sup>x<sup>2</sup> +4495a<sup>28</sup>x<sup>3</sup> +31465a<sup>27</sup>x<sup>4</sup> +169911a<sup>26</sup>x<sup>5</sup> +736281a<sup>25</sup>x<sup>6</sup> +2629575a<sup>24</sup>x<sup>7</sup> +7888725a<sup>23</sup>x<sup>8</sup> +20160075a<sup>22</sup>x<sup>9</sup> +44352165a<sup>21</sup>x<sup>10</sup> +84672315a<sup>20</sup>x<sup>11</sup> +141120525a<sup>19</sup>x<sup>12</sup> +206253075a<sup>18</sup>x<sup>13</sup> +265182525a<sup>17</sup>x<sup>14</sup> +300540195a<sup>16</sup>x<sup>15</sup> +300540195a<sup>15</sup>x<sup>16</sup> +265182525a<sup>14</sup>x<sup>17</sup> +206253075a<sup>13</sup>x<sup>18</sup> +141120525a<sup>12</sup>x<sup>19</sup> +84672315a<sup>11</sup>x<sup>20</sup> +44352165a<sup>10</sup>x<sup>21</sup> +20160075a<sup>9</sup>x<sup>22</sup> +7888725a<sup>8</sup>x<sup>23</sup> +2629575a<sup>7</sup>x<sup>24</sup> +736281a<sup>6</sup>x<sup>25</sup> +169911a<sup>5</sup>x<sup>26</sup> +31465a<sup>4</sup>x<sup>27</sup> +4495a<sup>3</sup>x<sup>28</sup> +465a<sup>2</sup>x<sup>29</sup> +31ax<sup>30</sup> +x<sup>31</sup> PolynomialRemainder [(x+a)<sup>31</sup>, x<sup>29</sup>-1] = 465a<sup>2</sup> +a<sup>31</sup> +(31a+31a<sup>30</sup>)x +(1+465a<sup>29</sup>)x<sup>2</sup> +4495a<sup>28</sup>x<sup>3</sup> +31465a<sup>27</sup>x<sup>4</sup> +169911a<sup>26</sup>x<sup>5</sup> +736281a<sup>25</sup>x<sup>6</sup> +2629575a<sup>24</sup>x<sup>7</sup> +7888725a<sup>23</sup>x<sup>8</sup> +20160075a<sup>22</sup>x<sup>9</sup> +44352165a<sup>21</sup>x<sup>10</sup> +84672315a<sup>20</sup>x<sup>11</sup> +141120525a<sup>19</sup>x<sup>12</sup> +206253075a<sup>18</sup>x<sup>13</sup> +265182525a<sup>17</sup>x<sup>14</sup> +300540195a<sup>16</sup>x<sup>15</sup> +300540195a<sup>15</sup>x<sup>16</sup> +265182525a<sup>14</sup>x<sup>17</sup> +206253075a<sup>13</sup>x<sup>18</sup> +141120525a<sup>12</sup>x<sup>19</sup> +84672315a<sup>11</sup>x<sup>20</sup> +44352165a<sup>10</sup>x<sup>21</sup> +20160075a<sup>9</sup>x<sup>22</sup> +7888725a<sup>8</sup>x<sup>23</sup> +2629575a<sup>7</sup>x<sup>24</sup> +736281a<sup>6</sup>x<sup>25</sup> +169911a<sup>5</sup>x<sup>26</sup> +31465a<sup>4</sup>x<sup>27</sup> +4495a<sup>3</sup>x<sup>28</sup> ({{EquationRef|A}}) PolynomialMod [PolynomialRemainder [(x+a)<sup>31</sup>, x<sup>29</sup>-1], 31] = a<sup>31</sup>+x<sup>2</sup> ({{EquationRef|B}}) PolynomialRemainder [x<sup>31</sup>+a, x<sup>29</sup>-1] = a+x<sup>2</sup> ({{EquationNote|A}}) - ({{EquationNote|B}}) = a<sup>31</sup>+x<sup>2</sup> - (a+x<sup>2</sup>) = a<sup>31</sup>-a <math>\max = \left\lfloor\log_2 (31) \sqrt{\varphi(29)} \right\rfloor = 26</math> {1<sup>31</sup>-1 = 0 (mod 31), 2<sup>31</sup>-2 = 0 (mod 31), 3<sup>31</sup>-3 = 0 (mod 31), ..., 26<sup>31</sup>-26 = 0 (mod 31)} <u>(* Step 6 *)</u> '''Output''' ''prime''. {{samp|31 Must be Prime}} }} Where PolynomialMod is a term-wise modulo reduction of the polynomial. e.g. PolynomialMod[x+2x<sup>2</sup>+3x<sup>3</sup>, 3] = x+2x<sup>2</sup>+0x<sup>3</sup> <ref>See [[Talk:AKS primality test#Worked Example|AKS Talk]] page for a discussion on why 'Example 2: n is not Prime past Step 4' is missing.</ref>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)