Rechnen mit beliebig langen Ganzzahlen

amiga-news.de Forum > Programmierung > Rechnen mit beliebig langen Ganzzahlen

[ - Suche - Neue Beiträge - Registrieren - Login - ]

-1-

[ - Beitrag schreiben - ]

21.03.2006, 21:35 Uhr

Honitos
Posts: 200
Nutzer

Moin,

ich muss bei einem Projekt mit sehr langen Ganzzahlen rechnen (100-300 Stellen). Dazu habe ich mir Stringbasierte Routinen geschrieben, die die vier Grundrechenarten nachbilden - viel zu langsam.

hat jemand zufällig irgendwo eine Bibliothek, oder quellcode in einer beliebigen Sprache, die eine schneller Methode benutzen ??

Gruss,
Sven

[ - Antworten - Zitieren - Direktlink - ]

21.03.2006, 23:09 Uhr

Flinx
Posts: 1073
Nutzer

OpenSSL enthält ein Paket namens bn (BigNum), vielleicht hilft das.

http://www.openssl.org/docs/crypto/bn.html#DESCRIPTION
http://www.openssl.org/source/

[ - Antworten - Zitieren - Direktlink - ]

22.03.2006, 00:11 Uhr

maia
Posts: 66
Nutzer

@Honitos:

Mal aus Neugier(das muß ja kommen): Wofür brauch man solch lange Zahlen?

[ - Antworten - Zitieren - Direktlink - ]

22.03.2006, 05:59 Uhr

Solar
Posts: 3680
Nutzer

Die wahrscheinlich simpelste Möglichkeit wäre in Perl, da der Support hier transparent erfolgt:

code:

#!/usr/bin/perl

use bignum;

...

Siehe z.B. hier.

[ - Antworten - Zitieren - Direktlink - ]

22.03.2006, 07:27 Uhr

Honitos
Posts: 200
Nutzer

@Flinx:
Danke - der Code ist zwar kaum lesbar, aber ich schaue mir den mal an.

@maia:
Für einen Verschlüsselungsalgorithmus, der auf sehr grossen Primzahlen basiert.

[ - Antworten - Zitieren - Direktlink - ]

22.03.2006, 11:08 Uhr

eliotmc
Posts: 925
Nutzer

@Honitos:

Alternativ nutze doch einfach ein short Array, das
sollte auf jeden Fall schneller sein als String.
Wobei arr[0] = x*10^0, arr[1] = x*10^1, ...

--
regards

eliot

[ - Antworten - Zitieren - Direktlink - ]

22.03.2006, 12:44 Uhr

Solar
Posts: 3680
Nutzer

OK, also anscheinend ist Perl nicht das "richtige" gewesen. Wie wäre es mit bignum.c?

[ - Antworten - Zitieren - Direktlink - ]

22.03.2006, 15:34 Uhr

Honitos
Posts: 200
Nutzer

@Solar:
Hi Solar !
Vielen Dank, das ist doch mal was.

@Eliotmc,
Der Tipp ist auch gut, das führt zu einer Beschleunigung um den Faktor 50, gemessen an der String-Variante, die ich vorher hatte...

[ - Antworten - Zitieren - Direktlink - ]

23.03.2006, 14:28 Uhr

Mad_Dog
Posts: 1944
Nutzer

Zitat:
Original von Honitos:

@maia:
Für einen Verschlüsselungsalgorithmus, der auf sehr grossen Primzahlen basiert.

Nenn das Kind doch gleich beim Namen: RSA.

--

http://www.norman-interactive.com

[ - Antworten - Zitieren - Direktlink - ]

23.03.2006, 15:00 Uhr

Supimajo
Posts: 1265
Nutzer

Wenns um RSA geht, dann gibts hier einen "RSA-Generator" der die BigNum-Funktion nutzt icl. Quelltext.

--
http://www.schwarzbuch-amiga.dl.am
Das "Verbraucherschutzforum" für AMIGA-Belange

[ - Antworten - Zitieren - Direktlink - ]

23.03.2006, 19:02 Uhr

Honitos
Posts: 200
Nutzer

Ja, es geht um RSA. Danke für den Link.
Mal sehen, ob ich das brauchen kann.
Hab die Routinen von bignum.c schon so konvertiert, dass das Prüfen einer Primzahl mit etwa 100 Stellen nur so um die 20sek dauert.
Da muss noch was drin sein, wenn ich keine ziffernmäßige, sondern eine bitweise Darstellung der Zahlen vornehme - dann kann man schön shiften...

Sven

[ - Antworten - Zitieren - Direktlink - ]

24.03.2006, 01:28 Uhr

_PAB_
Posts: 3016
Nutzer

Kennst jemand eine nette Bibliothek (die nicht GPL, sondern LGPL, BSD oder frei ist), die man sinnvoll in C++ einsetzen kann ?
Idealerweise sollte die Klasse auch "complex" Zahlen können oder zumindest als grundlegender Datentyp für eine vorhandene complex-Klasse geeignet sein.
Danke schonmal für die Hinweise

[ - Antworten - Zitieren - Direktlink - ]

24.03.2006, 12:31 Uhr

Supimajo
Posts: 1265
Nutzer

@_PAB_:

Hier soll man sich angeblich die wahrscheinlich schnellste BigNum-Library runterladen können (Freeware).

--
http://www.schwarzbuch-amiga.dl.am
Das "Verbraucherschutzforum" für AMIGA-Belange

[ - Antworten - Zitieren - Direktlink - ]

24.03.2006, 13:28 Uhr

Mad_Dog
Posts: 1944
Nutzer

Zitat:
Original von Honitos:
Hab die Routinen von bignum.c schon so konvertiert, dass das Prüfen einer Primzahl mit etwa 100 Stellen nur so um die 20sek dauert.
Da muss noch was drin sein, wenn ich keine ziffernmäßige, sondern eine bitweise Darstellung der Zahlen vornehme - dann kann man schön shiften...

Ich hoffe, Du hast auch die Carmichael-Zahlen
berücksichtigt

Und noch nen Tip: Da Du bei RSA mit sehr hohen Potenzen rechnest, solltest Du Sukzessive Quadratbildung benutzen.
--

http://www.norman-interactive.com

[ - Antworten - Zitieren - Direktlink - ]

25.03.2006, 20:02 Uhr

_PAB_
Posts: 3016
Nutzer

@Supimajo:
Ja, die GMP Bignum habe ich mir auch schon angesehen, nur leider finde ich hier keine Komplexen Zahlen.

[ - Antworten - Zitieren - Direktlink - ]

25.03.2006, 21:14 Uhr

Honitos
Posts: 200
Nutzer

Ist jemand in der Lage, aus den GMP Sourcen eine amigaOS shared library zu erzeugen ?? Ich habe mich damit noch nicht auseinander gesetzt, allerdings steht in der Doku, das man das für 68k kompilieren kann..

Gruss,
Sven

[ - Antworten - Zitieren - Direktlink - ]

26.03.2006, 17:51 Uhr

_PAB_
Posts: 3016
Nutzer

@Honitos:
Möglich ist das sicher, da es in C/C++ geschrieben ist.
Es wird vermutlich etwas Arbeit sein, das so zu machen, daß die Sourcen leicht zu updaten sind.

[ - Antworten - Zitieren - Direktlink - ]

-1-

[ - Beitrag schreiben - ]

amiga-news.de Forum > Programmierung > Rechnen mit beliebig langen Ganzzahlen

[ - Suche - Neue Beiträge - Registrieren - Login - ]