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)