Tips (1541)

Tip Bewertung (21):

function IsPrime(N: Cardinal): Boolean; register;
  // test if N is prime, do some small Strong Pseudo Prime test in certain bounds
  // copyright (c) 2000 Hagen Reddmann, don't remove
asm
      TEST  EAX,1            { Odd(N) ?? }
      JNZ   @@1
      CMP   EAX,2            { N == 2 ?? }
      SETE  AL
      RET
@@1:  CMP   EAX,73           { N        JB    @@C }
      JE    @@E              { N == 73 ?? }
      PUSH  ESI
      PUSH  EDI
      PUSH  EBX
      PUSH  EBP
      PUSH  EAX              { save N as Param for @@5 }
      LEA   EBP,[EAX - 1]    {  M == N -1, Exponent }
      MOV   ECX,32           { calc remaining Bits of M and shift M' }
      MOV   ESI,EBP
@@2:  DEC   ECX
      SHL   ESI,1
      JNC   @@2
      PUSH  ECX              { save Bits as Param for @@5 }
      PUSH  ESI              {  save M' as Param for @@5 }
      CMP   EAX,08A8D7Fh     {  N = 9080191 ?? }
      JAE   @@3
      // now if (N       MOV   EAX,31
      CALL  @@5              { 31^((N-1)(2^s)) mod N }
      JC    @@4
      MOV   EAX,73           { 73^((N-1)(2^s)) mod N }
      PUSH  OFFSET @@4
      JMP   @@5
      // now if (N @@3:   MOV   EAX,2
      CALL  @@5
      JC    @@4
      MOV   EAX,7
      CALL  @@5
      JC    @@4
      MOV   EAX,61
      CALL  @@5
@@4:  SETNC AL
      ADD   ESP,4 * 3
      POP   EBP
      POP   EBX
      POP   EDI
      POP   ESI
      RET
// do a Strong Pseudo Prime Test
@@5:  MOV   EBX,[ESP + 12]     { N on stack }
      MOV   ECX,[ESP +  8]     { remaining Bits }
      MOV   ESI,[ESP +  4]     { M' }
      MOV   EDI,EAX            { T = b, temp. Base }
@@6:  DEC   ECX
      MUL   EAX
      DIV   EBX
      MOV   EAX,EDX
      SHL   ESI,1
      JNC   @@7
      MUL   EDI
      DIV   EBX
      AND   ESI,ESI
      MOV   EAX,EDX
@@7:  JNZ   @@6
      CMP   EAX,1      { b^((N -1)(2^s)) mod N ==  1 mod N ?? }
      JE    @@A
@@8:  CMP   EAX,EBP    { b^((N -1)(2^s)) mod N == -1 mod N ?? , EBP = N -1 }
      JE    @@A
      DEC   ECX        { second part to 2^s }
      JNG   @@9
      MUL   EAX
      DIV   EBX
      CMP   EDX,1
      MOV   EAX,EDX
      JNE   @@8
@@9:  STC
@@A:  RET
@@B:  DB    3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
@@C:  MOV   EDX,OFFSET @@B
      MOV   ECX,18
@@D:  CMP   AL,[EDX + ECX]
      JE    @@E
      DEC   ECX
      JNL   @@D
@@E:  SETE  AL
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  if IsPrime(3453451) then
    ShowMessage('yes');
end;

{**** Another function ***}

function IsPrime(Prim: Longint): Boolean;
var
  Z: Real;
  Max: LongInt;
  Divisor: LongInt;
begin
  Prime := False;
  if (Prim and 1) = 0 then Exit;
  Z       := Sqrt(Prim);
  Max     := Trunc(Z) + 1;
  Divisor := 3;
  while Max > Divisor do
  begin
    if (Prim mod Divisor) = 0 then Exit;
    Inc(Divisor, 2);
    if (Prim mod Divisor) = 0 then Exit;
    Inc(Divisor, 4);
  end;
  Prime := True;
end;