AKS質數測試
演算法 > 例子：n = 31為質數

若存在整數a > 0 且b > 1 ，令 n  =  ab ；則輸出「合數」。
    for ( b = 2; b < =  log2(n); b +  +  ){
      a = n1/b;
      If ( a是整數 ) 輸出「合數」;
    }
    // a = n1/2...n1/4 = {5.568, 3.141, 2.360}，計算結果不是整數
找出最小的 r 令 ordr(n) > log2(n)。
    nextR = True;
    r = 1;
    while ( nextR =  = True ) {
      r +  + ;
      nextR = False
      for ( k = 1;(!nextR) &&k ≤ log2(n); k +  +  ){
        nextR = (nk % r =  = 1 || nk % r =  = 0);
      }
    }
    // 計算結果為：r  =  29
若 對某些a ≤ r，1 < gcd(a,n) < n，輸出「合數」。
    for ( a = r; a > 1; a-- ){
      If ( 1 < gcd(a,n) < n ) 輸出「合數」;
    }
     
    // gcd(29,31) = 1, gcd(28,31) = 1, ..., gcd(2,31) = 1，計算結果為找不到符合的a使得1 < gcd(a,n) < n為真
若 n ≤ r, 輸出「質數」。
    If ( n ≤ r ) 輸出「質數」;
     
    // 31 > 29，計算結果n比r大
對 a  =  1 到  \scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor 的所有數，
     如果 (X + a)n≠ Xn + a (mod Xr − 1,n), 輸出「合數」。
     
    for ( a = 1; a ≤  \scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor , a +  +  )
      if ( ((X + a)n-(Xn + a)) % (Xr−1,n) ≠ 0 ) 輸出「合數」。
    }
     
    / *  *  * 
    (x + a)31 % (x29-1,31)
      = (((x + a)29 % (x29-1,31)) * (x + a)2 % 31) % (x29-1,31)
      = ((1 + a29 + 29a28x + (406 % 31)a27x2 + (3654 % 31)a26x3 + (23751 % 31)a25x4 + (118755 % 31)a24x5 + (475020 % 31)a23x6 + (1560780 % 31)a22x7 + (4292145 % 31)a21x8 + (10015005 % 31)a20x9 + (20030010 % 31)a19x10 + (34597290 % 31)a18x11 + (51895935 % 31)a17x12 + (67863915 % 31)a16x13 + (77558760 % 31)a15x14 + (77558760 % 31)a14x15 + (67863915 % 31)a13x16 + (51895935 % 31)a12x17 + (34597290 % 31)a11x18 + (20030010 % 31)a10x19 + (10015005 % 31)a9x20 + (4292145 % 31)a8x21 + (1560780 % 31)a7x22 + (475020 % 31)a6x23 + (118755 % 31)a5x24 + (23751 % 31)a4x25 + (3654 % 31)a3x26 + (406 % 31)a2x27 + 29ax28) * (a2 + 2ax + x2)) % (x29-1,31)
      = ((1 + a29 + 29a28x + 3a27x2 + 27a26x3 + 5a25x4 + 25a24x5 + 7a23x6 + 23a22x7 + 9a21x8 + 21a20x9 + 11a19x10 + 19a18x11 + 13a17x12 + 17a16x13 + 15a15x14 + 15a14x15 + 17a13x16 + 13a12x17 + 19a11x18 + 11a10x19 + 21a9x20 + 9a8x21 + 23a7x22 + 7a6x23 +  25a5x24 + 5a4x25 + 27a3x26 + 3a2x27 + 29ax28) * (a2 + 2ax + x2)) % (x29-1,31)
      = ((1 + 2 * 29 + 3) % 31)a2 + a31 + ((2 + 29) % 31)ax + ((29 + 2 * 1) % 31)a30x + x2 + ((3 + 2 * 29 + 1) % 31)a29x2 + ((27 + 2 * 3 + 29) % 31)a28x3 + ((5 + 2 * 27 + 3) % 31)a27x4 + ((25 + 2 * 5 + 27) % 31)a26x5 + ((7 + 2 * 25 + 5) % 31)a25x6 + ((23 + 2 * 7 + 25) % 31)a24x7 + ((9 + 2 * 23 + 7) % 31)a23x8 + ((21 + 2 * 9 + 23) % 31)a22x9 + ((11 + 2 * 21 + 9) % 31)a21x10 + ((19 + 2 * 11 + 21) % 31)a20x11 + ((13 + 2 * 19 + 11) % 31)a19x12 + ((17 + 2 * 13 + 19) % 31)a18x13 + ((15 + 2 * 17 + 13) % 31)a17x14 + ((15 + 2 * 15 + 17) % 31)a16x15 + ((17 + 2 * 15 + 15) % 31)a15x16 + ((13 + 2 * 17 + 15) % 31)a14x17 + ((19 + 2 * 13 + 17) % 31)a13x18 + ((11 + 2 * 19 + 13) % 31)a12x19 + ((21 + 2 * 11 + 19) % 31)a11x20 + ((9 + 2 * 21 + 11) % 31)a10x21 + ((23 + 2 * 9 + 21) % 31)a9x22 + ((7 + 2 * 23 + 9) % 31)a8x23 + ((25 + 2 * 7 + 23) % 31)a7x24 + ((5 + 2 * 25 + 7) % 31)a6x25 + ((27 + 2 * 5 + 25) % 31)a5x26 + ((3 + 2 * 27 + 5) % 31)a4x27 + ((29 + 2 * 3 + 27) % 31)a3x28
      = a31 + x2
     
    (x31 + a) % (x29-1,31) = a + x2
     
    (a31 + x2)-(a + x2) = a31-a
     
     {\sqrt {\varphi (r)}}\log _{2}(n)={\sqrt {28}}*\log _{2}(31)=26.215
     
    (131-1) % 31 = 0, (231-2) % 31 = 0, (331-3) % 31 = 0, ..., (2631-26) % 31 = 0，計算結果為找不到符合的a使得(X + a)n≠ Xn + a (mod Xr − 1,n)為真
     *  *  * /
輸出「質數」。
    31必為質數。