Technikfun Technik, Technik und ääh – Technik.

Das Problem mit den großen Zahlen

18446744073709551615 - Das ist die größte Zahl, die man mit C-Boardmitteln maximal berechnen kann - 2^64 -1, also eine 64 Bit Zahl. Wie also soll man mit Zahlen rechnen die größer sind? Viele werden sich auch fragen, wofür man überhaupt mit so großen Zahlen rechnen wll beziehungsweise muss. Nun,  wenn man seine Daten zum Beispiel mit RSA verschlüsseln will, muss man mit sehr großen Zahlen umgehen können. Die heutigen RSA-Schlüssel sind 4096Bit lang, verglichen damit wirkt die anfangs erwähnte 64 Bit Zahl geradezu lächerlich klein. Es gibt viele Libraries bzw Bibliotheken, die mit großen Zahlen rechnen können. Die meisten davon sind aber schlecht dokumentiert, haben auch eine feste "Zahlengröße" (die Anzahl der reservierten Bits für die Zahl ist festgelegt) und sind zum Teil auch nur für bestimmte Projekte festgelegt. Aber nach langem Suchen habe ich eine Bibliothek gefunden, die auch mit sehr großen Zahlen umgehen kann, die gmp (GNU Multiple Precision Arithmetic Library). Diese ist sehr gut dokumentiert (die Doku findet man auf deren Seite), Speicher für die Zahlen wird standardmäßig immer bedarfsmäßig angeforderd und sie ist leicht zu benutzen, auch wenn man den kompletten Code umkrempeln muss - ein kleiner Nachteil.  Limits für die Größe der Zahlen werdenübrigens nur durch die Größe benutzbaren Arbeitsspeichers gesetzt, bei 2GB freiem Speicher kann man also theoretisch eine 17179869184 Bit große Zahl speichern.

Um  gmp einmal zu testen, habe ich mein Primzahlentestprogramm (ist auch zum Teil in QPrimes enthalten) einmal umgeschrieben:

#include <stdio.h>
#include <gmp.h>
#include <stdarg.h>

int primeln(mpz_t, mpz_t);

int main(int argc, char** argv)
{
mpz_t n, r ;
mpz_init(n);
mpz_init_set_str(r, "-1", 0);
gmp_printf("Zahl engeben: ");
mpz_inp_str(n, NULL, 0);
if (mpz_cmp_ui(n, 1)<=0)
gmp_printf("Zahlen kleiner 2 können keine Primzahl sein!\n");
else
{
primeln(r, n);
if (mpz_cmp_ui(r, 0)<0)
gmp_printf("Fehler!\n");
else if (mpz_cmp_ui(r,0)==0)
gmp_printf("%Zd ist prim!\n",n);
else
gmp_printf("%Zd ist nicht prim, kleinster Teiler: %Zd\n",n,r);
}
return 0;
}

int  primeln(mpz_t result, mpz_t pn)
{
mpz_t teiler,wurz, n;
mpz_init_set_str(teiler, "3", 0);
mpz_init(wurz);
mpz_init_set(n, pn);
if (mpz_cmp_ui(n, 2)==0)
{
mpz_set_ui(result, 0);
return 0;
}
if (mpz_divisible_ui_p(n, 2))
{
mpz_set_ui(result, 2);
return 0;
}
mpz_sqrt(wurz, n);
while (mpz_cmp(teiler, wurz)<=0)
{
//gmp_printf("Teiler: %Zd\n",teiler); //Einkommentieren, falls man sich für den aktuellen Teiler interessiert.
if (mpz_divisible_p(n, teiler))
{
mpz_set(result, teiler);
return 0;
}
mpz_add_ui(teiler, teiler, 2);
//mpz_sub_ui(teiler, teiler, 2);
}
mpz_set_ui(result, 0);
return 0;
}

Tut mir Leid, dass das jetzt nicht vernünftig formatiert ist, aber die einrückungen gehen irgendwie nicht. Um den Quelltext zu kompilieren, ruft man

gcc <dateiname>.c -lgmp -o <dateiname2>  -Wall

Startet man das Programm jetzt, kann man die gewünschte zu testende Zahl eingeben. Achtung, bei sehr großen Zahlen kann es scheinbar ewig dauern, hier muss ein effektiver Algorithmus her, aber zum testen und für kleine Zahlen geht es ja. Dieser Code wird demnächst in QPrimes integriert, um auch dort die Bearbeitung großer Zahlen zu ermöglichen.

Den Quelltext von oben kann man hier noch einmal als Datei downloaden: gmpprimzahlentest