## primality of general N

Expand Messages
• go to www.php.net and download the free PHP5 language, and run the following program from the command line interface, if you like... it finds the primality of
Message 1 of 1 , Feb 23, 2008
• 0 Attachment
go to www.php.net and download the free PHP5 language, and run the
following program from the command line interface, if you like...

it finds the primality of a general odd number using the 'bcmath'
functions that can handle large integers.

the test utilizes the 2-PRP test and detects a psuedo-prime before it
can be accidently reported as prime. I think that its deterministic.
I can modify the test to work for base 3, 5, etc. w/a slight change.

<?php

// This program can be run on the command line using: php slip.php.
// It was written and developed by W. Bouris, and this php code deter-
// mines the absolute primality of a number using a disected 2-PRP
test.

// MAIN PROGRAM ------------------------------------------------------
--

\$bcFuncs = array('bcadd', 'bccomp', 'bcdiv', 'bcmod', 'bcmul',
'bcpow', 'bcscale', 'bcsqrt', 'bcsub', 'bcpowmod');
\$flag = false;

foreach(\$bcFuncs as \$func)
{
if(!function_exists(\$func))
{
print("No BCMath with support for bcpowmod()!<br>");
\$flag = true;
}
}
if(\$flag) exit(1);

bcscale(0);

do
{
print("\n");
print("Please enter an odd number: ");
fscanf(STDIN, "%s\n", \$n);
}while(bccomp(bcmod(\$n, 2), 1) != 0);

if((bcmod(\$n, 3) != 0) and (bccomp(\$n, 3) != 0))
{
if((bcmod(\$n, 5) != 0) and (bccomp(\$n, 5) != 0))
{
\$y1 = bcpowmod(2, bcsub(\$n, 1), \$n);
if(bccomp(\$y1, 1) == 0)
{
\$y2 = bcpowmod(2, bcsub(bcdiv(bcsub(\$n, 1), 2), 3), \$n);
if(bccomp(bcmod(\$n, 4), 1) == 0)
{
bcscale(2);
\$x1 = bcdiv(\$n, 8); \$x2 = bcdiv(\$n, 2); \$x3 = bcdiv(bcmul(\$n, 3),
4); \$x4 = bcdiv(bcmul(\$n, 7), 8);
if(((bccomp(\$y2, \$x1) == 1) and (bccomp(\$y2, \$x2) != 1)) or
((bccomp(\$y2, \$x3) == 1) and (bccomp(\$y2, \$x4) != 1)))
{
print("\$n, composite\n");
}
else
{
print("\$n, prime\n");
}
}
else
{
bcscale(2);
\$x1 = bcdiv(\$n, 8); \$x2 = bcdiv(\$n, 2); \$x3 = bcdiv(bcmul(\$n, 3),
4); \$x4 = bcdiv(bcmul(\$n, 7), 8);
if((bccomp(\$y2, \$x1) != 1) or ((bccomp(\$y2, \$x2) == 1) and (bccomp
(\$y2, \$x3) != 1)) or (bccomp(\$y2, \$x4) == 1))
{
print("\$n, composite\n");
}
else
{
print("\$n, prime\n");
}
}
}
else
{
print("\$n, composite\n");
}
}
else
{
if((bccomp(\$n, 5) == 0))
{
print("\$n, prime\n");
}
else
{
print("\$n, composite\n");
}
}
}
else
{
if((bccomp(\$n, 3) == 0))
{
print("\$n, prime\n");
}
else
{
print("\$n, composite\n");
}
}

?>
Your message has been successfully submitted and would be delivered to recipients shortly.