AKS test for primes

Manindra Agrawal & Neeraj Kayal & Nitin Saxena present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.

The AKS algorithm for testing whether a number is prime is a polynomial-time algorithm based on an elementary theorem about Pascal triangles.

Rust

1

use std::iter::repeat;
 
fn aks_coefficients(k: usize) -> Vec<i64> {
    let mut coefficients = repeat(0i64).take(k + 1).collect::<Vec<_>>();
    coefficients[0] = 1;
    for i in 1..(k + 1) {
        coefficients[i] = -(1..i).fold(coefficients[0], |prev, j|{
            let old = coefficients[j];
            coefficients[j] = old - prev;
            old
        });
    }
    coefficients
}
 
fn is_prime(p: usize) -> bool {
    if p < 2 {
        false
    } else {
        let c = aks_coefficients(p);
        (1 .. (c.len() - 1) / 2 + 1).all(|i| (c[i] % (p as i64)) == 0)
    }
}
 
fn main() {
    for i in 0..8 {
        println!("{}: {:?}", i, aks_coefficients(i));
    }
    for i in (1..51).filter(|&i| is_prime(i)) {
        print!("{} ", i);
    }
}

2

An alternative version which computes the coefficients in a more functional but less efficient way.

fn aks_coefficients(k: usize) -> Vec<i64> {
	if k == 0 {
		vec![1i64]
	} else {
		let zero = Some(0i64);
		(1..k).fold(vec![1i64, -1], |r, _| {
			let a = r.iter().chain(zero.iter());
			let b = zero.iter().chain(r.iter());
			a.zip(b).map(|(x, &y)| x-y).collect()
		})
	}
}
 
fn is_prime(p: usize) -> bool {
    if p < 2 {
        false
    } else {
        let c = aks_coefficients(p);
        (1 .. (c.len() - 1) / 2 + 1).all(|i| (c[i] % (p as i64)) == 0)
    }
}
 
fn main() {
    for i in 0..8 {
        println!("{}: {:?}", i, aks_coefficients(i));
    }
    for i in (1..51).filter(|&i| is_prime(i)) {
        print!("{} ", i);
    }
}

Java

public class AksTest {
	
    private static final long[] c = new long[64];
    
    public static void main(String[] args) {
        for (int n = 0; n < 10; n++) {
            coeff(n);
            show(n);
        }
 
        System.out.print("Primes:");
        for (int n = 1; n < c.length; n++)
            if (isPrime(n))
                System.out.printf(" %d", n);
 
        System.out.println();
    }    
 
    static void coeff(int n) {
        c[0] = 1;
        for (int i = 0; i < n; c[0] = -c[0], i++) {
            c[1 + i] = 1;
            for (int j = i; j > 0; j--)
                c[j] = c[j - 1] - c[j];
        }
    }
 
    static boolean isPrime(int n) {
        coeff(n);
        c[0]++;
        c[n]--;
 
        int i = n;
        while (i-- != 0 && c[i] % n == 0)
            continue;
        return i < 0;
    }
 
    static void show(int n) {
        System.out.print("(x-1)^" + n + " =");
        for (int i = n; i >= 0; i--) {
            System.out.print(" + " + c[i] + "x^" + i);
        }
        System.out.println();
    }
}

JavaScript

Translation of: C

function coef(n) {
 	for (var c=[1], i=0; i<n; c[0]=-c[0], i+=1) {
		c[i+1]=1; for (var j=i; j; j-=1) c[j] = c[j-1]-c[j]		
	}
	return c
}
 
function show(cs)	{
	var s='', n=cs.length-1
	do s += (cs[n]>0 ? ' +' : ' ') + cs[n] + (n==0 ? '' : n==1 ? 'x' :'x<sup>'+n+'</sup>'); while (n--)
	return s
}
 
function isPrime(n) {
	var cs=coef(n), i=n-1; while (i-- && cs[i]%n == 0);
	return i < 1
}
 
for (var n=0; n<=7; n++) document.write('(x-1)<sup>',n,'</sup> = ', show(coef(n)), '<br>')
 
document.write('<br>Primes: ');
for (var n=2; n<=50; n++) if (isPrime(n)) document.write(' ', n)

Translation of: CoffeeScript

var i, p, pascal, primerow, primes, show, _i;

pascal = function() {
  var a;
  a = [];
  return function() {
    var b, i;
    if (a.length === 0) {
      return a = [1];
    } else {
      b = (function() {
        var _i, _ref, _results;
        _results = [];
        for (i = _i = 0, _ref = a.length - 1; 0 <= _ref ? _i < _ref : _i > _ref; i = 0 <= _ref ? ++_i : --_i) {
          _results.push(a[i] + a[i + 1]);
        }
        return _results;
      })();
      return a = [1].concat(b).concat([1]);
    }
  };
};
 
show = function(a) {
  var degree, i, sgn, show_x, str, _i, _ref;
  show_x = function(e) {
    switch (e) {
      case 0:
        return "";
      case 1:
        return "x";
      default:
        return "x^" + e;
    }
  };
  degree = a.length - 1;
  str = "(x - 1)^" + degree + " =";
  sgn = 1;
  for (i = _i = 0, _ref = a.length; 0 <= _ref ? _i < _ref : _i > _ref; i = 0 <= _ref ? ++_i : --_i) {
    str += ' ' + (sgn > 0 ? "+" : "-") + ' ' + a[i] + show_x(degree - i);
    sgn = -sgn;
  }
  return str;
};
 
primerow = function(row) {
  var degree;
  degree = row.length - 1;
  return row.slice(1, degree).every(function(x) {
    return x % degree === 0;
  });
};
 
p = pascal();
 
for (i = _i = 0; _i <= 7; i = ++_i) {
  console.log(show(p()));
}
 
p = pascal();
 
p();
 
p();
 
primes = (function() {
  var _j, _results;
  _results = [];
  for (i = _j = 1; _j <= 49; i = ++_j) {
    if (primerow(p())) {
      _results.push(i + 1);
    }
  }
  return _results;
})();
 
console.log("");
 
console.log("The primes upto 50 are: " + primes);

Reviewed (ES6)

function pascal(n) {
	var cs = []; if (n) while (n--) coef(); return coef
	function coef() {
		if (cs.length === 0) return cs = [1];
		for (var t=[1,1], i=cs.length-1; i; i-=1) t.splice( 1, 0, cs[i-1]+cs[i] ); return cs = t
	}
}

function show(cs) {
	for (var s='', sgn=true, i=0, deg=cs.length-1; i<=deg; sgn=!sgn, i+=1) {
		s += ' ' + (sgn ? '+' : '-') + cs[i] + (e => e==0 ? '' : e==1 ? 'x' : 'x<sup>' + e + '</sup>')(deg-i)
	}
	return '(x-1)<sup>' + deg + '</sup> =' + s;
}

function isPrime(cs) {
	var deg=cs.length-1; return cs.slice(1, deg).every( function(c) { return c % deg === 0 } )
}

var coef=pascal(); for (var i=0; i<=7; i+=1) document.write(show(coef()), '<br>')

document.write('<br>Primes: ');
for (var coef=pascal(2), n=2; n<=50; n+=1) if (isPrime(coef())) document.write(' ', n)

ref

• AKS test for primes
• PRIMES is in P
• AKS primality test