GCD eines Produktpaares

Ich habe zwei Zahlen, die jeweils das Produkt einer großen Anzahl kleinerer Zahlen sind, die ich kenne. Ich möchte den GCD (Greatest Common Divisor) dieser beiden Zahlen finden. Kann ich die teilweise Faktorisierung nutzen, um den Prozess zu beschleunigen?

Insbesondere ist jede größere Zahl das Produkt von kleineren Zahlen, von denen jede in der Größenordnung von 2 4000 liegt . Ich weiß nichts über die Faktorisierung der kleineren Zahlen.$2^{15}$$2^{4000}$

Bearbeiten: Während die Eingangsnummern ungefähr 120.000.000 Bit betragen, beträgt die GCD ungefähr 500.000 Bit. Die Faktoren der Zahlen sind insbesondere der Reihe nach. Sie sind alle ganze Zahlen in einem aufeinanderfolgenden Bereich.

Alle GCD-Algorithmen, die ich gesehen habe, verwenden die Zahlen direkt, nicht in teilweise faktorisierter Form oder so. Gibt es Algorithmen, die diese Informationen enthalten könnten, um die Dinge zu beschleunigen?

Sie können die paarweisen GCDs der Faktoren berechnen. Sie müssen die GCDs von den Faktoren trennen, um zu vermeiden, dass derselbe GCD-Faktor zweimal gefunden wird:

a[1...m] = [given factors of A]
b[1...n] = [given factors of B]
g = 1
for i from 1 to m do
    c = a[i]
    for j from 1 to n do
        d = gcd(c, b[j])
        g = g * d
        c = a[i] / d
        b[j] = b[j] / d
return g

Leider glaube ich nicht, dass dies nicht wesentlich schneller ist als die Berechnung der GCD der beiden Zahlen A und B.

Es gab ein ähnliches Problem, das relativ effizient gelöst wurde: Angenommen, Sie verwenden RSA, das alle auf Produkten mit zwei großen Primzahlen basiert, bei denen die Produkte nicht in angemessener Zeit berücksichtigt werden können. Wenn Sie jedoch zwei Produkte pq und p'q 'und entweder p = p' oder q = q 'haben, können Sie deren gcd berechnen und p = p' oder q = q 'erhalten, und der andere Faktor ist trivial. Wenn p = p 'und auch q = q' ist, ist dies natürlich keine Hilfe.

Keine Vorstellung, dass jemand eine Milliarde solcher Produkte herstellt und ein bisschen nachlässig ist. Ein Hacker stellt fest, dass einige Zahlen identisch sind, also p = p 'und q = q'. Es ist also eine gute Vermutung, dass einige Paare eine gcd ≠ 1 haben. Und das ist im wirklichen Leben mit Routern passiert, deren Verschlüsselung dies könnte dadurch geknackt werden.

Entschuldigung, ich habe keine Referenz und die Geschichte ist ein bisschen alt, aber Sie sollten sie finden können. War vor ein paar Jahren, vielleicht sechs oder so.