Zahl auf Primzahl prüfen

[Aphton]

Man kann zb. den kleinen fermatschen Satz hernehmen.

a^(p-1) mod p = 1

Bedingungen:
- a: integer; kein Vielfaches von p -> 1 < a < p
- p: Primzahl

Test: Primzahl

Code:

p = 13
a = 2

2^12 mod 13 = 1
4096 mod 13 = 1
1 = 1

p = Primzahl

Test: ungerade Zahl

Code:

p = 15
a = 2

2^14 mod 15 = 1
16384 mod 15 = 1
4 = 1

p <> Primzahl

Delphi-Quellcode:

function binPowMod(Base, Exponent: Int64; const ModVal: Int64): Int64;
begin
  Result := 1;
  while Exponent > 0 do
  begin
    if Exponent and 1 > 0 then
      Result := (Result * Base) mod ModVal;
    Base := Base * Base;
    Exponent := Exponent shr 1;
  end;
end;

function isPrime(const P: Int64): Boolean;
begin
  Result := (P > 1) and (P and 1 > 0) and (binPowMod(2, p-1, p) = 1);
end;

Edit:
Huch, habe die 64 Bit Grenze nicht berücksichtigt... Falls man aber eine BigInteger Klasse benutzt, sollte das kein Problem mehr werden.