Loading ...
Sorry, an error occurred while loading the content.

primality of general N

Expand Messages
  • leavemsg1
    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.