GCD of a pair of products I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use of the partial factorization I have to speed up the process?

In particular, each larger number is the product of $2^{15}$ smaller numbers, each of which is on the order of $2^{4000}$. I don't know anything about the factorization of the smaller numbers.

Edit:
While the input numbers are about 120,000,000 bits, the GCD is about 500,000 bits. The factors of the numbers are in particular in sequence. They are all integers in a consecutive range.

All of the GCD algorithms I've seen make use of the numbers directly, not in a partially factored form or anything. Are there any algorithms which could incorporate this information to speed things up?
You can compute the pairwise GCDs of the factors. You have to divide out the GCDs from the factors to avoid finding the same GCD factor twice:

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


Unfortunately, I don't think that this is not notably faster than the computation of the GCD of the two numbers A and B.