amiga-news DEUTSCHE VERSION
.
Links| Forums| Comments| Report news
.
Chat| Polls| Newsticker| Archive
.

amiga-news.de Forum > Programmierung > Rechnen mit beliebig langen Ganzzahlen [ - Search - New posts - Register - Login - ]

-1- [ - Post reply - ]

2006-03-21, 21:35 h

Honitos
Posts: 200
User 		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

[ - Answer - Quote - Direct link - ]
2006-03-21, 23:09 h

Flinx
Posts: 1073
User 		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/

[ - Answer - Quote - Direct link - ]
2006-03-22, 00:11 h

maia
Posts: 66
User 		@Honitos:

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

[ - Answer - Quote - Direct link - ]
2006-03-22, 05:59 h

Solar
Posts: 3680
User 		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.

[ - Answer - Quote - Direct link - ]
2006-03-22, 07:27 h

Honitos
Posts: 200
User 		@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.

[ - Answer - Quote - Direct link - ]
2006-03-22, 11:08 h

eliotmc
Posts: 925
User 		@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

[ - Answer - Quote - Direct link - ]
2006-03-22, 12:44 h

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

[ - Answer - Quote - Direct link - ]
2006-03-22, 15:34 h

Honitos
Posts: 200
User 		@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...

[ - Answer - Quote - Direct link - ]
2006-03-23, 14:28 h

Mad_Dog
Posts: 1944
User
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

[ - Answer - Quote - Direct link - ]
2006-03-23, 15:00 h

Supimajo
Posts: 1265
User 		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

[ - Answer - Quote - Direct link - ]
2006-03-23, 19:02 h

Honitos
Posts: 200
User 		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

[ - Answer - Quote - Direct link - ]
2006-03-24, 01:28 h

_PAB_
Posts: 3016
User 		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

[ - Answer - Quote - Direct link - ]
2006-03-24, 12:31 h

Supimajo
Posts: 1265
User 		@_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

[ - Answer - Quote - Direct link - ]
2006-03-24, 13:28 h

Mad_Dog
Posts: 1944
User
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

[ - Answer - Quote - Direct link - ]
2006-03-25, 20:02 h

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

[ - Answer - Quote - Direct link - ]
2006-03-25, 21:14 h

Honitos
Posts: 200
User 		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

[ - Answer - Quote - Direct link - ]
2006-03-26, 17:51 h

_PAB_
Posts: 3016
User 		@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.

[ - Answer - Quote - Direct link - ]

-1- [ - Post reply - ]


amiga-news.de Forum > Programmierung > Rechnen mit beliebig langen Ganzzahlen [ - Search - New posts - Register - Login - ]


.
Masthead | Privacy policy | Netiquette | Advertising | Contact
Copyright © 1998-2024 by amiga-news.de - all rights reserved.
.