Factoring eine große Zahl

Mögliche Duplizieren:
Factor a large number efficiently with gmp Factoring eine große Zahl

Ich weiß, dass ich es schon geschrieben, aber die Leute falsch verstanden, was ich meinte, und bis ich es der Post starb fixiert.
Was ich brauche, ist eine Möglichkeit, große Zahlen effizient zu faktorisieren (bis 2048 Bits zu finden) mit C++ und GMP (Gnu Multiple Precession lib) oder weniger bevorzugt auf andere Weise.
Die Zahlen sind praktisch zufällig, so dass es kaum eine Chance gibt, es wird schwer zu faktorisieren, und selbst wenn die Zahl schwer zu faktorisieren ist, kann ich die Zahl wiederholen (kann aber nicht wählen).
Wie mache ich das?

Quelle

2010-12-05 Dani

Oh, bitte lassen Sie uns wissen, wenn Sie es schaffen. Wenn Sie das tun, haben Sie im Wesentlichen alle Formen der Verschlüsselung mit öffentlichem/privatem Schlüssel unabhängig vom genauen Algorithmus gebrochen. Goodbye ssl, auf Wiedersehen ssh und vor allem auf Wiedersehen verschlüsselte militärische Kommunikation. – slebetman

Posts sterben nicht auf Stack Overflow. Die Frage ist immer noch da. Also, was ist das Problem? –

Sind Sie sicher, dass Sie eine große Zahl berücksichtigen müssen? Wenn Sie die Zahlen wählen können, warum multiplizieren Sie nicht viele kleine Primzahlen, bis Sie eine Zahl in Ihrer Reichweite haben? Dann kennen Sie bereits die Faktoren ... – jtdubs

Haben Sie versucht, die quadratic sieve oder die general number field sieve? (QS einfacher und leichter zu implementieren, GNFS schneller für sehr große Zahlen, aber Ihre Zahlen möglicherweise nicht groß genug sein, für GNFS viel schneller als QS sein)

bearbeiten: Nach a paper by Eric Landquist, dem Kreuzungspunkt zwischen QS und GNFS ist ungefähr 110 Stellen = ungefähr 365 Bits.

Quelle

2010-12-05 14:19:53

Es gibt keinen effizienten Weg (wahrscheinlich). Diese Annahme ist die Grundlage der modernen Kryptographie.

Quelle

2010-12-05 14:19:35

Bitte erläutern Sie den Downvote. Es mag niemanden gefallen, aber das ist die Antwort. –

-1: "Effizient" ist in diesem Zusammenhang ohne quantitative Angabe aus dem OP nicht sinnvoll, wer mag mit Tagen oder Wochen Laufzeit gut sein. –

Sie ignorieren auch den OP-Kommentar: "Die Zahlen sind praktisch zufällig, also gibt es kaum eine Chance, dass es schwer wird" –

Eine Möglichkeit, dies effizient zu tun, wird viele der derzeit verwendeten Verschlüsselungsalgorithmen durchbrechen.
Dies ist ein NPC-Problem, also ....

Quelle

2010-12-05 14:19:51

Sie ignorieren den OP-Kommentar: "Die Zahlen sind praktisch zufällig, so dass es kaum eine Chance gibt, wird es schwer zu faktor" –

@Jason: "Die Zahlen sind praktisch zufällig, so gibt es kaum eine Chance wird es schwer zu Faktor" ist ein kleiner Verdächtiger. Die RSA-Schlüsselerzeugung erfolgt mit praktisch zufälligen Zahlen (wenn auch das niedrige Bit immer auf 1 gesetzt ist). –

Wenn ich nichts vermisse Dies ist bekannt als ein "schwieriges" Problem. http://en.wikipedia.org/wiki/Integer_factorization. das ist derzeit unmöglich.

Quelle

2010-12-05 14:20:37 Daniel

Es gibt keine bekannte Möglichkeit, große Zahlen effizient zu faktorisieren. Eine Diskussion über warum und den Stand der Technik finden Sie unter Wikipedia.

Wie die Kommentare gezeigt haben, ist die Schwierigkeit dieses Problems die Grundlage für viele moderne Kryptographie, insbesondere Public-Key-Verschlüsselung.

Was Sie könnte tun ist eine Tabelle von kleinen Primzahlen speichern und arbeiten durch diese Tabelle Ihre große Anzahl von jedem Kandidaten Prime teilen, wie es geht. Wenn die Zahl "zu hart" ist (d. H., Sie haben keine kleinen Primzahlen mehr), wiederholen Sie den Vorgang.

Quelle

2010-12-05 14:20:53

Warum die Downvotes (für diese und ähnliche Antworten)? Sie haben nach einer effizienten Methode zur Faktorisierung großer Zahlen gefragt. Es gibt keine solche Methode. Nur weil du die Realität der Situation nicht magst, ist es kein Grund, eine korrekte Antwort zu verwerfen. –

Sie ignorieren den OP Kommentar: "Die Zahlen sind praktisch zufällig, so dass es kaum eine Chance gibt, wird es schwer zu Faktor sein" –

http://en.wikipedia.org/wiki/General_number_field_sieve

Viel Glück!

Quelle

2010-12-05 14:23:08

Warum denkst du wird es nicht schwer sein zu faktorisieren? Ja, es wird einige kleine Faktoren geben. Aber der Rest wird groß genug sein in einer Reihe von dieser Größe, dass es oft einige ernste Arbeit braucht, um zu berücksichtigen.

Ich würde Trial Divisionen durch einige kleine Primzahlen vorschlagen, um den kleinen Fisch aus dem Teich zu bekommen. Dann könntest du Pollards Rho-Methode ausprobieren, aber ich bezweifle, dass sie bei Zahlen mit so vielen Bits eine Chance hat. Besser wäre ein quadratisches Sieb.

Quelle

2010-12-05 14:31:06

Antwort

Verwandte Themen