Marco Tech Blog

January 3, 2008

Handbook Note 71/113: Is Prime Number Function

Note 71 of 113 of Delphi 2007 Handbook

posted by marcocantu @ 10:37AM | 4 Comments [0 Pending]

Handbook Note 71/113 Is Prime Number Function 

Testing a number for primality is not an easy task, 
and many methods were developed - especially now that 
cryptography relies so heavily on prime numbers. Some 
are just "probabilistic", other are "deterministic". 
See for example Miller-Rabin, or the newer Agrawal-
Kayal-Saxena.

PS: delete my previous post, please, it was submitted 
by mistake.

Comment by Luigi D. Sandon on January 3, 10:54

Handbook Note 71/113 Is Prime Number Function 

Yes, much simple way - not a deterministic, the
probability function; see the "Rabin-Miller" test for
more details.

the "Lehmann" sample:

<pre>
// tested on D7
program test_lehmann;

{$APPTYPE CONSOLE}

uses
  SysUtils;

// the probability of prime if true - not less 0.5
function lehmann_probe(p: integer): Boolean;
var
  a,z,r,q: int64;
begin
  p := abs(p);
// test for small numbers
  if p<4 then
    begin
      result := true;
      exit;
    end;
// get the random a for the probe
  repeat a := random(p); until a >= 3;
// calculate a^((p-1)/2) mod p
  z := a;
  r := (p-1) div 2;
  q := 1;
  while r>0 do
    begin
      z := (z*z) mod p;
      if (r and 1) = 1 then q := (q * z) mod p;
      r := r shr 1;
    end;
// the result
  result := (q = 1) or (q = (p-1));
end;

// numbers must be big!
function prime_lehmann(p,n: Integer): Boolean;
var
  m: Integer;
begin
  if n<0 then
    begin
      result := false;
      exit;
    end;
// this is only for this demo
  write('is the ',p,' prime? - ');
  m := n;
  result := true;
  while (result) and (n>0) do
    begin
      result := lehmann_probe(p);
      dec(n);
    end;
// this is only for this demo
  writeln(result,', number of probes ',m-n);
end;

var
  i,j: Integer;
begin
  randomize;
  j := 100+random(1000000);
  for i := j to (j+100) do prime_lehmann(i,30);
  readln;
end.
</pre>

Comment by Leonid Koninin on January 3, 18:12

Handbook Note 71/113 Is Prime Number Function 

sorry, mistype in previous source, must be:

// the probability of prime if true - not less 0.5
function lehmann_probe(p: integer): Boolean;
var
  a,z,r,q: int64;
begin
  p := abs(p);
// test for small numbers
  if p<4 then
    begin
      result := true;
      exit;
    end;
// get the random a for the probe
  repeat a := random(p); until a >= 3;
// calculate a^((p-1)/2) mod p
  z := a;
  r := (p-1) div 2;
  q := 1;
  while r>0 do
    begin
      if (r and 1) = 1 then q := (q * z) mod p;
      z := (z*z) mod p;
      r := r shr 1;
    end;
// the result
  result := (q = 1) or (q = (p-1));
end;

Comment by Leonid Koninin on January 3, 18:24

Handbook Note 71/113 Is Prime Number Function 

When you think of core Delphi functions and Fast, you
should think of FastCode ;-)

http://fastcode.sourceforge.net/challenge_content/IsPrime.html

Seems to be an old BV style because the RTL function
is not included (Which nowadays is)

So I can't give the correct speedup above RTL, but I
assume it's goood :)

Comment by Davy Landman [http://delphi-snippetrs.blogspot.com] on January 7, 17:18