Das deutsche QBasic- und FreeBASIC-Forum

[psygate]

Also gut... Ich hab jetzt seit einiger Zeit ein RIESEN Problem im wahrsten sinne des Wortes...

Alles begann, als ich einmal in Wikipedia von der RSA Verschlüsselung und Primzahlen gelesen hab, natürlich wollte ich das nachahmen und stieß auf ein Problem:

Kein einziger Datentyp war groß genug, um eine Zahl die größer als 10^38 ist zu fassen. Ich brauche eure hilfe, wie kann ich das realisieren, dass ich mmit Zahlen in der größenordnung 10^80 arbeiten kann und dann aucvh ncoht einen primzahlen check durchführen kann?

[Michael712]

Hallo.

Ich bin mir da nicht sicher, aber bei FreeBasic ist eine Lib dabei, die big_int oder so ähnlich heißt. Ich glaube dass das damit geht. Sonst musst du nach den anderen Mathematik librarys gucken.(alle bei fb dabei)

Mfg
Michael

[psygate]

gibts da nciht ein tut, wie ich die benutze??

[d.j.peters]

Hallo psygate,
da Du vermutlich "nur" ganze "positive" Zahlen im Bereich von 10 hoch 80 brauchst ist es möglich sich so etwas zu Programmieren aber sehr aufwendig.

Hier ein fertiges BASIC mit 2800 stelligen Zahlen oder so.
http://archives.math.utk.edu/software/msdos/number.theory/ubasic/.html

Grüsse Joshy

[vspickelen]

Und hier eine BASIC Langzahl-Lib mit Beispiel-Programmen für RSA:
http://mitglied.lycos.de/vspickelen/Largefiles/Nachladen.htm

Grützi,
vspickelen

[d.j.peters]

Hi vspickelen,
gut zu wissen kannte ich noch nicht.

Danke für den Link.

Grüsse Joshy

[Triton]

[MisterD]

auf QB-City gabs mal nen Taschenrechnerwettbewerb.. Da waren zwei von drei versionen mit strings.. die kriegen große zahlen zusammen (meiner zumindest, man muss halt die beschränkung rausnehmen). Die dritte Version war mit Arrays, ich glaub von EXP. Wie große Zahlen die bearbeitet weiß ich nicht..
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[psygate]

Das ist wahr, aber es gibt bei 10^80 sehr sehr viele möglickeiten, also, hat jemand eine gute library??

[MisterD]

wie gesagt, nimm am besten einfach eine der QB-Wettbewerbseinsendungen, frag ganz lieb und mach dann ne Lib draus oder so
Meine kannste benutzen wenn du willst.
_________________
"It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration."
Edsger W. Dijkstra

[tilli]

Moin,

Ein parr kleine Fragen mal:
- Kann ich davon ausgehen, dass du nur Integerzahlen brauchst?
- kann es sein, dass es sich um 256bit Zahlen handelt? (das wären 8* 32bit Integer)
- Welche Rechenoperatoren brauchst du? +,- und * sind nicht sooo tragisch, shifts sollten auch noch recht einfach machbar sein

CU2
Tilli

[psygate]

hm... die idee mit den strings hat mir gefallen... die befehle die ich brauche sind:

+,-,*,/,\,mod,xor,or,and usw, eigentlich die normalen befehle. Besonders nötig wäre ein "Primzahlcheck", der checkt, ob meine gigazahl auch wirkliche eine primzahl ist.

[Triton]

Na den sollte man nun wirklich noch selbst hinbekommen
_________________
Coding: silizium-net.de | Portfolio: Triton.ch.vu

[psygate]

mod usw schon, aber wie mach ich das mit dem primzahlcheck??

[OdinX]

wenn du dividieren kannst ist das dann ja kein problem mehr

[tilli]

Moin,

wenn es sich um Verschlüsselungn handelt, sollt man mit Priemzahlen aufpassen - das schränkt die Zahl der durchzuprobierenden Varianten doch schon extrem ein ...

CU2
Tilli

[psygate]

Im grunde richtig, aber, eine normale zahl kann man einfach wieder berechnen: ein beispiel:

(Bitte nciht ernst nehmen, bei 10^80 stellen großen zahlen wird dann etwas kniffeliger!)

Also, nehmen wir 20 und 42. (Ich übertreibe einfach mal!)

20*42=840.................Demnach ist 840 unser Public key.
Jetzt kann man aber einfach die nachricht entschlüsseln, weil sich 840 leicht factorisieren lässt, genauso wie 20 und 42. Damit wäre unser code entschlüsselt.

aber:

13*19=247.............................247 ist unser puvlic key.

247 kann aber nun nur in 13 und 19 factorisirt werden, eine andere möglichkeit gibt es nciht!
Somit wäre es viel schwerer, da es lange dauert, um eine 10^80 stellen lange primzahl zu finden.

[Triton]

[OdinX]

Umso besser wenn gerade mit Freebasic eine höhere gefunden wird.

[tilli]

Moin,
bekanntermaßen ist nichts auf dieser Welt absolut sicher, außer der TOD...

Die Frage ist doch eher, ob durch die Wahl einer Teilweise- Priemzahl nicht alles ncoh schwieriger wird:

Die Priemzahlen kann man in eine Liste eintragen - das ist im Schnitt so jede 50ste.

Wenn der Text nun entschlüsselt teilweise einen sinnvollen Code ergibt, dann ist es nicht gerade viel - es könnte auch ein Zufallsergebnis sein.

Leider kenne ich das dahinter steckende System nicht so genau.

Ich denke das Produkt aus 2 oder 3 Priemzahlen des Bereiches 10^(80/3) sollte noch viel weniger ratbare Zahlen ergeben... Jetzt weis ich allerdings nicht, ob zum Codieren eine entsprechende Priemzahl nicht dringend nötig ist ... Um die eindeutigkeit zu bewerkstelligen. Dann müsste man sie nehmen - oder den Algorythmus abändern - das ist dann die Variante, bei der am ehesten keiner drauf kommt

CU2
Tilli