Die Computerseite von Eckart Winkler
Primzahltests und Primfaktorzerlegung - Teil 3

 

Dieser Artikel ist im Heise-Verlag in der Zeitschrift "c't", Ausgabe 05/1989 erschienen. Er ist hier aus Gründen der besseren Übersicht dreigeteilt. Grundlage ist der Artikel "Lange Integer-Zahlen in C". Links:



Ein Taschenrechner

Damit schließen wir das Thema der Primzahlen ab. Am Ende des Artikels sind wir deswegen noch nicht. Denn nun gibt es noch ein weiteres Programm zu besprechen. Wenn wir den Inhalt dieses und des Artikels aus dem letzten Heft Revue passieren lassen, fällt auf, daß alle von uns programmierten Hauptprogramme nur Beispiele sind. Um die auftretenden Funktionen für eigene Anwendungen zu benutzen, müssen deshalb immer entsprechende Hauptprogramme geschrieben werden. Wollen wir beispielsweise feststellen, ob die Zahl 7^41-2 prim ist, müssen wir ein Programm schreiben, in dem zuerst der Wert der zu untersuchenden Zahl erzeugt wird. Sodann wird beispielsweise der Primzahltest von Miller-Rabin aufgerufen.

Das ist natürlich eine komplizierte und nicht anwenderfreundliche Vorgehensweise. Deshalb gibt es nun ein Programm, das derartige Arbeiten vereinfacht:

#define MaxNr 50
#include "longcalc.c"
#include "stdio.h"

longint x={1,0},y={1,0},m[10];
string xs="0", ys="0",ms[10];

void main()
{
  string s;
  int i;
  for (i=0;i<10;i++) { longl(0L,m[i]); ms[i][0]='0'; ms[i][1]='\0'; }
  while(1) {
    printf("****      Taschenrechner fuer lange Integers     ****\n");
    printf("X %s\n",xs);
    if (gt0l(y)) printf("Y %s\n",ys);
    scanf("%s",s); exec(s); }
}

/* ***** Ausfuehren eines Befehls ***** */

void exec(string ts)
{
  int f;
  longint t,h;
  string hs;
  switch (ts[0]) {
    case '0': case '1': case '2': case '3': case '4':
    case '5': case '6': case '7': case '8': case '9':
      printf("X-Register laden\n"); stol(ts,t);
      tr(x,xs,y,ys); tr(t,ts,x,xs); break;
    case '+':
      printf("Addition\n"); addl(y,x,x); ltos(x,xs);
      longl(0L,y); break;
    case '-':
      printf("Subtraktion\n"); subl(y,x,x); ltos(x,xs);
      longl(0L,y); break;
    case '*':
      printf("Multiplikation\n"); multl(y,x,x); ltos(x,xs);
      longl(0L,y); break;
    case '/':
      if (eq0l(x)) break;
      printf("Division\n"); divl(y,x,x); ltos(x,xs);
      longl(0L,y); break;
    case '%':
      if (eq0l(x)) break;
      printf("Rest der Division\n"); modl(y,x,x);
      ltos(x,xs); longl(0L,y); break;
    case '^':
      printf("Potenzieren\n"); powl(y,x,x); ltos(x,xs);
      longl(0L,y); break;
    case '!':
      printf("Fakultaet\n"); fakl(x,x); ltos(x,xs);
      longl(0L,y); break;
    case 'd': case 'D':
      printf("Dekrementieren\n"); decl(x); ltos(x,xs);
      longl(0L,y); break;
    case 'e': case 'E':
      printf("Ende\n"); exit(0); break;
    case 'f': case 'F':
      if (eq0l(x)) break;
      printf("Faktorisierungsverfahren von Pollard\n");
      longl(0L,y); poll(x,10000,25,t,&f);
      if (f) {
        printf(":\n: Faktor gefunden\n:\n"); transl(t,x); ltos(x,xs); }
      else printf(":\n: Kein Faktor gefunden\n:\n"); break;
    case 'g': case 'G':
      if (eq0l(x) || eq0l(y)) break;
      printf("Groesster gemeinsamer Teiler\n");
      ggtl(x,y,x); ltos(x,xs); longl(0L,y); break;
    case 'h': case 'H':
      printf("****      Taschenrechner fuer lange Integers     ****\n");
      printf(":\n: +  Addition               -  Subtraktion\n");
      printf(": *  Multiplikation         /  Division\n");
      printf(": %%  Rest der Division      ^  Potenzierung\n");
      printf(": !  Fakultaet              G  ggT\n");
      printf(": I  Inkrement              D  Dekrement\n");
      printf(": P  Primzahltest           F  Faktorisierung\n");
      printf(": S  Speichern einer Zahl   L  Laden einer Zahl\n");
      printf(": M  Speicheranzeige        X  X und Y vertauschen\n");
      printf(": H  Hilfe                  E  Ende\n:\n"); break;
    case 'i': case 'I':
      printf("Inkrementieren\n"); incl(x); ltos(x,xs);
      longl(0L,y); break;
    case 'l': case 'L':
      f=ts[1]-'0'; if (f<0 || f>9) break;
      printf("Laden einer Zahl ins X-Register\n");
      tr(x,xs,y,ys); tr(m[f],ms[f],x,xs); break;
    case 'm': case 'M':
      printf("****             Inhalt der Speicher             ****\n");
      printf(":\n");
      for (f=0;f<10;f++) printf(": %d %s\n",f,ms[f]);
      printf(":\n"); break;
    case 'p': case 'P':
      if (ltl(x,zehnl)) break;
      printf("Monte-Carlo-Primzahltest von Miller-Rabin\n");
      longl(0L,y);
      if (mr(x,30)) printf(":\n: x ist prim\n:\n");
        else printf(":\n: x ist nicht prim\n:\n"); break;
    case 's': case 'S':
      f=ts[1]-'0'; if (f<0 || f>9) break;
      printf("Speichern des X-Registers\n");
      tr(x,xs,m[f],ms[f]); break;
    case 'x': case 'X':
      printf("X- und Y-Register vertauschen\n");
      tr(x,xs,h,hs); tr(y,ys,x,xs); tr(h,hs,y,ys); break; }
}

/*   Uebertragen eines Registers   */
void tr(longint t, string ts, longint w, string ws)
  longint t,w;
  string ts,ws;
  {
  int i;
  for(i=0;ts[i]!='\0';i++) ws[i]=ts[i];
  ws[i]='\0'; transl(t,w);
  }

/* ***** Die Primzahlverfahren ***** */

void mr(longint n, int p)
  /* wie oben */

void mr_check(int k, longint u, longint n, longint a)
  /* wie oben */

void poll(longint n, int st, int ch, longint a, int *f)
  /* wie oben */

In der Bedienung verhält es sich ähnlich wie ein Taschenrechner. Alle wichtigen Funktionen sind integriert. Die Realisierung ist relativ einfach, deshalb beschränken wir uns auf eine Beschreibung der Anwendung. Wichtig ist nur, daß am Ende des Listings die Routinen mr, mr_check und poll nicht abgedruckt sind, da sie identisch zu denen aus Listing 2 und 3 sind. Der jeweilige Programmcode ist hier einzufügen.

Nach Start des Programms kommen wir direkt in eine Schleife, in der der Benutzer Eingaben durchführen kann. Zwei Möglichkeiten sind hier gegeben. Entweder er gibt eine Zahl ein. Dann wird diese in ein Rechenregister geladen. Oder er gibt einen Befehl ein. Dann wird dieser ausgeführt. Die Eingabe wird als String abgefragt. Wir müssen sie also immer durch die Return-Taste beenden. Die Entscheidung Zahl/Befehl wird aufgrund des ersten eingegebenen Zeichens getroffen, bei einem Befehl werden meist alle Zeichen außer dem ersten ignoriert.

Unser Taschenrechner verfügt über zwei Rechenregister, bezeichnet mit X- und Y-Register. Eine Zahleneingabe wandert ins X-Register. Befand sich dort bereits eine andere Zahl ungleich 0, wird diese ins Y-Register weitergeschoben. Ein Rechenbefehl, der zwei Operanden benötigt, holt sich diese aus den beiden Registern und schreibt das Ergebnis zurück ins X-Register. Das Y-Register wird gelöscht.

Wie haben wir vorzugehen, wenn wir z.B. zwei Zahlen subtrahieren wollen? Ganz einfach, wir geben die erste Zahl ein, etwa 37. Dann steht diese im X-Register. Darauf geben wir die zweite Zahl ein, z.B. 15. Jetzt steht 15 im X-Register, 37 im Y-Register. Nun geben wir ein Minuszeichen ein, drücken Return, und das Ergebnis erscheint im X-Register.

Somit wird auch klar, daß der erste Operand jeweils im Y-Register gesucht wird, der zweite im X-Register. Das ist wichtig, auf diese Art und Weise können die Operanden in der gewohnten Reihenfolge eingegeben werden. Der Operator kommt aber immer nach den Operanden an die Reihe, dies entspricht der UPN (Umgekehrt polnische Notation).

Nun zu den einzelnen Befehlen. Der wichtigste heißt "h" wie "Hilfe". Hiermit bringen wir alle eingebauten Befehle auf den Bildschirm. Am häufigsten werden wohl die Rechenoperationen Verwendung finden. Sie werden alle mit den in arithmetischen Ausdrücken üblichen Symbolen bezeichnet. Also +, -, * und / für die Grundrechenarten, ^ für Potenzierung und ! für die Berechnung der Fakultät. Zudem kann man mit % den Rest einer Division ermitteln.

Des weiteren sind Befehle zum schnellen Inkrementieren und Dekrementieren implementiert, nach den Anfangsbuchstaben i und d genannt. Der Befehl "p" führt für die Zahl im X-Register den Primzahltest von Miller-Rabin durch, "f" die Faktorisierung nach Pollard. Bei ersterem sind 30 Einzeltests vorgesehen, beim zweiten bis zu 10000 Schritte bei Überprüfung jedes 25. Schritts. Diese drei Parameter sind beim Aufruf des jeweiligen Unterprogramms festgelegt und können nach Belieben im Programmtext geändert werden.

Beim Miller-Rabin-Test findet keine Manipulation der Register statt, das Ergebnis der Überprüfung wird in Klartext auf den Bildschirm geschrieben. Dies gilt auch für das Verfahren von Pollard. Wird hier jedoch ein Faktor gefunden, ist dieser hinterher im X-Register zu finden. Ansonsten bleiben die Register unangetastet.

Außerdem besteht noch die Möglichkeit, Zahlen zwischenzuspeichern. Hierzu stehen zehn Speicherregister zur Verfügung. Der Befehl s (=store) speichert das X-Register ab, l (=load) wirkt in der umgekehrten Richtung. Bei diesen beiden Befehlen muß jeweils die Nummer des Speichers angegeben werden, der angesprochen wird. Möglich sind die Ziffern 0 bis 9. Sie müssen ohne Zwischenraum direkt auf den Befehl folgen.

Der l-Befehl hat dieselbe Wirkung wie eine Zahleneingabe von Hand. Das bedeutet, eine eventuell im X-Register vorhandene Zahl wird zunächst ins Y-Register weitergeschoben, bevor die zu ladende Zahl dort Platz findet. Mit "m" kann man sich die augenblickliche Belegung aller Speicherregister ausgeben lassen. Der letzte Befehl heißt "e". Er beendet die Programmausführung. Obwohl die Anwendung dieses Programms recht einfach ist, ist doch Vorsicht geboten. Denn es wurden keine Maßnahmen gegen Fehlbedienung eingebaut, dafür muß jeder selbst sorgen.

Wir kommen nun ein letztes Mal auf den RSA-Algorithmus zu sprechen. Denn den einen oder anderen könnte es ja interessieren, wie die im letzten Heft vorkommenden Zahlen n, s und t zustande kamen. Nun, für p und q wurden zwei Primzahlen verwendet, die mittels des Brillhart-Selfridge-Tests ermittelt wurden. Das waren p=2*3^30+1 und q=2^41*3+1. Damit sind die Werte von n und f klar. Um Werte für s und t zu bekommen, wurde die Zerlegung von a*f+1 mit a=3 berechnet und die Faktoren auf s und t aufgeteilt.

p und q konnten übrigens auch mit dem Miller-Rabin-Test als prim erkannt werden, während die Zerlegung von n nicht gelang. Nach 20000 Schritten des Pollard-Verfahrens wurde die Berechnung abgebrochen.


Literatur

  • J.Wolfart: Primzahltests und Primfaktorzerlegung (in: Jahrbuch Überblicke Mathematik 1981, Bibliographisches Institut, Seiten 161-188)

 

Übersicht Programmiersprache C Index