primality.ag

//Script to check whether a number is prime, using the
//Miller-Rabin primality test.
//(c) Larry T, 2019

//Import dependencies.
import "io";
import "maths";

//Define the function.
let rabinMiller(num, certainty) = {

    //Filter out basic primes.
    if (num == 2 | num == 3)
    {
        return true;
    }

    //Below 2 and % 0? Not prime.
    if (num < 2 | num % 2 == 0)
    {
        return false;
    }

    //Find the even integer below the number.
    let even_num = num - 1;
    let s = 0;

    //Find lowest odd divisor.
    while (even_num % 2 == 0)
    {
        even_num /= 2;
        s++;
    }

    //Generate a random integer.
    let rand = 0;
    for (i up to certainty - 1) 
    {
        while (true)
        {
            rand = random.int(0);
            if (rand >= 2 & rand < even_num - 2)
            {
                break;
            }
        }

        //Done, check for x=1 or x=even-1.
        let modPow = maths.modPow(rand, even_num, num);
        if (modPow == 1 | modPow == num - 1)
        {
            continue;
        }

        //Iterating to check for prime.
        for (i up to s - 1)
        {
            //From 1 upwards.
            if (i < 1) { continue; }

            modPow = maths.modPow(modPow, 2, num);
            if (modPow == 1)
            {
                return false;
            }
            else if (modPow == num - 1)
            {
                break;
            }
        }

        if (modPow != num - 1)
        {
            return false;
        }
        
    }

    //All tests have failed to prove composite, so return "probably prime".
    return true;
}


//Get the number to check.
print "Enter the number you wish to check for primality.";
let num = int(input.get());

//Check.
let isPrime = rabinMiller(num, 5);
if (isPrime)
{
    print "Your number is prime (probably)!";
}
else
{
    print "Your number is not prime. :(";
}