Umgehung der Ungenauigkeiten bei einem Faktorisierungsprogramm
-
Hallo an alle!
Im Rahmen einer Arbeit über Kryptographie habe ich ein Programm geschrieben, dass den Aufwand untersucht um eine große Zahl in ihre ebenfalls großen Primzahlen zu zerlegen. Dabei erzeuge ich erst eine Zahl aus zwei großen Primzahlen und faktorisiere diese anschließend wieder um den Aufwand zu betrachten. Leider kommt es bereits bei der Multiplikation dieser großen Primzahlen (ab etwa 10^8 pro Primzahl) zu derart großen Ungenauigkeiten, dass die Zahl falsch faktorisiert wird.
Kennt jemand vielleicht eine Möglichkeit/ein Multiplikationsverfahren dies durch bsp. Runden an der richtigen Stelle zu umgehen ohne gleich den komplizierten Weg über GNU MP wählen zu müssen?
Mir ist relativ egal wie genau die Zahlen im Verlauf der Rechnung sind, solange ich am Ende das richtige Produkt erhalte um es zu zerlegen.Besten Dank
-
es kemmt auf die letzet stelle an.
hast du etwa double genommen? das wäre fatal.
-
Ja habe ich, allerdings weiß ich nicht wie ich die großen Zahlen sonst behandeln könnte. Kennt jemand vllt. ein System das die Zahlen trotz double korrekt multipliziert?
-
ich multipliziere große zahlen immer mitr gmp und stopfe sie erst am ende in einen double. weil der double nicht genug platz für alle ziffern hat, fallen die letzten ziffern weg. damit sien die zahlen dann kaputt. ende gelände.
du kannst dir doch sicherlich vorstellen, daß 1000000000000000 und 1000000000000001 andere faktoren haben. bei 1000000000000000 sehe ich lauter 2 und 5 als primfaktoren, bei 1000000000000001 sind alle weg.
-
Ja klar, bloß sollte double noch Zahlen der genannten Größe speichern können. Gibt es irgendwo noch eine ausführlichere Anleitung für gmp als die Doku auf gmplib.org? Diese ist mit etwas zu kompliziert.
Besten Dank
-
Enceladus25 schrieb:
Ja klar, bloß sollte double noch Zahlen der genannten Größe speichern können.
haben deine doubles eine matisse von 52 bit?
wenn ja, passen da nur 15 dezimalziffern rein und nicht 16, wie du in deinem eingangspostings haben willst.
welches problem hast du damit, daß der double ziffern abschippelt?
nimm unsigned long long, damit kommst du auf 19 ziffern hoch.
es liegt nicht am rechnen, sondern deine dicken zahlen passen in den double einfach nicht rein.