AKS Primality Test

aks.py

# ChatGPT4 spit it out with some coaxing - looks legit, haven't tested.

import math

def is_prime(n):
    def is_power(a, b):
        if a == 1:
            return b != 1
        power = 1
        while power < b:
            power *= a
        return power == b

    def find_r(n):
        max_r = math.ceil(math.log2(n) ** 2)
        for r in range(2, max_r + 1):
            if not is_power(n, r):
                return r
        return -1

    def check_a(a, n, r):
        for k in range(1, r + 1):
            val = (pow(a, k, n) - k) % n
            if val != 0:
                return False
        return True

    # Check if n is a power of a smaller number
    for a in range(2, n):
        if is_power(a, n):
            return False

    # Find the smallest r such that ord_r(n) > log^2(n)
    r = find_r(n)

    # Check a-values from 1 to r
    for a in range(1, r + 1):
        if math.gcd(a, n) > 1:
            return False

        if not check_a(a, n, r):
            return False

    return True

n = 97  # Try with any number
print(f"{n} is prime: {is_prime(n)}")

Rust version it gave

use num::Integer;
use num::bigint::BigInt;
use num::pow::pow;

fn is_power(a: u64, b: u64) -> bool {
    if a == 1 {
        return b != 1;
    }
    let mut power = 1;
    while power < b {
        power *= a;
    }
    return power == b;
}

fn find_r(n: u64) -> u64 {
    let max_r = (n as f64).log2().powi(2).ceil() as u64;
    for r in 2..=max_r {
        if !is_power(n, r) {
            return r;
        }
    }
    return 0;
}

fn check_a(a: u64, n: u64, r: u64) -> bool {
    for k in 1..=r {
        let val = (pow(BigInt::from(a), k as usize) % n) - k as u64;
        if val != 0 {
            return false;
        }
    }
    return true;
}

fn is_prime(n: u64) -> bool {
    for a in 2..n {
        if is_power(a, n) {
            return false;
        }
    }

    let r = find_r(n);

    for a in 1..=r {
        if a.gcd(&n) > 1 {
            return false;
        }

        if !check_a(a, n, r) {
            return false;
        }
    }

    return true;
}

fn main() {
    let n = 97; // Try with any number
    println!("{} is prime: {}", n, is_prime(n));
}

Bash version it gave

#!/bin/bash

is_power() {
    local a="$1"
    local b="$2"
    if [ "$a" -eq 1 ]; then
        [ "$b" -ne 1 ]
        return
    fi
    local power=1
    while [ "$power" -lt "$b" ]; do
        power=$((power * a))
    done
    [ "$power" -eq "$b" ]
}

find_r() {
    local n="$1"
    local max_r=$(echo "l($n)^2" | bc -l | awk '{printf "%d\n", ($1 + 0.5)}')
    for ((r = 2; r <= max_r; r++)); do
        if ! is_power "$n" "$r"; then
            echo "$r"
            return
        fi
    done
    echo 0
}

check_a() {
    local a="$1"
    local n="$2"
    local r="$3"
    for ((k = 1; k <= r; k++)); do
        local val=$(echo "($a^$k) % $n" | bc)
        val=$((val - k))
        if [ "$val" -ne 0 ]; then
            return 1
        fi
    done
    return 0
}

is_prime() {
    local n="$1"
    for ((a = 2; a < n; a++)); do
        if is_power "$a" "$n"; then
            return 1
        fi
    done

    local r=$(find_r "$n")

    for ((a = 1; a <= r; a++)); do
        if ! (echo "$a" "$n" | awk '{print $1 % $2}') > /dev/null; then
            return 1
        fi

        if ! check_a "$a" "$n" "$r"; then
            return 1
        fi
    done

    return 0
}

n=97
if is_prime "$n"; then
    echo "$n is prime"
else
    echo "$n is not prime"
fi