Also, ich sitze zur Zeit an einer Implementation des RSA-Algorithmus und dazu ist es notwendig, das ich mit Primzahlen der Größenordnung zwischen 1024 und 4096 Bit (also zwischen 128 und 512 Byte) rechnen muss. Jetzt wollte ich mal fragen, ob hier jemand vielleicht Ideen hat, wie man so etwas theoretisch anstellen kann. Da gäbe es Beispielsweise die Möglichkeit einen Array von 512 ( eventuell + 2 Byte für die Angabe der Verwendeten Stellen ) Byte anzulegen und mit diesem Array die Grundrechenoperationen auszuführen. (Das ganze wird nicht in C geschrieben, daher kann ich keine Bitshiftoperatoren einsetzen)

Hat jemand eine bessere Idee, oder kann mir jemand einen Denkanstoss geben, wie ich damit rechnen kann?

[offtopic]
Hmm keine Ahnung, erinnert mich aber an den Film "Cube", nur hatten die da son Genie dass sich die ganzen Zahlen merken konnte... :)

Greetz CorDharel

Leader der HolyShitBastards

bitte beim thema bleiben. Mir ist das recht wichtig...

Du solltest dich an die Grundschule zurückerinnern ;p
Im Prinzip kannst du die Grundrechenarten einfach implementieren, indem du dir die Zahlen als Zahlen zur Basis 2^32 denkst, und für jede "Ziffer" einen 32-Bit-Integer verwendest. Dann kann man die grundlegenden Algorithmen für schriftliche Addition/Division/Multiplikation anwenden - das ist zumindest mal ein Anfang.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Wenn du uns eine Sprache sagst, können wir dir ja vielleicht auch mehr helfen. In Java zm Beispiel gibt es schon eine BigInteger.

georg-wicherski@pixel-house.net | http://www.pixel-house.net/ - Coding Resource| http://www.google.de/

Und ich habe für Delphi mal eine Klasse für 128Bit Zahlen geschrieben. Könnte man auch umschreiben (falls es für Delphi ist ;)).

nee, ich will nicht soviel verraten, da es für eine facharbeit ist, wo man ja bekannterweise möglichst viel selber erarbeiten soll.

Gibt es denn noch andere Möglichkeiten mit solchen Zahlen umzugehen?

Also, die verwendete Sprache wirst du ja auch wohl bei ner Facharbeit "verraten" können...
Wenn es für eine Facharbeit ist, dann ist eher die letzte Frage unangebracht ;p

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

also vom programmieren hab ich verdammt wenig checkung aber wenns dir hilft. ich hab nen prog das kann riesege datein öffnen (bis zu 2GB) hat ja auch was mit größe zu tun vieleicht kann dir das helfen.
wenn du denkst das es nützlich sein könnte, antworte und ich suche mal die adresse raus.

Die Lösung aller Eurer Probleme:
||Die Liste aller Compilier Fehler.|Der ultimative Compile Log Anaylizer||
||How to: Fragen stellen.||
||Sieben Wege LEAKs zu finden.||
||Die letzten wirklich bug-freien Compiler (Juli)||

@Zahnarzt: Hat leider nix damit zu tun.
@Topic: Kannst du wenigstens verraten, ob die Sprache inline assambler unterstützt. Dann wäre das nämlich einiges einfacher... Oder am besten gleich die Sprache posten (auch wenn jetzt BrainFuck oder so kommt *fg*)

err... ich wollte ja nur frage, ob einer noch eine idee hat, wie man sowas bewerkstelligen könnte, rein theoretisch nur ansatzweise. Ausarbeiten würde ich es ja eben.

Der Grund, warum ich nicht die Programmiersprache poste ist, das ich Angst habe, dass dann ein nettgemeinter Rat kommt, der mir zuviel vorwegnimmt, und dann wäre das ganze für die katz... Ist bescheuert, aber blöderweise tatsächlich so wahr.

@Hausi: Theoretisch schon, aber ich kenn mich nicht mit asm so gut aus, und das muss ja von mir ausgearbeitet werden. Also nützen tut mir nur reine Theorie...

Ok:
Da du kein asm kannst und auch keine Bitshiftops hast, würde ich dir vorschlagen, deine Idee mit dem Array von Bytes machen. Das Rechnen damit zeige ich mal Ansatzweise am Beispiel der Add-Funktion:
--------------------------------------------------------
#define MAX_NUM_PER_ELEMENT 255
#define NUM_BYTES 512
myInt Add( myInt num2 )
{
for (int i=0; i<NUM_BYTES; i++)
if (data[i]+num2.data[i]>MAX_NUM_PER_ELEMENT)
{
data[i]+=num2.data[i]-MAX_NUM_PER_ELEMENT;
for (int j=i; j<=NUM_BYTES; j++)
{
if (j==NUM_BYTES)
{
// Overflow error
}
else if (num2.data[j]<MAX_NUM_PER_ELEMENT)
{
num2.data[j]++;
break;
}
}
}
else
{
data[i]+=num2.data[i];
}
}
}
--------------------------------------------------------
Hoffe, mir ist kein Fehler unterlaufen; hab alles kurz aus dem Kopf geschrieben...
Ist leider nicht zu effizient, weil er dadurch durch alle Bytes loopen muss, gibt aber leider nicht viele andere Möglichkeiten. Ich hoffe, dass dir das hilft, einen guten Einstieg zu finden... Sonst einfach nochmal posten (habe extra die einfachste Funktion genommen zum zeigen, damit du auch noch was machen musst; schwer wirds dann bei der Divide-Funktion).

[Edit]
Codes deaktiviert --> WILL 2.8 hier >:(
[/Edit]

Du solltest es wie Prefect machen und einen byte (char) Array machen, indem jeder byte eine Ziffer in einem 256iger Zahlensystem represäntiert.

georg-wicherski@pixel-house.net | http://www.pixel-house.net/ - Coding Resource| http://www.google.de/

naja, danke, hausi...

@OneStone:
öhm... die idee war glaub ich meine... :)

Also ich würd so machen:
Eine komplett eigene Klasse für die Zahlen definieren. Innerhalb der Klasse dann die einzelnen Stellen der Zahl als einfach verkettete Liste repräsentieren. Dann die ganzen Operatoren überladen. Fertig.

www.d3opencoop.com - A Doom3 Cooperative Mod

Linked List ist viel zu aufwendig und Speicherverschwendung. In diesem Fall ist ein (womöglich dynamisches) Array sicher besser.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Erklär mal, wieso ein dynamisches Array weniger Speicher benötigt als eine verkette Liste.

www.d3opencoop.com - A Doom3 Cooperative Mod

ich hab mich übrigens inzwischen dazu entschieden einen byte-array zu nutzen in dem jeweils werte von 0 - 255 ( logisch, byte halt ) gespeichert werden, was von hinten nach vorne abgespeichert wird. Addition, Multiplikation und Subtraktion ist schon klar, aber wie dividiere ich?

Weil jedes Element der verketteten Liste einen Pointer auf das nächste Element enthält -> 4 byte mehr pro Element.

BTW @ Apfelkorn:

Zitat:

Prefect postete
Du solltest dich an die Grundschule zurückerinnern ;p
Im Prinzip kannst du die Grundrechenarten einfach implementieren, indem du dir die Zahlen als Zahlen zur Basis 2^32 denkst, und für jede "Ziffer" einen 32-Bit-Integer verwendest. Dann kann man die grundlegenden Algorithmen für schriftliche Addition/Division/Multiplikation anwenden - das ist zumindest mal ein Anfang.

cu,
Prefect

georg-wicherski@pixel-house.net | http://www.pixel-house.net/ - Coding Resource| http://www.google.de/

Bei der Linked List kommt auch noch die Heapfragmentation dazu.

Apfelkorn: Division durch Zahlen mit nur einer "Ziffer" sollte klar sein. Für die Division durch beliebig große Zahlen hab ich jetzt aber auch keine Lösung parat.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

@Superhausi:

MyInt ist also ne struct mit byte *data ?
Und wenn ich diese Zahl jetzt z.B. in der Konsole Anzeigen lassen will?:
3248989972388349038477782833489327489236782319840213973483784512365256564293547812369784689721367891278956516351276548736578678

Wie macht man das? (Ich suche auch na so einer große-Zahlen möglichkeit, für Primzahlen.Berechnung in C/C++, nach dem Motto "ICH FINDE DIE GRÖßTE PRIMZAHL!!!!". Am besten gleich ausdrucken *g*)

thx, cu, MfG the_viking

(( My =]=H=O=M=E=> Page! ))
Coder bei Brainshock-Interactive und bei Z-Software
My ICQ: #160959446

Das macht man genauso, wie man es bei normalen Zahlen auch macht: Schrittweise durch die Basis dividieren, den Rest anzeigen und das Ergebnis im nächsten Schritt verwenden. (Hinterher mußt du natürlich noch die Reihenfolge der Ziffern umdrehen, da sie in der falsche Reihenfolge herauskommen).

Ein alternatives System mit nicht ganz so vielen Divisionen bestünde darin, statt Ziffern mit Basis 2^32 Ziffern mit der Basis 10^9 zu verwenden (ein int pro Ziffer). Da verschwendet man dann zwar etwas Speicherplatz, aber man kann immer schön gemütlich 9 Basis-10-Ziffern auf einmal ausgeben, ohne umständliche Divisionen durchzuführen.
Je nach Aufgabenstellung ist das evtl. schneller.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.