Rechenoperationen mit großen Zahlen

softpad

Hallo liebe C-Experten, Ich möchte Rechenoperationen mit großen Zahlen durchführen ,die so groß sind dass Sie nicht mit C berechnet werden koennen. Es ist so dass Ich eine Modulo Teilung bzw. Multiplikation mit einer 50 Stellen langen Zahl durchführen möchte. Das geht in c wohl kaum mit den Standarddatentypen int long int u.s.w.. Es muss aber Funtionen geben die das koennen, ----RSA Verschluesselung u.s.w..
Kann mir jemand diese Funktionen hier verlinken oder einen Prototyp der auch funktioniert zeigen. Gibt es eine Seite auf der diese Funktionen nachlesbar sind.

DrakoXP

Üblicherweise nimmt man entweder eine Bibliothek, die große Zahlen unterstützt, wie z.B. GMP oder man schreibt sich selbst was.

Da bei Verschlüsselungsalgorithmen die Anforderungen, was die Anzahl Bits usw. angeht bekannst sind, nutzt man hier selten Typen, die beliebig große Werte erlauben, sondern schreibt sich eher kleine Strukturen, die genau die Anforderungen erfüllen.

Zum Beispiel könnte man sich sowas bauen:

struct int256_t
{
    int parts[4];
};

Dann schreibt man sich halt noch entsprechende Funktionen, die mit solche Strukturen rechnen und dabei Bitüberläufe und dergleichen beachten.

/* hier wird das ergebnis z.B. wieder in a gespeichert: a = a + b; */
void int256_add(struct int256_t * a, struct int256_t const * b);

Wutz

Einfache bigint-Bibliotheken verwenden oft Strings zum Aufnehmen der großen Zahlen. Große Bibliotheken sind meist kompliziert zu bedienen/erlernen.
Für einen schnellen Aha-Effekt kannst du mal probieren:
http://www.di-mgt.com.au/bigdigits.html
Die Bibliothek hat +,-,*,/,% und sogar random- und prime-Zeugs im Angebot.

Dortiges simples Beispiel, leicht abgeändert:

#include "bigd.h"
int main()
{
  BIGD u, v, w, x;
  /* Create new BIGD objects */
  u = bdNew();
  v = bdNew();
  w = bdNew();
  x = bdNew();

  bdConvFromHex(u, "aabbccddeeff0011");
  bdConvFromHex(v, "2233445566778899");

  bdMultiply(w, u, v);

  bdPrintHex("0x", w, "\n");
  bdDivide(x, u, w, v);
  bdPrintHex("0x", x, "\n");

  /* Free all objects we made */
  bdFree(&u);
  bdFree(&v);
  bdFree(&w);
  bdFree(&x);
  return 0;
}

Programmausgabe schrieb:

0x16cf223221110001d38993d01c571229
0xaabbccddeeff0011

Wie du erkennst, kannst du keine Operatoren benutzen, sondern musst entsprechende Funktionen aufrufen.

softpad

wie sieht ein struct in c aus , dass z.b. mit 100 oder 200 Stellen Dezimal Ganzzahloperationen machen kann ? Kannst du mir ein -- vollständiges -- Programm oder Funktion zeigen ? Davon müsste es doch genug geben ?

SeppJ

softpad schrieb:

wie sieht ein struct in c aus , dass z.b. mit 100 oder 200 Stellen Dezimal Ganzzahloperationen machen kann ?

Entweder so oder ähnlich:

typedef uint64_t fixed_big_integer[10];  // ungefähr 192 Dezimalstellen

Oder so oder ähnlich:

struct dynamic_big_integer  // beliebig große Zahlen, so lange Speicher da ist
{
  uint64_t *begin_allocated, *end_allocated, *first_digit;
};

Kannst du mir ein -- vollständiges -- Programm oder Funktion zeigen ?

Mit den obigen structs? Nein, ich programmiere jetzt sicher keine BigInteger Bibliothek. Was gefällt dir an den bisher gegebenen Antworten nicht?

Davon müsste es doch genug geben ?

Ja, gibt es. Was gefällt dir an den bisher gegebenen Antworten nicht?

Aber: Dir ist schon klar, dass die Zahlen bei RSA bei weitem nicht so groß sind, wie du vielleicht annimmst? Klar, du musst schon irgendwo deine 1024-Bit Primzahlen aufnehmen, was mit den Standarddatentypen nicht mehr geht. Aber du musst nie die extrem großen Potenzen wirklich ausrechnen. Da dich am Ende doch bloß das Ergebnis modulo einer anderen Zahl interessiert. Stichwort: Diskrete Exponentialfunktion
edit: Anscheinend ist es dir klar

softpad

Die Antworten sind gut. Ich muss sehrwahrscheinlich die BigInteger Bibliotheken und Beispielquelltext mit struct/class durchgehen bzw. mich länger damit befassen, um die funktionsweise der Rechenoperationen auf die Zahlenreihen zu verstehen......
Danke für die Beiträge !

SeppJ

Warum nutzt du denn die Biginteger-Bibliotheken nicht einfach?

Wenn du eine einfache Vorstellung willst, wie diese Bibliotheken intern arbeiten: So wie in der Grundschule, mit schriftlicher Addition, Multiplikation, Division und so weiter^*. Also Operationen basierend auf den Ziffern, bloß dass die Ziffern hier eben ganz Bytes oder gar ganze long ints sind, anstatt nur von 0 bis 9 zu gehen. Aber das ändert an der Mathematik nichts. Theoretisch könnte man sich auch auf Zeichenketten mit den Zeichen '0' bis '9' zur Speicherung beschränken, dann hätte man es wirklich so wie in der Grundschule. Aber das wäre unnötig ineffizient, da ein Zeichen im Computer 256 verschiedene Werte haben kann und man somit unnötig Platz und Rechenzeit⁺ verschenkt.

^*: Dies ist natürlich eine Lüge, aber es gibt dir eine gute Vorstellung und ist auch gar nicht so weit von der Realität weg. In Wirklichkeit gibt es ein paar Tricks, die man nutzen kann, um effizienter als in der Grundschule zu sein. Viele dieser Tricks beruhen darauf, dass man eine Zahlenbasis hat, die eine Zweierpotenz ist, anstatt 10, wie in der Grundschule. Daher lernt man diese Tricks in der Grundschule nicht.

⁺: Dem Rechenwerk ist es egal, ob man sich auf '0' bis '9' beschränkt oder die vollen 256 Werte eines Bytes nutzt. Eine Addition von zwei Bytes dauert trotzdem gleich lange. Das ist auch der Grund, warum ich oben uint64_t als Basis vorgeschlagen habe statt char. Das Rechenwerk eines modernen Rechners kann nämlich mindestens 64-Bit gleichzeitig verrechnen. es würde sogar länger dauern, mit 8-Bit zu rechnen, da man die 64-Bit Werte, die aus dem Speicher kommen, erst passend zurecht stutzen müsste.