AKS test for primes

aks.rs

extern mod extra;
use extra::bigint::BigInt;
use extra::bigint::Plus;
use extra::bigint::Minus;
use extra::bigint::Zero;
use extra::bigint::ToBigInt;

fn coefficients(p: uint) -> ~[BigInt] {
    if p==0 {
        ~[BigInt::new(Plus, ~[1])]
    } else {
        let mut result: ~[BigInt] = ~[BigInt::new(Plus, ~[1]),
                                      BigInt::new(Minus, ~[1])];
        let zero = Some(BigInt::new(Zero, ~[0]));
        for _ in range(1, p) {
            result = {
                let a = result.iter().chain(zero.iter());
                let b = zero.iter().chain(result.iter());
                a.zip(b).map(|(x, ref y)| x-**y).to_owned_vec()
            };
        }
        result
    }
}
 
fn is_prime(p: uint) -> bool {
    if p<2 {
        false
    } else {
        let mut c = coefficients(p);
        c[0] = c[0] - BigInt::new(Plus, ~[1]);
        for i in range(0, c.iter().len()/2) {
            if (c[i] % (p as i64).to_bigint()
                .unwrap_or(BigInt::new(Plus, ~[1])))
                != BigInt::new(Zero, ~[0]) {
                return false
            }
        }
        true
    }
}
 
fn main() {
    for p in range(0, 8) {
        print!("{}: ", p);
        println!("{}", coefficients(p as uint).to_str());
    }
 
    for p in range(1, 1001) {
        if is_prime(p as uint) {
            print!("{} ", p);
        }
    }
    println!("");
}

Just a short note to others, that this isn't actually AKS, but an exponential-time trial division. See the top material at Rosetta Code's "AKS test for primes", which has an unfortunate title (since the task isn't the AKS test). Also described in the AKS concepts portion on Wikipedia