MillerRabinTest.php

<?php
class MillerRabinTest {
    public static function isPrime($number, $round = 10) {
        $number = intval($number);
        $round = intval($round);
        if($number === 2) {
            return true;
        }
        if($number === 1 || $number % 2 === 0) {
            return false;
        }
        $d = $number - 1;
        $s = 0;
        while($d % 2 === 0) {
            $d /= 2;
            ++$s;
        }
        for($i = 0; $i < $round; ++$i) {
            $isProbablyPrime = false;

            $a = mt_rand(1, $number - 1);
            $r = self::modPow($a, $d, $number);
            if($r === 1 || $r === $number - 1) {
                $isProbablyPrime = true;
            }
            for($j = 0; !$isProbablyPrime && $j < $s; ++$j) {
                $r = self::modPow($r, 2, $number);
                if($r === $number - 1) {
                    $isProbablyPrime = true;
                }
            }
            if(!$isProbablyPrime) {
                return false;
            }
        }
        return true;
    }

    private static function modPow($base, $power, $mod) {
        $ret = 1;
        while($power > 0) {
            if($power % 2 === 1) {
                $ret = ($ret * $base) % $mod;
            }
            $base = ($base * $base) % $mod;
            $power /= 2;
        }
        return $ret;
    }
}

for($i = 1; $i < 100; ++$i) {
    echo $i . ": " . (MillerRabinTest::isPrime($i) ? 'prime' : 'composite') . "\n";
}