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?
GCD of a pair of products
algorithms;number theory;performance