GCD d'une paire de produits

J'ai deux nombres, qui sont chacun le produit d'un grand nombre de petits nombres que je connais. Je veux trouver le GCD (le plus grand commun diviseur) de ces deux nombres. Existe-t-il un moyen d'utiliser la factorisation partielle dont je dispose pour accélérer le processus?

En particulier, chaque nombre plus grand est le produit de nombres plus petits, chacun étant de l'ordre de . Je ne sais rien de la factorisation des petits nombres.$2^{15}$$2^{4000}$

Edit: Alors que les nombres d'entrée sont d'environ 120 000 000 bits, le GCD est d'environ 500 000 bits. Les facteurs des nombres sont notamment en séquence. Ce sont tous des entiers dans une plage consécutive.

Tous les algorithmes GCD que j'ai vus utilisent directement les nombres, pas sous une forme partiellement factorisée ou quoi que ce soit. Existe-t-il des algorithmes qui pourraient intégrer ces informations pour accélérer les choses?

Vous pouvez calculer les GCD par paire des facteurs. Vous devez diviser les GCD des facteurs pour éviter de trouver deux fois le même facteur GCD:

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

Malheureusement, je ne pense pas que ce ne soit pas notablement plus rapide que le calcul du GCD des deux nombres A et B.

Un problème similaire a été résolu de manière raisonnablement efficace: supposons que vous utilisez RSA, qui est entièrement construit sur des produits de deux grands nombres premiers, où les produits ne peuvent pas être pris en compte dans un délai raisonnable. Mais si vous avez deux produits pq et p'q 'et soit p = p' ou q = q ', alors vous pouvez calculer leur pgc et obtenir p = p' ou q = q 'et l'autre facteur est trivial. Bien sûr, si p = p 'et aussi q = q', cela ne sert à rien.

N'imaginez pas que quelqu'un génère un milliard de ces produits et est un peu négligent. Un pirate trouve que plusieurs nombres sont identiques, donc p = p 'et q = q', donc c'est une bonne supposition que plusieurs paires ont un gcd d 1. Et cela s'est produit dans la vie réelle avec des routeurs dont le cryptage pourrait être fissuré en conséquence.

Désolé, je n'ai aucune référence et l'histoire est un peu ancienne, mais vous devriez pouvoir la trouver. C'était il y a quelques années, peut-être six environ.