Algorithmus zur Bestimmung der Primalität einer Ganzahl

[negaH]

Wichtig ist dieser Teil, er ist die letzte Schleife aus dem Dokument, benutzt aber eine Algorithmus der durch Daniel J. Bernstein verbesserte Eingangsparameter beechnet.

Delphi-Quellcode:

// Bernstein 
// n=1000000007, r=3623, s=1785, q=1811 

  SetLength(M, R+1);  // M = x^r -1 
  NSet(M[R], 1); 
  NDec(N); 
  NSet(M[0], N); 
  NInc(N); 

  C := 0; 
  for I := 1 to S do 
  begin 
    NSet(P, [1, -I]); 
    StartTimer; 
    NPowModxkm1(P, N, R, N); 
    C := C + Ticks; 
    Write( #29, C / I / 1000 * S:10:2, #20 ); 
  end; 
end;

Bei der Zahl n=1000000007 muss also r=3623, s=1785 und q=1811 sein. Dies bedeutet das in der Schleife mit dem Polynom 1000000007x^3623 + 1000000008x^0 angefangen wird. Dieses Polynom hat für die klitzekleine Zahl 1000000007
also schon 3623 Koeffizienten, baut sich also im laufe der Schleife aus 3623 eigenen Zahlen zusammen.

Wollte man zb. Zahlen > 2^256 so überprüfen so würden die Polynomberechnungen über Vektoren mit mehr als 1Mio Elementen rechnen müssen.

Nach einigen eigenen Tests und einigen Diskusssionen mit Mathematikern dachte ich das AKS ein schlechter mathematischer Witz sein muß. Wie gesagt ohne diese aufwendige Polynomarithmetik gehts nicht.Nebenbei bemerkt,auch wenn obige Codeteile ziemlich verwurschtelt aussehen so sind sie weit effizienter als die Versuche die die Leute von Miracl oder GMP mit ihren Libs angestellt haben.

Gruß Hagen